# Day 1 ## Problem 1 Let $n \geqslant 100$ be an integer. Ivan writes the numbers $n, n+1, \ldots, 2 n$ each on different cards. He then shuffles these $n+1$ cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square. ## Problem 2 Show that the inequality $ \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}-x_{j}\right|} \leqslant \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}+x_{j}\right|} $ holds for all real numbers $x_1, \ldots , x_n$. ### Solution #### Shift to hypothetical minimum For any given list $(x_1, \ldots , x_n)$ there are other *shifted* lists $(x_1+c, \ldots , x_n+c)$ which add a $c\in\mathbb{R}$ to each element of the list. This *preserves relative differences*, so the LHS of the inequality for all of these shifted lists is equivalent. The RHS varies with $c$ $ \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}-x_{j}\right|} \leqslant \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}+x_{j}+2c\right|} $ Minimizing the RHS finds the list closest to "breaking" the inequality #### After shifting, there must be opposites Let $c$ be the constant that minimizes the RHS. There is a $k, l$ such that $(x_{k}+c)+(x_{l}+c)=0$ (Note $k$ and $l$ can be equal, meaning, it is possible there is not opposite *pair* after shifting, but rather a single element equal to 0) ##### Proof by contradiction Assume $x_{i}+x_{j} \neq 0$ for all $i, j$ There is a small enough $\epsilon>0$ such that the following are the same sign, regardless of choices for $i, j$ $ x_{i}+x_{j}-2 \epsilon, \quad x_{i}+x_{j}, \quad x_{i}+x_{j}+2 \epsilon $ Since the function $f(x)=\sqrt{(\vert x\vert)}$ is concave down over any continuous interval that does not contain zero, [[Jensen's inequality]] applies to our numbers $x_{i}+x_{j}\pm2 \epsilon$, which have the same sign. $\sqrt{\left|x_{i}+x_{j}-2 \epsilon\right|}+\sqrt{\left|x_{i}+x_{j}+2 \epsilon\right|}<2 \sqrt{\left|x_{i}+x_{j}\right|}$ Taking the double sum of both sides $ \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}+x_{j}-2 \epsilon\right|}+\sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}+x_{j}+2 \epsilon\right|}<2 \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}+x_{j}\right|} $ So one of the double sums on the right should be less than one of (excluding the coefficient) the double sum on the right. In the case that $x_i+x_j$ and its neighbors were positive, $ \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}+x_{j}-2 \epsilon\right|}\leq\sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}+x_{j}\right|} $ So either $\epsilon$ or its opposite is the ideal constant to minimize the (already minimized by shifting) sum on the RHS. There is no non-zero epsilon after all, so there must be at least one sum equal to zero: $x_{k}+x_{l} = 0$ #### Case 1: A zero element is present Let $x_k=0$. Any terms that include this in their sum on the RHS will be equivalent to any terms that include this in the difference $\sqrt{\vert x_i-0\vert}=\sqrt{\vert x_i+0\vert}$ So this zero element does not sway the inequality at all, and so the zero can be removed. The new list can then be reconsidered until there are no more zero elements, leading then to Case 2 #### Case 2: Non-zero additive inverses There exists $k \neq l$ such that $x_{k}=-x_{l}$ For each term including either $x_k$ or $x_l$, there is an equivalent term on the other side $\sqrt{\vert x_i-x_k\vert}=\sqrt{\vert x_i+x_l\vert}$ $\sqrt{\vert x_i-x_l\vert}=\sqrt{\vert x_i+x_k\vert}$ $\sqrt{\vert x_k-x_j\vert}=\sqrt{\vert x_l+x_j\vert}$ $\sqrt{\vert x_l-x_j\vert}=\sqrt{\vert x_k+x_j\vert}$ So, these terms do not sway the inequality, and the opposites can be removed, and the same shifting, reducing process can be applied. This can be repeated until there are no more terms, and the inequality is obviously true for $n=0$ since $0=0$ ## Problem 3 Let $D$ be an interior point of the acute triangle $A B C$ with $A B>A C$ so that $\angle D A B=$ $\angle C A D$. The point $E$ on the segment $A C$ satisfies $\angle A D E=\angle B C D$, the point $F$ on the segment $A B$ satisfies $\angle F D A=\angle D B C$, and the point $X$ on the line $A C$ satisfies $C X=B X$. Let $O_{1}$ and $O_{2}$ be the circumcentres of the triangles $A D C$ and $E X D$, respectively. Prove that the lines $B C, E F$, and $O_{1} O_{2}$ are concurrent.