2015 USAJMO Problems/Problem 6
Solution
Let the number of stones in row be and let the number of stones in column be . Since there are stones, we must have
Lemma 1: If any pilings are equivalent, then and are the same in both pilings .
Proof: We suppose the contrary. Note that and remain invariant after each move, therefore, if any of the or are different, they will remain different.
Lemma 2: Any pilings with the same and are equivalent.
Proof: Suppose piling 1 and piling 2 not the same piling. Call a stone in piling 1 wrong if the stone occupies a position such that there are more stones in that position in piling 1 than piling 2. Similarly define a wrong stone in piling 2. Let a wrong stone be at in piling 1. Since is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at , such that . Similarly, we must have a wrong stone in piling 1 at row c, say at where . Clearly, making the move in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be after a sequence of moves, so piling 1 and piling 2 are equivalent.
Lemma 3: Given the sequences and such that and , there is always a piling that satisfies and .
Proof: We take the lowest , , such that and place a stone at , then we subtract and by each, until and become , which will happen when stones are placed, because and are both initially and decrease by after each stone is placed. Note that in this process and remains invariant, thus, the final piling satisfies the conditions above.
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences and such that and . By stars and bars, the number of ways is .
Solution by Shaddoll