Found problems: 5802
Let $(a_n), n = 0, 1, . . .,$ be a sequence of real numbers such that $a_0 = 0$ and
\[a^3_{n+1} = \frac{1}{2} a^2_n -1, n= 0, 1,\cdots\]
Prove that there exists a positive number $q, q < 1$, such that for all $n = 1, 2, \ldots ,$
\[|a_{n+1} - a_n| \leq q|a_n - a_{n-1}|,\]
and give one such $q$ explicitly.
Let $ a_1,a_2,\dots$ be sequence of real numbers such that $ a_1\equal{}1$, $ a_2\equal{}\dfrac{4}{3}$, and \[ a_{n\plus{}1}\equal{}\sqrt{1\plus{}a_na_{n\minus{}1}}, \quad \forall n \ge 2.\] Prove that for all $ n \ge 2$, \[ a_n^2>a_{n\minus{}1}^2\plus{}\dfrac{1}{2}\] and \[ 1\plus{}\dfrac{1}{a_1}\plus{}\dfrac{1}{a_2}\plus{}\dots\plus{}\dfrac{1}{a_n}>2a_n.\]
[i]Fajar Yuliawan, Bandung[/i]
Given positive integer $n (n \geq 2)$, find the largest positive integer $\lambda$ satisfying :
For $n$ bags, if every bag contains some balls whose weights are all integer powers of $2$ (the weights of balls in a bag may not be distinct), and the total weights of balls in every bag are equal, then there exists a weight among these balls such that the total number of balls with this weight is at least $\lambda$.
Let $n$ be a positive integer. Find the number of sequences $a_0,a_1,a_2,\dots,a_{2n}$ of integers in the range $[0,n]$ such that for all integers $0\leq k\leq n$ and all nonnegative integers $m$, there exists an integer $k\leq i\leq 2k$ such that $\lfloor k/2^m\rfloor=a_i.$
[i]Andrew Carratu[/i]
Let $n$ be a positive integer. A [i]Japanese triangle[/i] consists of $1 + 2 + \dots + n$ circles arranged in an equilateral triangular shape such that for each $i = 1$, $2$, $\dots$, $n$, the $i^{th}$ row contains exactly $i$ circles, exactly one of which is coloured red. A [i]ninja path[/i] in a Japanese triangle is a sequence of $n$ circles obtained by starting in the top row, then repeatedly going from a circle to one of the two circles immediately below it and finishing in the bottom row. Here is an example of a Japanese triangle with $n = 6$, along with a ninja path in that triangle containing two red circles.
[asy]
// credit to vEnhance for the diagram (which was better than my original asy):
size(4cm);
pair X = dir(240); pair Y = dir(0);
path c = scale(0.5)*unitcircle;
int[] t = {0,0,2,2,3,0};
for (int i=0; i<=5; ++i) {
for (int j=0; j<=i; ++j) {
filldraw(shift(i*X+j*Y)*c, (t[i]==j) ? lightred : white);
draw(shift(i*X+j*Y)*c);
}
}
draw((0,0)--(X+Y)--(2*X+Y)--(3*X+2*Y)--(4*X+2*Y)--(5*X+2*Y),linewidth(1.5));
path q = (3,-3sqrt(3))--(-3,-3sqrt(3));
draw(q,Arrows(TeXHead, 1));
label("$n = 6$", q, S);
label("$n = 6$", q, S);
[/asy]
In terms of $n$, find the greatest $k$ such that in each Japanese triangle there is a ninja path containing at least $k$ red circles.
Let $n$ be a positive integer. We start with $n$ piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of $n$) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.
Is it possible to put $\binom{n}{2}$ consecutive natural numbers on the edges of a complete graph with $n$ vertices in a way that for every path (or cycle) of length $3$ where the numbers $a,b$ and $c$ are written on its edges (edge $b$ is between edges $c$ and $a$), $b$ is divisible by the greatest common divisor of the numbers $a$ and $c$?
[i]Proposed by Morteza Saghafian[/i]
Consider the $n \times n$ “multiplication table” below. The numbers in the first column multiplied by the numbers in the first row give the remaining numbers in the table.
[asy]
import graph;
size(3.5cm);
for (int x=0; x<=5; ++x)
draw((x, 0) -- (x, 5), linewidth(.5pt));
for (int y=0; y<=5; ++y)
draw((0, y) -- (5, y), linewidth(.5pt));
draw((0,0)--(5,0)--(5,5)--(0,5)--cycle);
void foo(int x, int y, string n)
{
label(n, (x+0.5, y+0.5));
}
foo(0, 4, "1");
foo(1, 4, "2");
foo(2, 4, "3");
foo(3, 4, "$\dots$");
foo(4, 4, "$n$");
foo(0, 3, "2");
foo(1, 3, "4");
foo(2, 3, "6");
foo(3, 3, "$\dots$");
foo(4, 3, "$2n$");
foo(0, 2, "3");
foo(1, 2, "6");
foo(2, 2, "9");
foo(3, 2, "$\dots$");
foo(4, 2, "$3n$");
foo(0, 1, "$\vdots$");
foo(1, 1, "$\vdots$");
foo(2, 1, "$\vdots$");
foo(3, 1, "$\ddots$");
foo(4, 1, "$\vdots$");
foo(0, 0, "$n$");
foo(1, 0, "$2n$");
foo(2, 0, "$3n$");
foo(3, 0, "$\dots$");
foo(4, 0, "$n^2$");
[/asy]
We create a path from the upper-left square to the lower-right square by always moving one cell either to the right or down. For example, in the case $n = 5$, here is one such possible path, with all the numbers along the path circled:
[asy]
import graph;
size(3.5cm);
for (int x=0; x<=5; ++x)
draw((x, 0) -- (x, 5), linewidth(.5pt));
for (int y=0; y<=5; ++y)
draw((0, y) -- (5, y), linewidth(.5pt));
draw((0,0)--(5,0)--(5,5)--(0,5)--cycle);
void foo(int x, int y, string n)
{
label(n, (x+0.5, y+0.5));
}
draw(Circle((0.5,4.5),0.5));
draw(Circle((1.5,4.5),0.5));
draw(Circle((2.5,4.5),0.5));
draw(Circle((2.5,3.5),0.5));
draw(Circle((3.5,3.5),0.5));
draw(Circle((3.5,2.5),0.5));
draw(Circle((3.5,1.5),0.5));
draw(Circle((3.5,0.5),0.5));
draw(Circle((4.5,0.5),0.5));
foo(0, 4, "1");
foo(1, 4, "2");
foo(2, 4, "3");
foo(3, 4, "4");
foo(4, 4, "5");
foo(0, 3, "2");
foo(1, 3, "4");
foo(2, 3, "6");
foo(3, 3, "8");
foo(4, 3, "10");
foo(0, 2, "3");
foo(1, 2, "6");
foo(2, 2, "9");
foo(3, 2, "12");
foo(4, 2, "15");
foo(0, 1, "4");
foo(1, 1, "8");
foo(2, 1, "12");
foo(3, 1, "16");
foo(4, 1, "20");
foo(0, 0, "5");
foo(1, 0, "10");
foo(2, 0, "15");
foo(3, 0, "20");
foo(4, 0, "25");
[/asy]
If we add up the circled numbers in the example above (including the start and end squares), we get $93$. Considering all such possible paths on the $n \times n$ grid:
(a) What is the smallest sum we can possibly get when we add up the numbers along such a path? Express your answer in terms of $n$, and prove that it is correct.
(b) What is the largest sum we can possibly get when we add up the numbers along such a path? Express your answer in terms of $n$, and prove that it is correct.
Let $n$, $(n \geq3)$ be a positive integer and the polynomial $f(x)=(1+x) \cdot (1+2x) \cdot (1+3x) \cdot ... \cdot (1+nx)$ $= a_0+a_1 \cdot x+a_2 \cdot x^2+a_3 \cdot x^3+...+a_n \cdot x^n$. Show that the number $a_3$ divides the number $k=C^2_{n+1} \cdot (2 \cdot C^2_n \cdot C^2_{n+1}-3 \cdot a_2).$
Let $n$ be a positive integer. Two players $A$ and $B$ play a game in which they take turns choosing positive integers $k \le n$. The rules of the game are:
(i) A player cannot choose a number that has been chosen by either player on any previous turn.
(ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn.
(iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game.
The player $A$ takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies.
[i]Proposed by Finland[/i]
Numbers $1, 2,\ldots, n$ are written on the board. By one move, we replace some two numbers $ a, b$ with the number $a^2-b{}$. Find all $n{}$ such that after $n-1$ moves it is possible to obtain $0$.
Define a sequence of positive rational numbers $x_0, x_1, x_2, x_3, \cdots$ by $x_0 = 2, x_1 = 3,$ and
for all $n \geq 2,$
$$x_n = \frac{x_{n-1}^2 + 5}{x_{n-2}}$$
(a) Prove that $x_n$ is an integer for all $n \geq 0.$
(b) Prove that if $x_n$ is prime, then either $n = 0$ or $n = 2^k$ for some integer $k \geq 0.$
Prove that for evey positive integer n, there exits a positive integer k such that $ 2^n | 19^k \minus{} 97$
For all $n\ge2$ positive integer, let $f(n)$ denote the product of all distinct prime divisors of $n$. For example, $f(5)=5$, $f(8)=2$, and $f(12)=6$. Given a sequence ${a_n}$, where $a_1\ge2$, defined as follows:
$$a_{n+1}=a_n+f(a_n)$$
Show that for any prime $p$, there exists a term $a_k$ in the sequence such that $p|a_k$.
In a party among any four persons there are three people who are mutual acquaintances or mutual strangers. Prove that all the people can be separated into two groups $A$ and $B$ such that in $A$ everybody knows everybody else and in $B$ nobody knows anybody else.
Let $x_1, x_2, \dots, x_n$ be different real numbers. Prove that
\[\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}=\left\{\begin{array}{ll}
0, & \text { if } n \text { is even; } \\
1, & \text { if } n \text { is odd. }
\end{array}\right.\]
Given a positive integer $k$ and other two integers $b > w > 1.$ There are two strings of pearls, a string of $b$ black pearls and a string of $w$ white pearls. The length of a string is the number of pearls on it. One cuts these strings in some steps by the following rules. In each step:
[b](i)[/b] The strings are ordered by their lengths in a non-increasing order. If there are some strings of equal lengths, then the white ones precede the black ones. Then $k$ first ones (if they consist of more than one pearl) are chosen; if there are less than $k$ strings longer than 1, then one chooses all of them.
[b](ii)[/b] Next, one cuts each chosen string into two parts differing in length by at most one. (For instance, if there are strings of $5, 4, 4, 2$ black pearls, strings of $8, 4, 3$ white pearls and $k = 4,$ then the strings of 8 white, 5 black, 4 white and 4 black pearls are cut into the parts $(4,4), (3,2), (2,2)$ and $(2,2)$ respectively.) The process stops immediately after the step when a first isolated white pearl appears.
Prove that at this stage, there will still exist a string of at least two black pearls.
[i]Proposed by Bill Sands, Thao Do, Canada[/i]
We will consider odd natural numbers $n$ such that$$n|2023^n-1$$
$\textbf{a.}$ Find the smallest two such numbers.
$\textbf{b.}$ Prove that there exists infinitely many such $n$
Let $n$ be a positive integer. Each cell of an $n \times n$ table is coloured in one of $k$ colours where every colour is used at least once. Two different colours $A$ and $B$ are said to touch each other, if there exists a cell coloured in $A$ sharing a side with a cell coloured in $B$. The table is coloured in such a way that each colour touches at most $2$ other colours. What is the maximal value of $k$ in terms of $n$?
For integer $a$, $a \neq 0$, $v_2(a)$ is greatest nonnegative integer $k$ such that $2^k | a$. For given $n \in \mathbb{N}$ determine highest possible cardinality of subset $A$ of set $ \{1,2,3,...,2^n \} $ with following property:
For all $x, y \in A$, $x \neq y$, number $v_2(x-y)$ is even.
The sequence $a_{n}$ is defined by $a_{1}\geq 2$ and the recurrence formula
\[a_{n+1}=a_{n}\sqrt{\frac{a_{n}^3+2}{2(a_{n}^3+1)}}\]
for $n\geq 1$. Prove that for every integer $n$, the inequality $a_{n}>\sqrt{\frac{3}{n}}$ holds.
A convex polygon is such that the distance between any two vertices does not exceed $ 1$.
$ (i)$ Prove that the distance between any two points on the boundary of the polygon does not exceed $ 1$.
$ (ii)$ If $ X$ and $ Y$ are two distinct points inside the polygon, prove that there exists a point $ Z$ on the boundary of the polygon such that $ XZ \plus{} YZ\le1$.
Let $ x_0 \equal{} 1$ and for $ n\ge0,$ let $ x_{n \plus{} 1} \equal{} 3x_n \plus{} \left\lfloor x_n\sqrt {5}\right\rfloor.$ In particular, $ x_1 \equal{} 5,\ x_2 \equal{} 26,\ x_3 \equal{} 136,\ x_4 \equal{} 712.$ Find a closed-form expression for $ x_{2007}.$ ($ \lfloor a\rfloor$ means the largest integer $ \le a.$)
The product of positive numbers $x, y$ and $z$ is equal to $1$. Prove that if it holds that
$$\frac1x +\frac1y + \frac1z \ge x + y + z,$$
then for any natural $k$, holds the inequality
$$\frac{1}{x^k} +\frac{1}{y^k} + \frac{1}{z^k} \ge x^k + y^k + z^k.$$
Let $ n > 1$ be an integer. Find all sequences $ a_1, a_2, \ldots a_{n^2 \plus{} n}$ satisfying the following conditions:
\[ \text{ (a) } a_i \in \left\{0,1\right\} \text{ for all } 1 \leq i \leq n^2 \plus{} n;
\]
\[ \text{ (b) } a_{i \plus{} 1} \plus{} a_{i \plus{} 2} \plus{} \ldots \plus{} a_{i \plus{} n} < a_{i \plus{} n \plus{} 1} \plus{} a_{i \plus{} n \plus{} 2} \plus{} \ldots \plus{} a_{i \plus{} 2n} \text{ for all } 0 \leq i \leq n^2 \minus{} n.
\]
[i]Author: Dusan Dukic, Serbia[/i]