Fascinating induction problem with numerous interpretations

Solution 1:

Here's a slick geometric proof (I'll clean this diagram up later when I can draw it properly): $$ \begin{array}{lllllll} \circ \\ \circ & \circ\\ \circ & \circ & \circ\\ \bullet& \bullet& \bullet& \bullet\\ \bullet& \bullet& \bullet& \bullet& \circ\\ \bullet& \bullet& \bullet& \bullet& \circ & \circ \\ \end{array} $$ Here $n=7$, $r=4$, $s=3$. We start with an $(n-1)\times(n-1)$ right triangle (of area $\frac{n(n-1)}2$); then splitting $n$ and adding a term of form $r\times s$ corresponds to taking the rectangular chunk above out of the triangle, and the two piles of size $r$ and $s$ correspond to the two right triangles (of edge lengths $r-1$ and $s-1$) left over. Each further step of the process just corresponds to taking another rectangle (with its top right corner on the diagonal) out of what's left of the original right triangle and leaving two more right triangles (possibly empty) behind.

Solution 2:

Think of it as an energy calculation with stack of chips (or coins) instead of piles of stones. A chip whose bottom side is at height $h$ has "potential energy" $h$; when it moves down to height $k$, it "releases" (as "heat" or whatever) the amount of energy $h-k$. A stack of $n$ chips starts with potential energy $0+1+2+\cdots+(n-1)=n(n-1)/2$, all of which is released by the time things are down to $n$ stacks of $1$ chips each.

When you split a pile of $r+s$ chips into two piles by taking, say $r$ chips from the top to make a new pile, each of those chips moves down by $s$ positions. This releases energy $rs$. So no matter how you go about the disassembly of the initial stack, the sum of those $rs$'s must be $n(n-1)/2$.

(I have to give credit here to Richard Guy, who told me about the problem a few years ago and gave me the hint "potential energy.")