International Mathematical Olympiad

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 }& \to & 2^{k-1}\text{ piles of }2\text{ pebbles }\\ 2^{k-1}\text{ piles of }2\text{ pebbles }& \to & 2^{k-2}\text{ piles of }4\text{ pebbles }\\ 2^{k-2}\text{ piles of }4\text{ pebbles }& \to & 2^{k-3}\text{ piles of }8\text{ pebbles }\\ & ⋮& \\ 2\text{ piles of }{2}^{k-1}\text{ pebbles }& \to & 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⩽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⩽\min (a,b)$ pebbles from both piles, and forming a new pile with $2c$ 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}{rl}& a\to a-c\\ & b\to b-c\\ & 0\to 2c\end{array}$$ Assume that after the move the number of pebbles in each pile is divisible by an odd integer $m$. In particular, $m|2c,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.

---

Alternative solution.

We show an alternative strategy if $n$ is not a power of $2$. Write $n$ in binary form: $n=2^{i_1}+2^{i_2}+\cdots +2^{i_k}$, where $i_1>i_2>\cdots >i_k$. Now we make piles of sizes $2^{i_1},2^{i_2},\dots ,2^{i_k}$. We call the pile with $2^{i_1}$ the large pile, all the others are the small piles.

The strategy is the following: take the two smallest small piles. If they have the same size of $2^a$, we make a pile of size $2^{a+1}$. If they have different sizes, we double the smaller pile using the large pile (we allow the large pile to have a negative number of pebbles: later we prove that it is not possible). We call all the new piles small. When we have only one small pile, we terminate the process: we have at most $2$ piles.

After each move we have one less number of piles, and all the piles have cardinality power of $2$. The number of pebbles is decreasing, and at the end of the process, it has a size of $n-2^{i_2+1}⩾n-2^{i_1}>0$, thus we can manage to have two piles.

---

Alternative solution.

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}$ - simple if each (non-empty) pile in $\mathcal{C}$ consists of a single pebble; - good if at least one (non-empty) pile in $\mathcal{C}$ has an even number of pebbles and the numbers of pebbles on the piles in $\mathcal{C}$ have no non-trivial odd common divisor ($\mathcal{C}$ has the odd divisor property); - solvable if there exists a simple configuration which is reachable from $\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 $|{\mathcal{C}}^{\prime }|⩾|\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 $|{\mathcal{C}}^{\prime }|⩾|\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, $2a,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 $2a,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: - ${\mathcal{C}}^{\prime }$ is reachable from $\mathcal{C}$ and $|{\mathcal{C}}^{\prime }|>|\mathcal{C}|$; - ${\mathcal{C}}^{\prime }$ is either simple or good.

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,\dots ,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⩾1$ we have $a_j\equiv \frac{a_i}{2}(\mathrm{mod}{2}^t)$ for all $j\ne 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\ne i$ are odd. To prove the second assertion, we proceed by induction on $t$, with the case $t=1$ already being established. If $t⩾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}(a_j+\frac{a_i}{2})(\mathrm{mod}{2}^{t-1})$, whence $a_j\equiv \frac{a_i}{2}(\mathrm{mod}{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=2x$ and $a_j=x$ for all $j\ne i$. Thus, $x$ is an odd common divisor of $a_1,\dots ,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. ($⟹$) 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.

($⟸$) 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⩾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.