Let $f$ and $g$ be two nonzero polynomials with integer coefficients and $\operatorname{deg} f\gt \operatorname{deg} g$. Suppose that for infinitely many primes $p$ the polynomial $p f+g$ has a rational root. Prove that $f$ has a rational root.
Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function, and let $f^{m}$ be $f$ applied $m$ times. Suppose that for every $n \in \mathbb{N}$ there exists a $k \in \mathbb{N}$ such that $f^{2 k}(n)=n+k$, and let $k_{n}$ be the smallest such $k$. Prove that the sequence $k_{1}, k_{2}, \ldots$ is unbounded.
We say that a function $f: \mathbb{R}^{k} \rightarrow \mathbb{R}$ is a metapolynomial if, for some positive integers $m$ and $n$, it can be represented in the form
Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers $x$ and $y$ such that $x\gt y$ and $x$ is to the left of $y$, and replaces the pair $(x, y)$ by either $(y+1, x)$ or $(x-1, x)$. Prove that she can perform only finitely many such iterations.
Let $n \geq 1$ be an integer. What is the maximum number of disjoint pairs of elements of the set $\{1,2, \ldots, n\}$ such that the sums of the different pairs are different integers not exceeding $n$ ?
In a $999 \times 999$ square table some cells are white and the remaining ones are red. Let $T$ be the number of triples $\left(C_{1}, C_{2}, C_{3}\right)$ of cells, the first two in the same row and the last two in the same column, with $C_{1}$ and $C_{3}$ white and $C_{2}$ red. Find the maximum value $T$ can attain.
Players $A$ and $B$ play a game with $N \geq 2012$ coins and 2012 boxes arranged around a circle. Initially $A$ distributes the coins among the boxes so that there is at least 1 coin in each box. Then the two of them make moves in the order $B, A, B, A, \ldots$ by the following rules:
- On every move of his $B$ passes 1 coin from every box to an adjacent box.
- On every move of hers $A$ chooses several coins that were not involved in $B$ 's previous move and are in different boxes. She passes every chosen coin to an adjacent box.
Player $A$ 's goal is to ensure at least 1 coin in each box after every move of hers, regardless of how $B$ plays and how many moves are made. Find the least $N$ that enables her to succeed.
The columns and the rows of a $3 n \times 3 n$ square board are numbered $1,2, \ldots, 3 n$. Every square $(x, y)$ with $1 \leq x, y \leq 3 n$ is colored asparagus, byzantium or citrine according as the modulo 3 remainder of $x+y$ is 0 , 1 or 2 respectively. One token colored asparagus, byzantium or citrine is placed on each square, so that there are $3 n^{2}$ tokens of each color.
Suppose that one can permute the tokens so that each token is moved to a distance of at most $d$ from its original position, each asparagus token replaces a byzantium token, each byzantium token replaces a citrine token, and each citrine token replaces an asparagus token. Prove that it is possible to permute the tokens so that each token is moved to a distance of at most $d+2$ from its original position, and each square contains a token with the same color as the square.
Let $k$ and $n$ be fixed positive integers. In the liar's guessing game, Amy chooses integers $x$ and $N$ with $1 \leq x \leq N$. She tells Ben what $N$ is, but not what $x$ is. Ben may then repeatedly ask Amy whether $x \in S$ for arbitrary sets $S$ of integers. Amy will always answer with yes or no, but she might lie. The only restriction is that she can lie at most $k$ times in a row. After he has asked as many questions as he wants, Ben must specify a set of at most $n$ positive integers. If $x$ is in this set he wins; otherwise, he loses. Prove that:
a) If $n \geq 2^{k}$ then Ben can always win.
b) For sufficiently large $k$ there exist $n \geq 1.99^{k}$ such that Ben cannot guarantee a win.
There are given $2^{500}$ points on a circle labeled $1,2, \ldots, 2^{500}$ in some order. Prove that one can choose 100 pairwise disjoint chords joining some of these points so that the 100 sums of the pairs of numbers at the endpoints of the chosen chords are equal.
In the triangle $A B C$ the point $J$ is the center of the excircle opposite to $A$. This excircle is tangent to the side $B C$ at $M$, and to the lines $A B$ and $A C$ at $K$ and $L$ respectively. The lines $L M$ and $B J$ meet at $F$, and the lines $K M$ and $C J$ meet at $G$. Let $S$ be the point of intersection of the lines $A F$ and $B C$, and let $T$ be the point of intersection of the lines $A G$ and $B C$. Prove that $M$ is the midpoint of $S T$.
Let $A B C D$ be a cyclic quadrilateral whose diagonals $A C$ and $B D$ meet at $E$. The extensions of the sides $A D$ and $B C$ beyond $A$ and $B$ meet at $F$. Let $G$ be the point such that $E C G D$ is a parallelogram, and let $H$ be the image of $E$ under reflection in $A D$. Prove that $D, H, F, G$ are concyclic.
In an acute triangle $A B C$ the points $D, E$ and $F$ are the feet of the altitudes through $A$, $B$ and $C$ respectively. The incenters of the triangles $A E F$ and $B D F$ are $I_{1}$ and $I_{2}$ respectively; the circumcenters of the triangles $A C I_{1}$ and $B C I_{2}$ are $O_{1}$ and $O_{2}$ respectively. Prove that $I_{1} I_{2}$ and $O_{1} O_{2}$ are parallel.
Let $A B C$ be a triangle with $A B \neq A C$ and circumcenter $O$. The bisector of $\angle B A C$ intersects $B C$ at $D$. Let $E$ be the reflection of $D$ with respect to the midpoint of $B C$. The lines through $D$ and $E$ perpendicular to $B C$ intersect the lines $A O$ and $A D$ at $X$ and $Y$ respectively. Prove that the quadrilateral $B X C Y$ is cyclic.
Let $A B C$ be a triangle with $\angle B C A=90^{\circ}$, and let $C_{0}$ be the foot of the altitude from $C$. Choose a point $X$ in the interior of the segment $C C_{0}$, and let $K, L$ be the points on the segments $A X, B X$ for which $B K=B C$ and $A L=A C$ respectively. Denote by $M$ the intersection of $A L$ and $B K$. Show that $M K=M L$.
Let $A B C$ be a triangle with circumcenter $O$ and incenter $I$. The points $D, E$ and $F$ on the sides $B C, C A$ and $A B$ respectively are such that $B D+B F=C A$ and $C D+C E=A B$. The circumcircles of the triangles $B F D$ and $C D E$ intersect at $P \neq D$. Prove that $O P=O I$.