Let $\mathcal{S}$ be a set of $10$ points in a plane that lie within a disk of radius $1$ billion. Define a $move$ as picking a point $P \in \mathcal{S}$ and reflecting it across $\mathcal{S}$'s centroid. Does there always exist a sequence of at most $1500$ moves after which all points of $\mathcal{S}$ are contained in a disk of radius $10$? Advaith Avadhanam
Problem
Source: ELMO Shortlist 2024/C5
Tags: Elmo, combinatorics
Number1048576
24.06.2024 23:59
The answer is yes. For now, replace $10$ with $n$. To prove this, we use variance (!)
Let the points have co-ordinates $(x_i,y_i)$, and let $G = (G_x,G_y)$ be the centroid. Also, write $U_i = G_x - x_i$, $V_i = G_y - y_i$.
Consider the sum $S_k = \sum_i (x_i - G_x)^2 + (y_i - G_y)^2$ (in other words the "variance" of the points, here $k$ is the number of moves that have elapsed). The key claim is that we can pick $i$ to make this decrease by a large amount.
A move involves mapping $x_i \mapsto 2G_x - x_i$, $y_i \mapsto 2G_y - y_i$. Then, $G_x \mapsto G_x + \frac{2V_i}{n}$ and similarly for $G_y$.
Then by some calculation we can show that $S_{k+1} = S_k - (1 - (\frac{n-2}{n})^2)((U_i)^2 + (V_i)^2)$. The expected value of $(U_i)^2 + (V_i)^2$ across all $i$ is $\frac{S_k}{n}$ (this can be seen by summing $(U_i)^2 + (V_i)^2$ over all $i$). Hence, $E[S_{k+1}] = S_k(1 - (1 - (\frac{n-2}{n})^2)/n) = S_k(\frac{241}{250})$. Hence, by PHP we can choose $i$ so that $S_{k+1} \leq \frac{241}{250} \cdot S_k$. Note that the maximum possible value of $S_0$ for which the points can exist in a disk of radius $10^9$ is $20 \times (2 \times 10^{9})^2 = 8\times 10^{17}$, and the maximum possible value of $S_i$ for which the points must exist in a disk of radius $10$ is $100$. Hence, we can do it in $x$ moves, where $(\frac{250}{241})^x > 8\times 10^{15}$. However, by Bernoulli, $(\frac{250}{241})^{27} = (1 + \frac{9}{241})^{27} > 1 + \frac{243}{241} > 2$. Also, $2^{10} > 10^3 \implies 2^{53} > 8 \times 10^{15}$.
Also, $27 \times 53 = 1431 < 1500$. Hence, we are done.