Let \(n\) be a positive integer. We start with \(n\) piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of \(n\)) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.
Answer: \(1\) if \(n\) is a power of two, and \(2\) otherwise.
The solution we describe is simple, but not the most effective one.
We can combine two piles of \(2^{k-1}\) pebbles to make one pile of \(2^{k}\) pebbles. In particular, given \(2^{k}\) piles of one pebble, we may combine them as follows:
\[\begin{array}{lll} 2^{k} \text { piles of } 1 \text { pebble } & \rightarrow 2^{k-1} \text { piles of } 2 \text { pebbles } \\ 2^{k-1} \text { piles of } 2 \text { pebbles } & \rightarrow 2^{k-2} \text { piles of } 4 \text { pebbles } \\ 2^{k-2} \text { piles of } 4 \text { pebbles } & \rightarrow 2^{k-3} \text { piles of } 8 \text { pebbles } \\ & \vdots & \\ 2 \text { piles of } 2^{k-1} \text { pebbles } & \rightarrow 1 \text { pile of } 2^{k} \text { pebbles } \end{array}\]
This proves the desired result in the case when \(n\) is a power of \(2\). If \(n\) is not a power of \(2\), choose \(N\) such that \(2^{N}<n<2^{N+1}\). Let \(m=n-2^{N}\). Then \(0<m<2^{N}\). Make a pile of \(2^{N}\) pebbles and call it the large pile. (Alternatively, one can be more efficient and make a pile of \(2^{M}\) pebbles where \(m \leqslant 2^{M}\).) Since \(n\) is not a power of two, there is at least one other pile with pebbles. All other piles have a single pebble (initial condition). Choose one single pebble pile and remove the pebble and one pebble from the large pile and form a pile of \(2\) pebbles. If \(m<2^{N}-1\), remove another pebble from the large pile and one pebble from the \(2\)-pile and form a new pile of \(2\) pebbles. Repeat until the large pile contains exactly \(m\) pebbles. At this point we have one pile of \(m\) pebbles, one pile of \(2\) pebbles, and the rest are single pebble piles. There must be \(n-m-2=2^{N}-2\) single piles. Combine two and two into piles of two pebbles. Then there are \(2^{N-1}\) piles of two pebbles, which we can make into one pile of \(2^{N}\) pebbles. We are left with exactly two piles of pebbles. Lastly we will prove that it is not possible to form a single pile with all pebbles when \(n\) is not a power of two. A move consists of choosing two piles of say \(a\) and \(b\) pebbles, then removing \(c \leqslant \min (a, b)\) pebbles from both piles, and forming a new pile with \(2 c\) pebbles. If we include piles of zero pebbles, then this move changes the number of pebbles in three piles as follows (and leaves all other piles unchanged):\[\begin{array}{lll} a & \rightarrow a-c \\ b & \rightarrow b-c \\ 0 & \rightarrow 2 c \end{array}\]
Assume that after the move the number of pebbles in each pile is divisible by an odd integer \(m\). In particular, \(m|2 c, m| a-c\) and \(m \mid b-c\). Since \(m\) is odd, it follows that \(m \mid c\), and then that \(m \mid a\) and \(m \mid b\). Hence also before the move the number of pebbles in each pile is divisible by the integer \(m\). If \(n\) is not a power of 2 , then \(n\) is divisible by an odd integer \(m>1\). In order to make a single pile of \(n\) pebbles, we would have to start with a distribution in which the number of pebbles in each pile is divisible by the integer \(m\). This is impossible when we start with all piles containing a single pebble. Remarks on starting configurations From any starting configuration that is not a single pile, if there are at least two piles with at least two pebbles, we can remove one pebble from two such piles, and form a new pile with \(2\) pebbles. We can repeat this until we have one pile of \(2\) pebbles and the rest are single pebble piles, and then proceed as in the solution. Hence, if \(n\) is a power of two, we can make a single pile from any starting configuration. If \(n\) is of the form \(n=2^{k} m\) where \(m>1\) is odd, then we can make a single pile from any starting configuration in which the number of pebbles in each pile is divisible by the integer \(m\), otherwise two piles is the best we can do. Half of this is proven already. For the other half, assume we start with a configuration in which the number of pebbles in each pile is divisible by the integer \(m\). Replace each pile of \(t m\) pebbles with a pile of \(t\) boulders. We now have a total of \(2^{k}\) boulders, hence we can make them into one pile of \(2^{k}\) boulders. Replacing the boulders with pebbles again, we are done.