EGMO 2016

Let $n$ be an odd positive integer, and let $x_{1}, x_{2}, \ldots, x_{n}$ be non-negative real numbers. Show that

$$\min _{i=1, \ldots, n}\left(x_{i}^{2}+x_{i+1}^{2}\right) \leq \max _{j=1, \ldots, n}\left(2 x_{j} x_{j+1}\right)$$

where $x_{n+1}=x_{1}$.

Let $A B C D$ be a cyclic quadrilateral, and let diagonals $A C$ and $B D$ intersect at $X$. Let $C_{1}, D_{1}$ and $M$ be the midpoints of segments $C X$, $D X$ and $C D$, respectively. Lines $A D_{1}$ and $B C_{1}$ intersect at $Y$, and line $M Y$ intersects diagonals $A C$ and $B D$ at different points $E$ and $F$, respectively. Prove that line $X Y$ is tangent to the circle through $E, F$ and $X$.

Let $m$ be a positive integer. Consider a $4 m \times 4 m$ array of square unit cells. Two different cells are related to each other if they are in either the same row or in the same column. No cell is related to itself. Some cells are coloured blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.

Two circles, $\omega_{1}$ and $\omega_{2}$, of equal radius intersect at different points $X_{1}$ and $X_{2}$. Consider a circle $\omega$ externally tangent to $\omega_{1}$ at a point $T_{1}$, and internally tangent to $\omega_{2}$ at a point $T_{2}$. Prove that lines $X_{1} T_{1}$ and $X_{2} T_{2}$ intersect at a point lying on $\omega$.

Let $k$ and $n$ be integers such that $k \geq 2$ and $k \leq n \leq 2 k-1$. Place rectangular tiles, each of size $1 \times k$ or $k \times 1$, on an $n \times n$ chessboard so that each tile covers exactly $k$ cells, and no two tiles overlap. Do this until no further tile can be placed in this way. For each such $k$ and $n$, determine the minimum number of tiles that such an arrangement may contain.

Let $S$ be the set of all positive integers $n$ such that $n^{4}$ has a divisor in the range $n^{2}+1, n^{2}+2, \ldots, n^{2}+2 n$. Prove that there are infinitely many elements of $S$ of each of the forms $7 m, 7 m+1,7 m+2,7 m+5,7 m+6$ and no elements of $S$ of the form $7 m+3$ or $7 m+4$, where $m$ is an integer.