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.
Throughout the solution, we will consider the moves in reverse order. Namely, imagine we have some piles of pebbles, and we are allowed to perform moves as follows: take a pile with an even number of pebbles, split it into two equal halves and add the pebbles from each half to a different pile, possibly forming new piles (we may assume for convenience that there are infinitely many empty piles at any given moment). Given a configuration of piles \(\mathcal{C}\), we will use \(|\mathcal{C}|\) to denote the number of non-empty piles in \(\mathcal{C}\). Given two configurations \(\mathcal{C}_{1}, \mathcal{C}_{2}\), we will say that \(\mathcal{C}_{2}\) is reachable from \(\mathcal{C}_{1}\) if \(\mathcal{C}_{2}\) can be obtained by performing a finite sequence of moves starting from \(\mathcal{C}_{1}\). Call a configuration of piles \(\mathcal{C}\)
The problem asks to find the smallest number of non-empty piles in a solvable configuration consisting of \(n\) pebbles. We begin the process of answering this question by making the following observation:
Lemma 1: Let \(\mathcal{C}\) be a configuration of piles. Let \(\mathcal{C}^{\prime}\) be a configuration obtained by applying a single move to \(\mathcal{C}\). Then
i. if \(\mathcal{C}^{\prime}\) has the odd divisor property, then so does \(\mathcal{C}\);
ii. the converse to (i) holds if \(\left|\mathcal{C}^{\prime}\right| \geqslant|\mathcal{C}|\).
Proof: Suppose that the move consists of splitting a pile of size \(2a\) and adding \(a\) pebbles to each of two piles of sizes \(b\) and \(c\). Here, \(a\) is a positive integer and \(b, c\) are non-negative integers. Thus, \(\mathcal{C}^{\prime}\) can be obtained from \(\mathcal{C}\) by replacing the piles of sizes \(2a, b, c\) by two piles of sizes \(a+b\) and \(a+c\). Note that the extra assumption \(\left|\mathcal{C}^{\prime}\right| \geqslant|\mathcal{C}|\) of part (ii) holds if and only if at least one of \(b, c\) is zero.
i. Suppose \(\mathcal{C}\) doesn't have the odd divisor property, i.e. there exists an odd integer \(d>1\) such that the size of each pile in \(\mathcal{C}\) is divisible by \(d\). In particular, \(2 a, b, c\) are multiples of \(d\), so since \(d\) is odd, it follows that \(a, b, c\) are all divisible by \(d\). Thus, \(a+b\) and \(a+c\) are also divisible by \(d\), so \(d\) divides the size of each pile in \(\mathcal{C}^{\prime}\). In conclusion, \(\mathcal{C}^{\prime}\) doesn't have the odd divisor property.
ii. If \(\mathcal{C}^{\prime}\) doesn't have the odd divisor property and at least one of \(b, c\) is zero, then there exists an odd integer \(d>1\) such that the size of each pile in \(\mathcal{C}^{\prime}\) is divisible by \(d\). In particular, \(d\) divides \(a+b\) and \(a+c\), so since at least one of these numbers is equal to \(a\), it follows that \(d\) divides \(a\). But then \(d\) must divide all three of \(a, b\) and \(c\), and hence it certainly divides \(2 a, b\) and \(c\). Thus, \(\mathcal{C}\) doesn't have the odd divisor property, as desired.
Lemma 2: If \(\mathcal{C}_{2}\) is reachable from \(\mathcal{C}_{1}\) and \(\mathcal{C}_{2}\) has the odd divisor property, then so does \(\mathcal{C}_{1}\). In particular, any solvable configuration has the odd divisor property.
Proof: The first statement follows by inductively applying part (i) of Lemma 1. The second statement follows from the first because every simple configuration has the odd divisor property.
The main claim is the following:
Lemma 3: Let \(\mathcal{C}\) be a good configuration. Then there exists a configuration \(\mathcal{C}^{\prime}\) with the following properties:
Proof: Call a configuration terminal if it is a counterexample to the claim. The following claim is at the heart of the proof:
Claim: Let \(a_{1}, \ldots, a_{k}\) be the numbers of pebbles on the non-empty piles of a terminal configuration \(\mathcal{C}\). Then there exists a unique \(i \in[k]\) such that \(a_{i}\) is even. Moreover, for all \(t \geqslant 1\) we have \(a_{j} \equiv \frac{a_{i}}{2}\left(\bmod 2^{t}\right)\) for all \(j \neq i\).
Proof of Claim: Since the configuration is good, there must exist \(i \in[k]\) such that \(a_{i}\) is even. Moreover, by assumption, if we split the pile with \(a_{i}\) pebbles into two equal halves, the resulting configuration will not be good. By part (ii) of Lemma 2,the only way this can happen is that \(\frac{a_{i}}{2}\) and \(a_{j}\) for all \(j \neq i\) are odd. To prove the second assertion, we proceed by induction on \(t\), ith the case \(t=1\) already being established. If \(t \geqslant 2\), then split the pile with \(a_{i}\) pebbles into two equal halves and move one half to the pile with \(a_{j}\) pebbles. Since \(\frac{a_{i}}{2}\) and \(a_{j}\) are both odd, \(a_{j}+\frac{a_{i}}{2}\) is even, so by part (ii) of Lemma 2, the resulting configuration \(\mathcal{C}^{\prime}\) is good. Thus, \(\mathcal{C}^{\prime}\) is terminal, so by the induction hypothesis, we have \(\frac{a_{i}}{2} \equiv \frac{1}{2}\left(a_{j}+\frac{a_{i}}{2}\right)\left(\bmod 2^{t-1}\right)\), whence \(a_{j} \equiv \frac{a_{i}}{2} \pmod {2^{t}}\)), as desired.
Suppose for contradiction that there exists a configuration as in the Claim. It follows that there exists \(i \in[k]\) and an odd integer \(x\) such that \(a_{i}=2 x\) and \(a_{j}=x\) for all \(j \neq i\). Thus, \(x\) is an odd common divisor of \(a_{1}, \ldots, a_{k}\), so by the odd divisor property, we must have \(x=1\). But then we can obtain a simple configuration by splitting the only pile with two pebbles into two piles each consisting of a single pebble, which is a contradiction.
With the aid of Lemmas 2 and 3, it is not hard to characterise all solvable configurations: Lemma 4. A configuration of piles \(\mathcal{C}\) is solvable if and only if it is simple or good.
Proof: (\(\Longrightarrow\)) Suppose \(\mathcal{C}\) is not simple. Then since we have to be able to perform at least one move, there must be at least one non-empty pile in \(\mathcal{C}\) with an even number of pebbles. Moreover, by Lemma 2, \(\mathcal{C}\) has the odd divisor property, so it must be good.
\((\Longleftarrow)\) This follows by repeatedly applying Lemma 3 until we reach a simple configuration. Note that the process must stop eventually since the number of non-empty piles is bounded from above.
Finally, the answer to the problem is implied by the following corollary of Lemma 4: Lemma 5. Let \(n\) be a positive integer. Then
(i) a configuration consisting of a single pile of \(n\) pebbles is solvable if and only if \(n\) is a power of two;
(ii) if \(n \geqslant 2\), then the configuration consisting of piles of sizes 2 and \(n-2\) is good.
Proof: (i) By Lemma 4, this configuration is solvable if and only if either \(n=1\) or \(n\) is even and has no non-trivial odd divisor, so the conclusion follows.
(ii) Since 2 is even and has no non-trivial odd divisor, this configuration is certainly good, so the conclusion follows by Lemma 4.
Instead of choosing pebbles from two piles, one could allow choosing an equal number of pebbles from each of \(k\) piles, where \(k \geqslant 2\) is a fixed (prime) integer. However, this seems to yield a much harder problem - if \(k=3\), numerical evidence suggests the same answer as in the case \(k=2\) (with powers of two replaced by powers of three), but the case \(k=5\) is already unclear.