Suppose you have identical coins distributed in several piles with one or more coins in each pile. An action consists of taking two piles, which have an even total of coins among them, and redistribute their coins in two piles so that they end up with the same number of coins. A distribution is levelable if it is possible, by means of 0 or more operations, to end up with all the piles having the same number of coins. Determine all positive integers $n$ such that, for all positive integers $k$, any distribution of $nk$ coins in $n$ piles is levelable.
Problem
Source: Centroamerican 2020, problem 2
Tags: combinatorics, Combinatorial games
29.10.2020 07:00
The answer is $n = 2^m$ for $m\geq 0$. First define a number $n$ to be leveler if for all positive integer $k$, any distribution of $nk$ coins in $n$ piles is levelable. We proceed by induction. It can be verified that $n = 1$ is leveler. Our hypothesis is that $2^{m}$ is leveler. We are going to prove that $2^{m+1}$ is leveler. Since $2^{m+1}\cdot k$ is even, there is an even quantity of piles with each parity of coins, so we can pair them to get two groups of $2^m$ piles with $2^m\cdot k$ coins, by our hypothesis, $2^m$ is leveler, and we get that $2^{m+1}$ is leveler by making each group having $k$ coins, no matter the configuration. To prove that $2^m\cdot i$ with $i\equiv 1 \mod 2$ and $m\geq 0$ is not leveler, take the following configuration: For $k = i$ we can have $2^m$ piles with $1$ coin and the others with $i+1$ coins. Since $i+1$ is even, it is evident that this configuration is not levelable since $1$ and $i+1$ have different parity, so $2^m \cdot i$ is not leveler.
30.10.2020 08:09
First we are going to prove that there are finitely many possible operations for any given $n$. For this let $a_1, a_2, \dots a_n$ be the amount of coins on each pile, and let us define $\sigma$ such that at first $\sigma_0 = \sum_{i=1}^{n} {(k-a_i)^2} \ge 0$. After applying an opperation to piles with $x$ and $y$ coins, $x \neq y$, we calculate $\sigma_1$ and notice that. \begin{align*} \sigma_1 - \sigma_0&=2\left(k-\dfrac{x+y}{2}\right)^2-((k-x)^2+(k-y)^2)\\ &=\dfrac{(x+y)^2}{2}-(x^2+y^2)<0 \end{align*} So $\sigma$ strictly decreases and cannot be less than $0$, thus there are finitely many moves, and we always have to hit a point where no more operations are available. Now let a final configuration be a distribution of $n$ piles that has no more operations available. We are going to prove that if $n=2^r$, then a final configuration of $n$ is leveled, for arbitrary $k$. Notice that a final configuration has to be either leveled, or be such that all piles with even number of coins have the same amount of coins, and all piles with odd number of coins have the same amount of coins. Now let us assume that for $n=2^r$ we reach a final configuration where we have $m$ piles with $0<m<2^r$, all of them with the same odd number of coins $2v+1$, and we have $2^r-m$ piles, all of them with the same even number of coins $2u$. So, \begin{align*} m(2v+1)+(2^r-m)2u&=2^rk\\ \iff m(2v-2u+1)+2^{r+1}u&=2^rk \end{align*} And since $2v-2u+1$ is odd, therefore $2^r \mid m$ wich yields a contradiction. So this concludes that for $n=2^r$ a final configuration must be leveled. To discard the non powers of $2$ just proceed as musan1909.
23.11.2022 05:24
We claim that only the powers of $2$ works. Lemma 1 $n$ odd doesn´t work Proof: Let $n=2u+1$, colocate $u$ piles with $k+u+1$ coins and $u+1$ piles with $k-u$ coins, since $k+u+1$ and $k-u$ have different parity we can´t even modify the number of coins in each pile by an action. Lemma 2 $n=2^v*j, j$ odd, doesn´t work Proof: Only take $2^v$ groups of piles using the same configuration as in Lemma 1 in every group. Lemma 3 $n=2^j$ works for every $j$ Proof: By induction, clearly $n=1$ works. $\blacksquare$ Case $n=2^j$ As the sum of the coins in every pile is an odd number there are an even number of piles with each parity of the number of coins, so we can level between the odd piles and the even and we obtain that are $2^{j-1}$ piles that have another pile with the same number of coins, and this case can be easy done by the case $n=2^{j-1}$, and we are done.