Found problems: 766
Consider the sequence defined recursively by $(x_1,y_1)=(0,0)$,
$(x_{n+1},y_{n+1})=\left(\left(1-\frac{2}{n}\right)x_n-\frac{1}{n}y_n+\frac{4}{n},\left(1-\frac{1}{n}\right)y_n-\frac{1}{n}x_n+\frac{3}{n}\right)$.
Find $\lim_{n\to \infty}(x_n,y_n)$.
(a) Find the numbers $a_0,. . . , a_{100}$, such that $a_0 = 0, a_{100} = 1$ and for all $k = 1,. . . , 99$ :
$$a_k = \frac12 a_{k- 1} + \frac12 a_{k+1 }$$
(b) Find the numbers $a_0,. . . , a_{100}$, such that $a_0 = 0, a_{100} = 1$ and for all $k = 1,. . . , 99$ :
$$a_k = 1+\frac12 a_{k- 1} + \frac12 a_{k+1 }$$.
Each of the integers from $1$ to $n$ is written on a separate card, and then the cards are combined into a deck and shuffled. Three players, $A,B,$ and $C,$ take turns in the order $A,B,C,A,\dots$ choosing one card at random from the deck. (Each card in the deck is equally likely to be chosen.) After a card is chosen, that card and all higher-numbered cards are removed from the deck, and the remaining cards are reshuffled before the next turn. Play continues until one of the three players wins the game by drawing the card numbered $1.$
Show that for each of the three players, there are arbitrarily large values of $n$ for which that player has the highest probability among the three players of winning the game.
Define the function $f:(0,1)\to (0,1)$ by \[\displaystyle f(x) = \left\{ \begin{array}{lr} x+\frac 12 & \text{if}\ \ x < \frac 12\\ x^2 & \text{if}\ \ x \ge \frac 12 \end{array} \right.\] Let $a$ and $b$ be two real numbers such that $0 < a < b < 1$. We define the sequences $a_n$ and $b_n$ by $a_0 = a, b_0 = b$, and $a_n = f( a_{n -1})$, $b_n = f (b_{n -1} )$ for $n > 0$. Show that there exists a positive integer $n$ such that \[(a_n - a_{n-1})(b_n-b_{n-1})<0.\]
[i]Proposed by Denmark[/i]
The sequence $\{a_{n}\}_{n \ge 1}$ is defined by \[a_{1}=1, \; a_{n+1}=2a_{n}+\sqrt{3a_{n}^{2}+1}.\] Show that $a_{n}$ is an integer for every $n$.
Prove that there exist infinitely many integers $n$ such that $n$, $n+1$, $n+2$ are each the sum of the squares of two integers. [Example: $0=0^2+0^2$, $1=0^2+1^2$, $2=1^2+1^2$.]
Given real numbers $x_i \ (i = 1, 2, \cdots, 4k + 2)$ such that
\[\sum_{i=1}^{4k +2} (-1)^{i+1} x_ix_{i+1} = 4m \qquad ( \ x_1=x_{4k+3} \ )\]
prove that it is possible to choose numbers $x_{k_{1}}, \cdots, x_{k_{6}}$ such that
\[\sum_{i=1}^{6} (-1)^{i} k_i k_{i+1} > m \qquad ( \ x_{k_{1}} = x_{k_{7}} \ )\]
A $1 \times n$ rectangle ($n \geq 1 $) is divided into $n$ unit ($1 \times 1$) squares. Each square of this rectangle is colored red, blue or green. Let $f(n)$ be the number of colourings of the rectangle in which there are an even number of red squares. What is the largest prime factor of $f(9)/f(3)$? (The number of red squares can be zero.)
Let $n$ be a positive integer and let $\alpha_n $ be the number of $1$'s within binary representation of $n$.
Show that for all positive integers $r$,
\[2^{2n-\alpha_n}\phantom{-1} \bigg|^{\phantom{0}}_{\phantom{-1}} \sum_{k=-n}^{n} \binom{2n}{n+k} k^{2r}.\]
Let $\{a_{n}\}_{n \ge 1}$ be a sequence of positive integers such that \[0 < a_{n+1}-a_{n}\le 2001 \;\; \text{for all}\;\; n \in \mathbb{N}.\] Show that there are infinitely many pairs $(p, q)$ of positive integers such that $p>q$ and $a_{q}\; \vert \; a_{p}$.
For how many three-element sets of positive integers $\{a,b,c\}$ is it true that $a \times b \times c = 2310$?
$\textbf{(A)}\ 32 \qquad
\textbf{(B)}\ 36 \qquad
\textbf{(C)}\ 40 \qquad
\textbf{(D)}\ 43 \qquad
\textbf{(E)}\ 45$
There are $n$ students standing in a circle, one behind the other. The students have heights $h_1<h_2<\dots <h_n$. If a student with height $h_k$ is standing directly behind a student with height $h_{k-2}$ or less, the two students are permitted to switch places. Prove that it is not possible to make more than $\binom{n}{3}$ such switches before reaching a position in which no further switches are possible.
If a $5 \times n$ rectangle can be tiled using $n$ pieces like those shown in the diagram, prove that $n$ is even. Show that there are more than $2 \cdot 3^{k-1}$ ways to file a fixed $5 \times 2k$ rectangle $(k \geq 3)$ with $2k$ pieces. (symmetric constructions are supposed to be different.)
Let $ a, b \in \mathbb{N}$ with $ 1 \leq a \leq b,$ and $ M \equal{} \left[\frac {a \plus{} b}{2} \right].$ Define a function $ f: \mathbb{Z} \mapsto \mathbb{Z}$ by
\[ f(n) \equal{} \begin{cases} n \plus{} a, & \text{if } n \leq M, \\
n \minus{} b, & \text{if } n >M. \end{cases}
\]
Let $ f^1(n) \equal{} f(n),$ $ f_{i \plus{} 1}(n) \equal{} f(f^i(n)),$ $ i \equal{} 1, 2, \ldots$ Find the smallest natural number $ k$ such that $ f^k(0) \equal{} 0.$
Let $$x_0 = 5\,\, ,\, \,\,x_{n+1} = x_n +\frac{1}{x_n}.$$
Prove that $45 < x_{1000} < 45.1$.
A sequence ($a_n$) satisfies the following conditions:
(i) For each $m \in N$ it holds that $a_{2^m} = 1/m$.
(ii) For each natural $n \ge 2$ it holds that $a_{2n-1}a_{2n} = a_n$.
(iii) For all integers $m,n$ with $2m > n \ge 1$ it holds that $a_{2n}a_{2n+1} = a_{2^m+n}$.
Determine $a_{2000}$. You may assume that such a sequence exists.
Show that $\lceil (\sqrt{3}+1)^{2n})\rceil$ is divisible by $2^{n+1}.$
Find all one-to-one mappings $f:\mathbb{N}\to\mathbb{N}$ such that for all positive integers $n$ the following relation holds:
\[ f(f(n)) \leq \frac {n+f(n)} 2 . \]
Given that ${a_n}$ and ${b_n}$ are two sequences of integers defined by
\begin{align*}
a_1=1, a_2=10, a_{n+1}=2a_n+3a_{n-1} & ~~~\text{for }n=2,3,4,\ldots, \\
b_1=1, b_2=8, b_{n+1}=3b_n+4b_{n-1} & ~~~\text{for }n=2,3,4,\ldots.
\end{align*}
Prove that, besides the number $1$, no two numbers in the sequences are identical.
For a positive integer $x$, define a sequence $a_0, a_1, a_2, . . .$ according to the following rules:
$a_0 = 1$, $a_1 = x + 1$ and $$a_{n+2} = xa_{n+1} - a_n$$ for all $n \ge 0$.
Prove that there exist infinitely many positive integers x such that this sequence does not contain a prime number.
For $n \geq 3$ find the eigenvalues (with their multiplicities) of the $n \times n$ matrix
$$\begin{bmatrix}
1 & 0 & 1 & 0 & 0 & 0 & \dots & \dots & 0 & 0\\
0 & 2 & 0 & 1 & 0 & 0 & \dots & \dots & 0 & 0\\
1 & 0 & 2 & 0 & 1 & 0 & \dots & \dots & 0 & 0\\
0 & 1 & 0 & 2 & 0 & 1 & \dots & \dots & 0 & 0\\
0 & 0 & 1 & 0 & 2 & 0 & \dots & \dots & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 2 & \dots & \dots & 0 & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & & \vdots & \vdots\\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \ddots & \vdots & \vdots\\
0 & 0 & 0 & 0 & 0 & 0 & \dots & \dots & 2 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & \dots & \dots & 0 & 1
\end{bmatrix}$$
Let $ k$ and $ s$ be positive integers. For sets of real numbers $ \{\alpha_1, \alpha_2, \ldots , \alpha_s\}$ and $ \{\beta_1, \beta_2, \ldots, \beta_s\}$ that satisfy
\[ \sum^s_{i\equal{}1} \alpha^j_i \equal{} \sum^s_{i\equal{}1} \beta^j_i \quad \forall j \equal{} \{1,2 \ldots, k\}\]
we write \[ \{\alpha_1, \alpha_2, \ldots , \alpha_s\} \overset{k}{\equal{}} \{\beta_1, \beta_2, \ldots , \beta_s\}.\]
Prove that if \[ \{\alpha_1, \alpha_2, \ldots , \alpha_s\} \overset{k}{\equal{}} \{\beta_1, \beta_2, \ldots , \beta_s\}\] and $ s \leq k,$ then there exists a permutation $ \pi$ of $ \{1, 2, \ldots , s\}$ such that
\[ \beta_i \equal{} \alpha_{\pi(i)} \quad \forall i \equal{} 1,2, \ldots, s.\]
The sequence $ \{x_{n}\}_{n \ge 1}$ is defined by
\[ x_{1} \equal{} 2, x_{n \plus{} 1} \equal{} \frac {2 \plus{} x_{n}}{1 \minus{} 2x_{n}}\;\; (n \in \mathbb{N}).
\] Prove that
a) $ x_{n}\not \equal{} 0$ for all $ n \in \mathbb{N}$,
b) $ \{x_{n}\}_{n \ge 1}$ is not periodic.
There are four basketball players $A,B,C,D$. Initially the ball is with $A$. The ball is always passed from one person to a different person.
In how many ways can the ball come back to $A$ after $\textbf{seven}$ moves? (for example $A\rightarrow C\rightarrow B\rightarrow D\rightarrow A\rightarrow B\rightarrow C\rightarrow A$, or $A\rightarrow D\rightarrow A\rightarrow D\rightarrow C\rightarrow A\rightarrow B\rightarrow A)$.
Let $ n \geq 2$ be a positive integer and $ \lambda$ a positive real number. Initially there are $ n$ fleas on a horizontal line, not all at the same point. We define a move as choosing two fleas at some points $ A$ and $ B$, with $ A$ to the left of $ B$, and letting the flea from $ A$ jump over the flea from $ B$ to the point $ C$ so that $ \frac {BC}{AB} \equal{} \lambda$.
Determine all values of $ \lambda$ such that, for any point $ M$ on the line and for any initial position of the $ n$ fleas, there exists a sequence of moves that will take them all to the position right of $ M$.