Problem:
Steve is piling indistinguishable stones on the squares of an grid. Each square can have an arbitrarily high pile of stones. After he is 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, 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:
We think of the pilings as assigning a positive integer to each square on the grid. Now, we restrict ourselves to the types of moves in which we take a lower left and upper right stone and move them to the upper left and lower right of our chosen rectangle. Call this a Type 1 stone move. We claim that we can perform a sequence of Type 1 stone moves on any piling to obtain an equivalent piling for which we cannot perform any Type 1 move, i.e. in which no square that has stones is above and to the right of any other square that has stones. We call such a piling a "down-right" piling.
To prove that any piling is equivalent to a down-right piling, first consider the squares in the leftmost column and topmost row of the grid. Let be the entry (number of stones) in the upper left corner, and let and be the sum of the remaining entries in the leftmost column and topmost row respectively. If , we can perform a sequence of Type 1 stone moves to remove all the stones from the leftmost column except for the top entry, and if we can similarly clear all squares in the top row except for the top left square. In the former case, we can now ignore the leftmost column and repeat the process on the second-to-leftmost column and the top row; similarly, in the latter case, we can ignore the\
top row and proceed as before. Since the corner square cannot be part of any Type 1 move at each step in the process, it follows that we end up with a down-right piling.
We next show that down-right pilings in any size grid (not necessarily ) are uniquely determined by their row-sums and column-sums, given that the row sums and column sums are nonnegative integers which sum to both along the rows and the columns. Let the topmost row sum be and the leftmost column sum be . Then the upper left square must contain stones, since otherwise there would be stones both in the first row and first column that are not in the upper left square. Whichever is smaller indicates that either the row or the column respectively is empty save for the upper left square; then we can remove this row or column and are reduced to a smaller grid in which we know all the row and column sums. Since one-row and one-column pilings are clearly uniquely determined by their column and row sums, it follows by induction that down-right pilings are determined uniquely by their row-sums and column sums.
Finally, notice that row sums and column sums are both invariant under stone moves. Therefore every piling is equivalent to a unique down-right piling. It therefore suffices to count the number of down-right pilings, which is also equivalent to counting the number of possibilities for the row-sums and column-sums. As stated above, the row sums and column sums can be the sums of any two -tuples of nonnegative integers that each sum to . The number of such tuples is , and so the total number of non-equivalent pilings is the number of pairs of these tuples, i.e. .
The problems on this page are the property of the MAA's American Mathematics Competitions