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
According to the given, , where
and
are rational. Likewise,
. Hence
, namely
. Let
, then consider
, where
and
. We have:
By induction,
for all in.tegers
.
Therefore, for nonzero integer
,
, namely
.
Hence
. Letting
, we obtain
, where
is the slope of the linear functions, and
.