Exercise 6. Let $n \geqslant 1$ be an integer. Morgane initially has $n$ piles, each containing one coin. She then allows herself operations of the following form: she chooses two piles, takes as many coins from the first pile as from the second, and forms a new pile with the coins she has taken.

Determine, as a function of $n$, the smallest number of non-empty piles that Morgane can obtain from such operations.
Solution to Exercise 6 If $n$ is a power of 2, Morgane can manage to end up with only one pile by proceeding as follows: she merges the $n$ piles of size 1 into $n / 2$ piles of size 2, then merges these $n / 2$ piles into $n / 4$ piles of size 4, and so on.

Conversely, when Morgane extracts $k$ pieces from two piles originally containing $a$ and $b$ pieces to form three piles (possibly empty) of $a-k, b-k$, and $2k$ pieces, we observe that $\operatorname{PGCD}(a-k, b-k, 2k)$ divides $2a$ and $2b$, and thus divides $2 \operatorname{PGCD}(a, b)$. Consequently, an immediate induction shows that if Morgane has $k$ piles of sizes $t_{1}, t_{2}, \ldots, t_{k}$, the number $\operatorname{PGCD}(t_{1}, t_{2}, \ldots, t_{k})$ is a power of 2. In particular, if Morgane manages to have only one pile, which will contain $n$ pieces, then $n$ must be a power of 2.

Finally, here is how, for any value of $n$, Morgane can proceed to end up with only two piles. She writes $n$ as a sum of increasing powers of 2, that is, numbers $2^{a_{1}} < 2^{a_{2}} < \cdots < 2^{a_{k}}$ such that $n = 2^{a_{1}} + 2^{a_{2}} + \cdots + 2^{a_{k}}$. For each $i \leq k$, and proceeding as in the case where $n$ is a power of 2, Morgane groups $2^{a_{i}}$ of her pieces into a single pile, thus obtaining $k$ piles.

Morgane then distinguishes her pile of size $2^{a_{1}}$, which she calls the target, and her pile of size $2^{a_{k}}$, which she calls the reserve. The $k-2$ other piles are seen as normal piles. Then Morgane sets out to double the size of her target pile while ensuring it will never be larger than a normal pile, proceeding as follows:

$\triangleright$ if the target pile is the same size as a normal pile, Morgane merges these two piles into a new target pile; a normal pile disappears during this operation;

$\triangleright$ otherwise, the target pile is of size $2^{a}$ strictly smaller than each normal pile, and Morgane then extracts $2^{a}$ pieces from the reserve to integrate them into the target pile, which is now of size $2^{a+1}$.

After $\ell$ such steps, the target pile is now of size $2^{a_{1}+\ell}$, and it has absorbed the piles of sizes $2^{a_{i}} < 2^{a_{1}+\ell}$, as well as at most $2^{a_{k-1}}$ pieces from the reserve, which is therefore still not empty. Thus, after $a_{k-1}+1-a_{1}$ steps, the target pile is now of size $2^{a_{k-1}+1}$, and it has absorbed all the normal piles, which means that there are now only two piles.

In conclusion, the minimum number of piles Morgane can end up with is 1 if $n$ is a power of 2, and it is 2 otherwise.

Graders' Comments The exercise was of progressive difficulty. Like many combinatorial exercises, it rewarded students who tested small cases. Indeed, by testing small cases, such as 2 and 4, one sees that if $n$ is a power of 2, then one can form a single pile. By continuing with small cases such as 3, 5, and 6, one sees that if $n$ is a sum of $k$ powers of 2, then one can form $k$ piles. But $k$ is not necessarily the minimum: for 7, one can obtain a pile of 4, one of 2, and one of 1; then one can obtain a pile of 3, and two of 2, thus a pile of 4 and one of 3. Thus, one can do better than the number of 1s in the binary representation of $n$.

By testing numbers from 8 to 16, one sees that one can obtain 2 piles for numbers that are not powers of 2, but not better, and that the good strategy is to form a large pile of a power of 2, then to slightly empty it to form 2 piles. After that, it only remains to formalize this argument to show that one can obtain two piles.

The most difficult part of the exercise remained: why, if $n$ is not a power of 2, one cannot obtain a single pile. Unfortunately, some misread the statement and thought they had to remove as many pieces from the first pile as there were in the second: this is not stated in the statement. Some tried to proceed by induction to show that several steps before the end, there was a pile of size $n / 2^{k}$ (or even $2^{k}$ such piles). This is not true for $k=3$: indeed, one can imagine having a pile of $5n / 8$ and one of $3n / 8$, taking $n / 8$ pieces from each to have a pile of $n / 2$ and two of $n / 4$, and in two merges obtaining a single pile.

The argument was more subtle: the simplest was to write $n = 2^{k} \times y$ with $y$ odd, and to show by induction that $k$ steps before the end, each pile had a size divisible by $y$. Alternatively, to show that the piles had a size of the form $k n / 2^{j}$ with $k$ odd, and thus could never be of size 1.