Let $n> 2$ be an integer. A child has $n^2$ candies, which are distributed in $n$ boxes. An operation consists in choosing two boxes that together contain an even number of candies and redistribute the candy from those boxes so that both contain the same amount of candy. Determine all the values of $n$ for which the child, after some operations, can get each box containing $n$ candies, no matter which the initial distribution of candies is.
Problem
Source: Peru IMO TST 2016 p11
Tags: combinatorics
16.05.2019 04:42
The answer is all powers of $2$. Before proving this, let's define some notations. Call a configuration of some boxes immovable if the child has no valid move to make. We claim that an immovable configuration which isn't the one with $n$ in every box exists if and only if $n$ is not a power of two. First, we will show this claim for $n$ not a power of two. Let $n$ be any positive integer which isn't a power of two. Then, let $v_2(n) = k$. Consider the configuration where the boxes contain $1, 1, \cdots 1, \frac{n^2 - n + 2^k}{2^k}, \frac{n^2 - n+2^k}{2^k}, \cdots, \frac{n^2 - n + 2^k}{2^k}$ candies in the boxes, where there are $n-2^k$ $1$'s and $2^k$ $\frac{n^2-n+2^k}{2^k}$'s. This is an immovable configuration since $1$ is odd and $\frac{n^2 - n + 2^k}{2^k}$ is even. Notice that this shows that all non-powers of $2$ don't work, so it suffices only to show that the child can always do it for $n$ a power of $2$. Indeed, notice that the only way for a configuration to be immovable is if there are two distinct values of the number of candies over all the boxes, one of them odd and one of them even. Suppose that $n = 2^k$. Then, if there are $t$ of the odd number and $2^k - t$ of the even number, then since $v_2(t \cdot a + (2^k - t) \cdot b) = v_2(t)$ whenever $a$ is odd and $b$ is even, there are clearly no immovable configurations for evens. From here, the finish is clear. If we let $a_1, a_2, \cdots, a_n$ be variables which correspond to the number of candies in a box, it suffices only to note that the quantity $\sum (a_i - a_j)^2$ decreases with each one of the child's moves. This monovariant solves the problem, and so we're done.