Kvant Math Problem 1001
Let $S(n)$ denote the total sum of all recorded products when a pile of $n$ stones is repeatedly split until all piles contain one stone.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m40s
Source on kvant.digital
Problem
A pile contains 1001 stones. It is arbitrarily divided into two piles, the number of stones in each is counted, and the product of these two numbers is recorded. Then, the same operation is performed on one of these piles (containing more than one stone): it is divided into two, and the product of the numbers of stones in the newly formed piles is recorded. The same operation is then repeated on one of the resulting three piles, and so on, until all piles contain exactly one stone. What is the sum of the 1000 recorded products?
A. S. Merkuryev
Leningrad City Mathematics Olympiad (1986)
Exploration
Let $S(n)$ denote the total sum of all recorded products when a pile of $n$ stones is repeatedly split until all piles contain one stone.
Small cases suggest a pattern.
For $n=2$, the only split is $2=1+1$, and the recorded product is $1$. Hence $S(2)=1$.
For $n=3$, split as $1+2$. The recorded products are $2$ and then $1$, so $S(3)=3$.
For $n=4$, one possibility is
$$4\to 1+3,$$
giving product $3$, then
$$3\to 1+2,$$
giving product $2$, then
$$2\to 1+1,$$
giving product $1$.
Thus $S(4)=6$.
The values are
$$1,3,6,$$
which equal
$$\binom22,\binom32,\binom42.$$
This suggests
$$S(n)=\binom n2=\frac{n(n-1)}2.$$
The process is not uniquely determined, so the first question is whether the total sum depends on the sequence of splits. For $n=4$, try another decomposition:
$$4\to 2+2.$$
The products recorded are
$$4,\ 1,\ 1,$$
whose sum is again $6$.
The crucial point is to find a quantity preserved by every split. Suppose a pile of size $m$ is divided into piles of sizes $a$ and $b$, where $a+b=m$. The recorded number is $ab$. The identity
$$\binom m2=\binom a2+\binom b2+ab$$
shows that the decrease of $\binom{\cdot}{2}$ caused by the split is exactly the recorded product. This strongly suggests a telescoping argument.
The step most likely to hide an error is proving rigorously that summing this identity over all splits indeed accounts for every recorded product and leaves exactly $\binom{1001}{2}$.
Problem Understanding
We start with one pile containing $1001$ stones. At each step, a pile containing more than one stone is split into two nonempty piles. The product of the sizes of the two new piles is recorded. The procedure continues until every pile contains exactly one stone.
We must determine the sum of all $1000$ recorded products.
This is a Type C problem, since a numerical value must be determined.
The core difficulty is that the sequence of splits is completely arbitrary. The answer must therefore be independent of the choices made during the process. The identity
$$\binom m2=\binom a2+\binom b2+ab$$
suggests that each recorded product measures the decrease of a certain global quantity, causing the total sum to telescope.
The expected answer is
$$\frac{1001\cdot1000}{2}=500500.$$
Proof Architecture
Define the potential of a collection of piles to be the sum of $\binom{x}{2}$ over all pile sizes $x$.
For a split $m=a+b$, prove that the recorded product equals
$$\binom m2-\binom a2-\binom b2.$$
This follows from direct algebraic expansion.
Show that after each split, the decrease of the potential equals the recorded product. This is immediate because only one pile changes.
Sum these equalities over the entire process. The decreases telescope, yielding that the total recorded sum equals the initial potential minus the final potential.
Compute the initial and final potentials. Initially there is one pile of size $1001$, and finally there are $1001$ piles of size $1$.
The most delicate point is the telescoping argument, because it must account for an arbitrary sequence of splits.
Solution
Let
$$\Phi=\sum \binom{x}{2},$$
where the sum is taken over all current piles and $x$ denotes the size of a pile.
Suppose at some stage a pile containing $m$ stones is divided into two piles containing $a$ and $b$ stones, where
$$a+b=m.$$
The recorded product is $ab$.
Using
$$\binom m2=\frac{m(m-1)}2,$$
we obtain
$$\binom m2-\binom a2-\binom b2 = \frac{m(m-1)-a(a-1)-b(b-1)}2.$$
Since $m=a+b$,
$$m(m-1)-a(a-1)-b(b-1) = (a+b)^2-(a+b)-a^2+a-b^2+b = 2ab.$$
Therefore
$$\binom m2-\binom a2-\binom b2=ab.$$
Before the split, the contribution of the pile being divided to $\Phi$ is $\binom m2$. After the split, its contribution becomes
$$\binom a2+\binom b2.$$
All other piles remain unchanged. Hence the decrease of $\Phi$ during this step is
$$\binom m2-\binom a2-\binom b2=ab,$$
which is exactly the recorded product.
Summing over all splits, the total sum of recorded products equals the total decrease of $\Phi$ during the entire process.
Initially there is one pile of size $1001$, so
$$\Phi_{\text{initial}}=\binom{1001}{2}.$$
At the end, all piles have size $1$. Since
$$\binom12=0,$$
the final value is
$$\Phi_{\text{final}}=0.$$
Thus the sum of all recorded products is
$$\Phi_{\text{initial}}-\Phi_{\text{final}} = \binom{1001}{2} = \frac{1001\cdot1000}{2} = 500500.$$
Hence the required value is
$$\boxed{500500}.$$
Verification of Key Steps
The identity
$$\binom m2-\binom a2-\binom b2=ab$$
must be checked carefully. Expanding with $m=a+b$ gives
$$\frac{(a+b)(a+b-1)-a(a-1)-b(b-1)}2 = \frac{2ab}{2} = ab.$$
Any mistake in expanding the quadratic terms would destroy the argument.
The potential function changes only in the pile that is split. If one incorrectly sums
$$\binom a2+\binom b2$$
without subtracting the old contribution $\binom m2$, the decrease is not obtained. The equality between recorded product and decrease of potential relies on comparing the state immediately before and immediately after the split.
For a concrete check, consider
$$4\to2+2\to1+1+2\to1+1+1+1.$$
The recorded products are
$$4,\ 1,\ 1,$$
whose sum is $6$.
The potential values are
$$\binom42=6,\quad \binom22+\binom22=2,\quad 0+0+\binom22=1,\quad 0.$$
The successive decreases are
$$4,\ 1,\ 1,$$
exactly matching the recorded products.
Alternative Approaches
Interpret $\binom{x}{2}$ as the number of unordered pairs of stones contained in the same pile. Initially every pair of stones lies in a common pile, so there are
$$\binom{1001}{2}$$
such pairs.
When a pile of size $m$ is split into piles of sizes $a$ and $b$, exactly $ab$ unordered pairs become separated for the first time, namely the pairs with one stone in each new pile. The recorded number is precisely the number of pairs separated at that step.
Every unordered pair of distinct stones is separated exactly once during the entire process. After separation, the two stones can never belong to the same pile again. Consequently, the sum of all recorded products equals the total number of unordered pairs of stones,
$$\binom{1001}{2}=500500.$$
This combinatorial proof is very short and intuitive. The potential-function proof makes the invariance completely explicit and generalizes immediately to similar splitting processes.