CMO 2016

Let $a_1,a_2,\cdots, a_{31} ;b_1,b_2, \cdots, b_{31}$ be positive integers such that $a_1< a_2<\cdots< a_{31}\leq2015$ , $b_1< b_2<\cdots<b_{31}\leq2015$ and $a_1+a_2+\cdots+a_{31}=b_1+b_2+\cdots+b_{31}.$ Find the maximum value of $S=|a_1-b_1|+|a_2-b_2|+\cdots+|a_{31}-b_{31}|.$

In $\triangle AEF$ , let $B$ and $D$ be on segments $AE$ and $AF$ respectively, and let $ED$ and $FB$ intersect at $C$ . Define $K,L,M,N$ on segments $AB,BC,CD,DA$ such that $\frac{AK}{KB}=\frac{AD}{BC}$ and its cyclic equivalents. Let the incircle of $\triangle AEF$ touch $AE,AF$ at $S,T$ respectively; let the incircle of $\triangle CEF$ touch $CE,CF$ at $U,V$ respectively. Prove that $K,L,M,N$ concyclic implies $S,T,U,V$ concyclic.

Let $p$ be an odd prime and $a_1, a_2,...,a_p$ be integers. Prove that the following two conditions are equivalent:

1. There exists a polynomial $P(x)$ with degree $\leq \frac{p-1}{2}$ such that $P(i) \equiv a_i \pmod p$ for all $1 \leq i \leq p$ 2) For any natural $d \leq \frac{p-1}{2}$ , $$\sum_{i=1}^p (a_{i+d} - a_i )^2 \equiv 0 \pmod p$$ where indices are taken $\pmod p$

Let $n \geq 2$ be a positive integer and define $k$ to be the number of primes $\leq n$ . Let $A$ be a subset of $S = \{2,...,n\}$ such that $|A| \leq k$ and no two elements in $A$ divide each other. Show that one can find a set $B$ such that $|B| = k$ , $A \subseteq B \subseteq S$ and no two elements in $B$ divide each other.

Let $ABCD$ be a convex quadrilateral. Show that there exists a square $A'B'C'D'$ (Vertices maybe ordered clockwise or counter-clockwise) such that $A \not = A', B \not = B', C \not = C', D \not = D'$ and $AA',BB',CC',DD'$ are all concurrent.

Let $G$ be a complete directed graph with $100$ vertices such that for any two vertices $x,y$ one can find a directed path from $x$ to $y$ .

a) Show that for any such $G$ , one can find a $m$ such that for any two vertices $x,y$ one can find a directed path of length $m$ from $x$ to $y$ (Vertices can be repeated in the path)

b) For any graph $G$ with the properties above, define $m(G)$ to be smallest possible $m$ as defined in part a). Find the minimim value of $m(G)$ over all such possible $G$ 's.