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
, there is always a piling that satisfies
and
.
Proof: We take the lowest ,
, such that
and place a stone at (i, j)
g_i
h_j
1
g_i
h_i
0$$ (Error compiling LaTeX. Unknown error_msg)\forall i
m
\sum_{i=1}^n g_i
\sum_{i=1}^n h_i
m
1
r_i+g_i
c_i+h_i$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$ (Error compiling LaTeX. Unknown error_msg)r_ic_i
\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m
\binom{n+m-1}{m}^{2}$.
Solution by Shaddoll