Let $a$ be a positive real number and $\{x_n\}_{n\geq 1}$ a sequence of real numbers such that $x_1=a$ and \[ x_{n+1} \geq (n+2)x_n - \sum^{n-1}_{k=1}kx_k, \ \forall \ n\geq 1. \] Prove that there exists a positive integer $n$ such that $x_n > 1999!$. [i]Ciprian Manolescu[/i]

On the grid plane all possible broken lines with the following properties are constructed: each of them starts at the point $(0, 0)$, has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding [i]worm[/i], the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles $2\times 1$ and $1\times 2$) in exactly $n > 2$ different ways, is equal to the number of positive integers that are less than n and relatively prime to $n$. (Ilke Chanakchi, Ralf Schiffler)

Squares of an $n \times n$ table ($n \ge 3$) are painted black and white as in a chessboard. A move allows one to choose any $2 \times 2$ square and change all of its squares to the opposite color. Find all such n that there is a finite number of the moves described after which all squares are the same color.

[u]Round 9[/u] [b]p25.[/b] For how many nonempty subsets of $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\}$ is the sum of the elements divisble by $32$? [b]p26.[/b] America declared independence in $1776$. Take the sum of the cubes of the digits of $1776$ and let that equal $S_1$. Sum the cubes of the digits of $S_1$ to get $S_2$. Repeat this process $1776$ times. What is $S_{1776}$? [b]p27.[/b] Every Golden Grahams box contains a randomly colored toy car, which is one of four colors. What is the expected number of boxes you have to buy in order to obtain one car of each color? [u]Round 10[/u] [b]p28.[/b] Let $B$ be the answer to Question $29$ and $C$ be the answer to Question $30$. What is the sum of the square roots of $B$ and $C$? [b]p29.[/b] Let $A$ be the answer to Question $28$ and $C$ be the answer to Question $30$. What is the sum of the sums of the digits of $A$ and $C$? [b]p30.[/b] Let $A$ be the answer to Question $28$ and $B$ be the answer to Question $29$. What is $A + B$? [u]Round 11[/u] [b]p31.[/b] If $x + \frac{1}{x} = 4$, find $x^6 + \frac{1}{x^6}$. [b]p32.[/b] Given a positive integer $n$ and a prime $p$, there is are unique nonnegative integers $a$ and $b$ such that $n = p^b \cdot a$ and $gcd (a, p) = 1$. Let $v_p(n)$ denote this uniquely determined $a$. Let $S$ denote the set of the first 20 primes. Find $\sum_{ p \in S} v_p \left(1 + \sum^{100}_{i=0} p^i \right)$. [b]p33. [/b] Find the maximum value of n such that $n+ \sqrt{(n - 1) +\sqrt{(n - 2) + ... +\sqrt{1}}} < 49$ (Note: there would be $n - 1$ square roots and $n$ total terms). [u]Round 12[/u] [b]p34.[/b] Give two numbers $a$ and $b$ such that $2015^a < 2015! < 2015^b$. If you are incorrect you get $-5$ points; if you do not answer you get $0$ points; otherwise you get $\max \{20-0.02(|b - a| - 1), 0\}$ points, rounded down to the nearest integer. [b]p35.[/b] Twin primes are prime numbers whose difference is $2$. Let $(a, b)$ be the $91717$-th pair of twin primes, with $a < b$. Let $k = a^b$, and suppose that $j$ is the number of digits in the base $10$ representation of $k$. What is $j^5$? If the correct answer is $n$ and you say $m$, you will receive $\max \left(20 - | \log \left(| \frac{m}{n} |\right), 0 \right)$ points, rounded down to the nearest integer. [b]p36.[/b] Write down any positive integer. Let the sum of the valid submissions (i.e. positive integer submissions) for all teams be $S$. One team will be chosen randomly, according to the following distribution: if your team's submission is $n$, you will be chosen with probability $\frac{n}{S}$ . The amount of points that the chosen team will win is the greatest integer not exceeding $\min \{K, \frac{ 10000}{S} \}$. $K$ is a predetermined secret value. PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c3h3157009p28696627]here [/url] and 5-8 [url=https://artofproblemsolving.com/community/c3h3157013p28696685]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $k > 1$ be a fixed odd number, and for non-negative integers $n$ let $$f_n=\sum_{\substack{0\leq i\leq n\\ k\mid n-2i}}\binom{n}{i}.$$ Prove that $f_n$ satisfy the following recursion: $$f_{n}^2=\sum_{i=0}^{n} \binom{n}{i}f_{i}f_{n-i}.$$

Let $ 0 < x_{1}\leq\frac {x_{2}}{2}\leq\cdots\leq\frac {x_{n}}{n}, 0 < y_{n}\leq y_{n \minus{} 1}\leq\cdots\leq y_{1},$ Prove that $ (\sum_{k \equal{} 1}^{n}x_{k}y_{k})^2\leq(\sum_{k \equal{} 1}^{n}y_{k})(\sum_{k \equal{} 1}^{n}(x_{k}^2 \minus{} \frac {1}{4}x_{k}x_{k \minus{} 1})y_{k}).$ where $ x_{0} \equal{} 0.$

A polynomial is [i]good[/i] if it has integer coefficients, it is monic, all its roots are distinct, and there exists a disk with radius $0.99$ on the complex plane that contains all the roots. Prove that there is no [i]good[/i] polynomial for a sufficient large degree. [i]Proposed by Rodrigo Sanches Angelo (rsa365), Brazil.[/i]

Given real numbers $ x_1 < x_2 < \ldots < x_n$ such that every real number occurs at most two times among the differences $ x_j \minus{} x_i$, $ 1\leq i < j \leq n$, prove that there exists at least $ \lfloor n/2\rfloor$ real numbers that occurs exactly one time among such differences.

For each prime $p$, construct a graph $G_p$ on $\{1,2,\ldots p\}$, where $m\neq n$ are adjacent if and only if $p$ divides $(m^{2} + 1-n)(n^{2} + 1-m)$. Prove that $G_p$ is disconnected for infinitely many $p$

Let $n$ be a positive integer and let $a_1\le a_2 \le \dots \le a_n$ be real numbers such that \[a_1+2a_2+\dots+na_n=0.\] Prove that \[a_1[x]+a_2[2x]+\dots+a_n[nx] \ge 0\] for every real number $x$. (Here $[t]$ denotes the integer satisfying $[t] \le t<[t]+1$.)

Let $m$ and $n$ be positive integers integers such that $2m + 1 < n$, and let $S$ be the set of the $2^n$ subsets of $\{1,2,\ldots,n\}$. Prove that we can place the elements of $S$ on a circle, so that for any two adjacent elements $A$ and $B$, the set $A \Delta B$ has exactly $2m + 1$ elements. [b]Note[/b]: $A \Delta B = (A \cup B) - (A \cap B)$ is the set of elements that are exclusively in $A$ or exclusively in $B$.

A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for every initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off. [i]Proposed by Australia[/i]

A function $f$ from the set of positive real numbers to itself satisfies $$f(x + f(y) + xy) = xf(y) + f(x + y)$$ for all positive real numbers $x$ and $y$. Prove that $f(x) = x$ for all positive real numbers $x$.

Let $ n, k \in \mathbb{N}$ with $ 1 \leq k \leq \frac {n}{2} - 1.$ There are $ n$ points given on a circle. Arbitrarily we select $ nk + 1$ chords among the points on the circle. Prove that of these chords there are at least $ k + 1$ chords which pairwise do not have a point in common.

Let $\mathbb{R}^+$ be the set of positive real numbers. Find all functions $f \colon \mathbb{R}^+ \to \mathbb{R}^+$ such that, for all $x,y \in \mathbb{R}^+$, $$f(xy+f(x))=xf(y)+2.$$