Given integer $n > 1$ and real number $t \geq 1$. $P$ is a parallelogram with four vertices $(0, 0), (0, t), (tF_{2n+1}, tF_{2n}), (tF_{2n+1}, tF_{2n} + t)$. Here, ${F_n}$ is the $n$-th term of Fibonacci sequence defined by $F_0 = 0, F_1 = 1$ and $F_{m+1} = F_m + F_{m-1}$. Let $L$ be the number of integral points (whose coordinates are integers) interior to $P$, and $M$ be the area of $P$, which is $t^2F_{2n+1}.$ [b][i]i)[/i][/b] Prove that for any integral point $(a, b)$, there exists a unique pair of integers $(j, k)$ such that$ j(F_{n+1}, F_n) + k(F_n, F_{n-1}) = (a, b)$, that is,$ jF_{n+1} + kF_n = a$ and $jF_n + kF_{n-1} = b.$ [i][b]ii)[/b][/i] Using [i][b]i)[/b][/i] or not, prove that $|\sqrt L-\sqrt M| \leq \sqrt 2.$

Let $(a_n)$ be a decreasing sequence of positive numbers with limit $0$ such that $$b_n = a_n -2 a_{n+1}+a_{n+2} \geq 0$$ for all $n.$ Prove that $$\sum_{n=1}^{\infty} n b_n =a_1.$$

Let the sequence $\{K_{n}\}_{n \ge 1}$ be defined by \[K_{1}=2, K_{2}=8, K_{n+2}=3K_{n+1}-K_{n}+5(-1)^{n}.\] Prove that if $K_{n}$ is prime, then $n$ must be a power of $3$.

Consider a grid of all lattice points $(m, n)$ with $m, n$ between $1$ and $125$. There exists a “path” between two lattice points $(m_1, n_1)$ and $(m_2, n_2)$ on the grid if $m_1n_1 = m_2n_2$ or if $m_1/n_1 = m_2/n_2$. For how many lattice points $(m, n)$ on the grid is there a sequence of paths that goes from $(1, 1)$ to $(m, n$)?

Initially the number $2000$ is written down. The following operation is repeatedly performed: the sum of the $10$-th powers of the last number's digits is written down. Prove that in the infinite sequence thus obtained, some two numbers will be equal.

Let $p > 3$ be a given prime number. For a set $S \subseteq \mathbb{Z}$ and $a \in \mathbb{N}$ , define $S_a = \{ x \in \{ 0,1, 2,...,p-1 \}$ | $(\exists_s \in S) x \equiv_p a \cdot s \}$ . $(a)$ How many sets $S \subseteq \{ 1, 2,...,p-1 \} $ are there for which the sequence $S_1 , S_2 , ..., S_{p-1}$ contains exactly two distinct terms? $(b)$ Determine all numbers $k \in \mathbb{N}$ for which there is a set $ S \subseteq \{ 1, 2,...,p-1 \} $ such that the sequence $S_1 , S_2 , ..., S_{p-1} $ contains exactly $k$ distinct terms. [i]Proposed by Milan Basic and Milos Milosavljevic[/i]

Let $A$ be a real number and $(a_{n})$ be a sequence of real numbers such that $a_{1}=1$ and \[1<\frac{a_{n+1}}{a_{n}}\leq A \mbox{ for all }n\in\mathbb{N}.\] $(a)$ Show that there is a unique non-decreasing surjective function $f: \mathbb{N}\rightarrow \mathbb{N}$ such that $1<A^{k(n)}/a_{n}\leq A$ for all $n\in \mathbb{N}$. $(b)$ If $k$ takes every value at most $m$ times, show that there is a real number $C>1$ such that $Aa_{n}\geq C^{n}$ for all $n\in \mathbb{N}$.

The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and \[\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k\] for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).

Let $k$ be an integer and define a sequence $a_0 , a_1 ,a_2 ,\ldots$ by $$ a_0 =0 , \;\; a_1 =k \;\;\text{and} \;\; a_{n+2} =k^{2}a_{n+1}-a_n \; \text{for} \; n\geq 0.$$ Prove that $a_{n+1} a_n +1$ divides $a_{n+1}^{2} +a_{n}^{2}$ for all $n$.

[u]Round 5[/u] [b]p13.[/b] In coordinate space, a lattice point is a point all of whose coordinates are integers. The lattice points $(x, y, z)$ in three-dimensional space satisfying $0 \le x, y, z \le 5$ are colored in n colors such that any two points that are $\sqrt3$ units apart have different colors. Determine the minimum possible value of $n$. [b]p14.[/b] Determine the number of ways to express $121$ as a sum of strictly increasing positive Fibonacci numbers. [b]p15.[/b] Let $ABCD$ be a rectangle with $AB = 7$ and $BC = 15$. Equilateral triangles $ABP$, $BCQ$, $CDR$, and $DAS$ are constructed outside the rectangle. Compute the area of quadrilateral $P QRS$. [u] Round 6[/u] Each of the three problems in this round depends on the answer to one of the other problems. There is only one set of correct answers to these problems; however, each problem will be scored independently, regardless of whether the answers to the other problems are correct. [b]p16.[/b] Let $C$ be the answer to problem $18$. Suppose that $x$ and $y$ are real numbers with $y > 0$ and $$x + y = C$$ $$x +\frac{1}{y} = -2.$$ Compute $y +\frac{1}{y}$. [b]p17.[/b] Let $A$ be the answer to problem $16$. Let $P QR$ be a triangle with $\angle P QR = 90^o$, and let $X$ be the foot of the perpendicular from point $Q$ to segment $P R$. Given that $QX = A$, determine the minimum possible area of triangle $PQR$. [b]p18.[/b] Let $B$ be the answer to problem $17$ and let $K = 36B$. Alice, Betty, and Charlize are identical triplets, only distinguishable by their hats. Every day, two of them decide to exchange hats. Given that they each have their own hat today, compute the probability that Alice will have her own hat in $K$ days. [u]Round 7[/u] [b]p19.[/b] Find the number of positive integers a such that all roots of $x^2 + ax + 100$ are real and the sum of their squares is at most $2013$. [b]p20.[/b] Determine all values of $k$ such that the system of equations $$y = x^2 - kx + 1$$ $$x = y^2 - ky + 1$$ has a real solution. [b]p21.[/b] Determine the minimum number of cuts needed to divide an $11 \times 5 \times 3$ block of chocolate into $1\times 1\times 1$ pieces. (When a block is broken into pieces, it is permitted to rotate some of the pieces, stack some of the pieces, and break any set of pieces along a vertical plane simultaneously.) [u]Round 8[/u] [b]p22.[/b] A sequence that contains the numbers $1, 2, 3, ... , n$ exactly once each is said to be a permutation of length $n$. A permutation $w_1w_2w_3... w_n$ is said to be sad if there are indices $i < j < k$ such that $w_j > w_k$ and $w_j > w_i$. For example, the permutation $3142756$ is sad because $7 > 6$ and $7 > 1$. Compute the number of permutations of length $11$ that are not sad. [b]p23.[/b] Let $ABC$ be a triangle with $AB = 39$, $BC = 56$, and $CA = 35$. Compute $\angle CAB - \angle ABC$ in degrees. [b]p24.[/b] On a strange planet, there are $n$ cities. Between any pair of cities, there can either be a one-way road, two one-way roads in different directions, or no road at all. Every city has a name, and at the source of every one-way road, there is a signpost with the name of the destination city. In addition, the one-way roads only intersect at cities, but there can be bridges to prevent intersections at non-cities. Fresh Mann has been abducted by one of the aliens, but Sophy Moore knows that he is in Rome, a city that has no roads leading out of it. Also, there is a direct one-way road leading from each other city to Rome. However, Rome is the secret police’s name for the so-described city; its official name, the name appearing on the labels of the one-way roads, is unknown to Sophy Moore. Sophy Moore is currently in Athens and she wants to head to Rome in order to rescue Fresh Mann, but she does not know the value of $n$. Assuming that she tries to minimize the number of roads on which she needs to travel, determine the maximum possible number of roads that she could be forced to travel in order to find Rome. Express your answer as a function of $n$. PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c4h2809419p24782489]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $ \, a_{0}, a_{1}, a_{2},\ldots\,$ be a sequence of positive real numbers satisfying $ \, a_{i\minus{}1}a_{i\plus{}1}\leq a_{i}^{2}\,$ for $ i \equal{} 1,2,3,\ldots\; .$ (Such a sequence is said to be [i]log concave[/i].) Show that for each $ \, n > 1,$ \[ \frac{a_{0}\plus{}\cdots\plus{}a_{n}}{n\plus{}1}\cdot\frac{a_{1}\plus{}\cdots\plus{}a_{n\minus{}1}}{n\minus{}1}\geq\frac{a_{0}\plus{}\cdots\plus{}a_{n\minus{}1}}{n}\cdot\frac{a_{1}\plus{}\cdots\plus{}a_{n}}{n}.\]

There are $n \ge 3$ positive integers written on a board. A [i]move[/i] consists of choosing three numbers $a, b, c$ written from the board such that there exists a non-degenerate non-equilateral triangle with sides $a, b, c$ and replacing those numbers with $a + b - c, b + c - a$ and $c + a - b$. Prove that a sequence of moves cannot be infinite.

Let $F_1$ be an arbitrary convex quadrilateral. For $k\ge2$, $F_k$ is obtained by cutting $F_{k-1}$ into two pieces along one of its diagonals, flipping one piece over, and the glueing them back together along the same diagonal. What is the maximum number of non-congruent quadrilaterals in the sequence $\{F_k\}$?

Let $X_1, X_2, \ldots$ be independent random variables of the same distribution such that their joint distribution is discrete and is concentrated on infinitely many different values. Let $a_n$ denote the probability that $X_1,\ldots, X_{n+1}$ are all different on the condition that $X_1,\ldots, X_n$ are all different ($n\ge 1$). Show that (a) $a_n$ is strictly decreasing and tends to $0$ as $n\to \infty$; and (b) for any sequence $1\le f(1)\le f(2) < \ldots$ of positive integers the joint distribution of $X_1, X_2, \ldots$ can be chosen such that $$\limsup_{n\to\infty}\frac{a_{f(n)}}{a_n}=1$$ holds.

Let $n$ be a given positive integer. Say that a set $K$ of points with integer coordinates in the plane is connected if for every pair of points $R, S\in K$, there exists a positive integer $\ell$ and a sequence $R=T_0,T_1, T_2,\ldots ,T_{\ell}=S$ of points in $K$, where each $T_i$ is distance $1$ away from $T_{i+1}$. For such a set $K$, we define the set of vectors \[\Delta(K)=\{\overrightarrow{RS}\mid R, S\in K\}\] What is the maximum value of $|\Delta(K)|$ over all connected sets $K$ of $2n+1$ points with integer coordinates in the plane? [i]Grigory Chelnokov, Russia[/i]