Kvant Math Problem 1241
For a small instance with piles $1,2,3$, one move cannot remove all stones, because the three pile sizes are different.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m06s
Source on kvant.digital
Problem
There are 1990 piles consisting of 1, 2, 3, $\ldots$, 1990 stones, respectively. In one move, it is allowed to remove the same number of stones from any subset of piles. What is the minimum number of moves required to remove all the stones?
N. Agahanov
All-Union Mathematical Olympiad (XXIV, 1990)
Exploration
For a small instance with piles $1,2,3$, one move cannot remove all stones, because the three pile sizes are different. Two moves suffice: remove $2$ stones from piles $2$ and $3$, leaving $(1,0,1)$, then remove $1$ stone from the remaining two nonempty piles.
For piles $1,2,3,4$, three moves are enough. Remove $4$ from pile $4$, remove $2$ from piles $2$ and $3$, and remove $1$ from piles $1$ and $3$. Each pile size has been represented as a sum of distinct move sizes:
$$1=1,\qquad 2=2,\qquad 3=2+1,\qquad 4=4.$$
This suggests viewing each move as having a certain value, and each pile receives that value if it belongs to the chosen subset. If the move sizes are $a_1,\dots,a_m$, then every pile size must be representable as a sum of some subcollection of these numbers.
Hence, after $m$ moves, the number of different pile sizes that can be produced is at most the number of subsets, namely $2^m$. Since the piles have sizes $1,2,\dots,1990$, there are $1991$ required sums if we include $0$. This gives the lower bound
$$2^m\ge 1991.$$
Since
$$2^{10}=1024<1991<2048=2^{11},$$
we obtain $m\ge 11$.
The crucial point is whether $11$ moves are actually sufficient. The natural idea is to use move sizes
$$1,2,4,\dots,1024.$$
Every integer from $0$ to $2047$ has a binary expansion, so every pile size from $1$ to $1990$ can be represented as a subset sum of these eleven numbers. Then, for each move size $2^k$, remove $2^k$ stones from exactly those piles whose binary representation contains that bit.
The only delicate step is proving rigorously that any strategy with $m$ moves yields at most $2^m$ different initial pile sizes.
Problem Understanding
We have piles containing $1,2,\dots,1990$ stones. In one move we choose any subset of piles and remove the same positive number of stones from every pile in that subset. The task is to determine the minimum number of moves needed to make all piles empty.
This is a Type C problem. We must determine the minimum possible number of moves and prove both that this number can be achieved and that fewer moves are impossible.
The core difficulty is to translate a sequence of moves into a combinatorial description of the original pile sizes. Each move contributes a fixed amount to every pile on which it acts, so every initial pile size must be expressible as a subset sum of the move sizes. Since $1990$ is slightly below $2^{11}$, one expects that $11$ binary move sizes should suffice.
Proof Architecture
The first lemma states that if the move sizes are $a_1,\dots,a_m$, then the initial size of every pile is a subset sum of ${a_1,\dots,a_m}$. This follows because a pile loses exactly those move sizes corresponding to the moves in which it participates.
The second lemma states that after $m$ moves there can be at most $2^m$ distinct pile sizes. This follows because there are only $2^m$ subsets of an $m$ element set.
The lower bound is obtained by applying the second lemma to the $1991$ numbers $0,1,\dots,1990$.
The upper bound is obtained by choosing move sizes $1,2,4,\dots,1024$ and using binary representations.
The hardest direction is the lower bound. The lemma most likely to fail under careless scrutiny is the claim that each pile size corresponds to a subset sum of the move sizes.
Solution
Suppose a strategy uses $m$ moves. Let the numbers of stones removed in the moves be
$$a_1,a_2,\dots,a_m.$$
Consider any pile. During move $i$, either this pile is chosen and loses $a_i$ stones, or it is not chosen and loses nothing. Since the pile ends empty, its initial size equals the total number of stones removed from it over the entire process. Hence its initial size is of the form
$$\sum_{i\in S} a_i$$
for some subset $S\subseteq{1,\dots,m}$.
Thus every initial pile size belongs to the set of subset sums of $a_1,\dots,a_m$.
There are at most $2^m$ subsets of ${1,\dots,m}$, so there are at most $2^m$ subset sums. Consequently the number of distinct pile sizes that can occur initially is at most $2^m$.
Our collection of piles has sizes
$$1,2,\dots,1990.$$
Together with the size $0$, which is also a subset sum corresponding to the empty subset, we obtain $1991$ distinct numbers
$$0,1,\dots,1990.$$
Therefore
$$2^m\ge 1991.$$
Since
$$2^{10}=1024<1991<2048=2^{11},$$
every strategy requires at least $11$ moves.
It remains to show that $11$ moves suffice.
Take eleven moves whose sizes are
$$1,2,4,8,\dots,1024.$$
Every integer $n$ with $0\le n\le 1990$ has a binary expansion
$$n=\sum_{k=0}^{10}\varepsilon_k2^k, \qquad \varepsilon_k\in{0,1}.$$
For the move of size $2^k$, choose exactly those piles whose binary expansion contains the digit $\varepsilon_k=1$ in position $k$.
Fix a pile containing $n$ stones. The moves applied to this pile are precisely those corresponding to the ones in the binary expansion of $n$. The total number of stones removed from this pile is therefore
$$\sum_{k=0}^{10}\varepsilon_k2^k=n.$$
Hence the pile becomes empty.
Since this holds for every pile of size $1,2,\dots,1990$, all piles are removed in $11$ moves.
The lower bound shows that fewer than $11$ moves are impossible, and the construction shows that $11$ moves are sufficient. Therefore the minimum number of moves is
$$\boxed{11}.$$
Equality holds for the binary construction described above.
Verification of Key Steps
The lower bound depends on the statement that every pile size is a subset sum of the move sizes. For a fixed pile, define $S$ to be the set of moves in which that pile participates. During move $i\in S$ it loses exactly $a_i$ stones, and during moves outside $S$ it loses none. Since the pile finishes with zero stones, its initial size is exactly $\sum_{i\in S}a_i$. No additional assumption is used.
The counting argument requires only an upper bound. Different subsets may produce the same sum, so the number of distinct subset sums can be smaller than $2^m$, but it can never exceed $2^m$. Thus having $1991$ distinct required values forces $2^m\ge1991$.
For the construction, the largest move size is $1024$. A pile of size $n\le1990$ participates in the move of size $1024$ only when the corresponding binary digit equals $1$. The total removed from that pile is exactly its binary expansion. Since every integer from $0$ to $1990$ has such an expansion using the powers $2^0,\dots,2^{10}$, no pile receives too many or too few stones removed.
Alternative Approaches
One can formulate the problem in terms of characteristic vectors. Associate to each pile a binary vector of length $m$, where the $i$th coordinate equals $1$ if the pile participates in move $i$ and equals $0$ otherwise. The size of the pile is the scalar product of this vector with $(a_1,\dots,a_m)$. Since there are only $2^m$ binary vectors, there can be at most $2^m$ different pile sizes. This yields the same lower bound.
Another approach to the upper bound is to regard the eleven moves as generating all integers from $0$ to $2047$. The powers of two form a basis for binary representation, so every required pile size is obtained uniquely as a subset sum. This is essentially the same construction, expressed in the language of subset sum systems rather than binary digits.