2015 USAMO Problems/Problem 4
Problem
Steve is piling indistinguishable stones on the squares of an grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions for some , such that and . A stone move consists of either removing one stone from each of and and moving them to and respectively,j or removing one stone from each of and and moving them to and respectively.
Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.
How many different non-equivalent ways can Steve pile the stones on the grid?
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