Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2015 USAMO Problems/Problem 4

Revision as of 19:08, 10 March 2016 by Shaddoll (talk | contribs) (minor hole)

Problem

Steve is piling $m\geq 1$ indistinguishable stones on the squares of an $n\times n$ 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 $(i, k), (i, l), (j, k), (j, l)$ for some $1\leq i, j, k, l\leq n$, such that $i<j$ and $k<l$. A stone move consists of either removing one stone from each of $(i, k)$ and $(j, l)$ and moving them to $(i, l)$ and $(j, k)$ respectively,j or removing one stone from each of $(i, l)$ and $(j, k)$ and moving them to $(i, k)$ and $(j, l)$ 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 $i$ be $r_i$ and let the number of stones in column $i$ be $c_i$. Since there are $m$ stones, we must have $\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m$

Lemma 1: If any $2$ pilings are equivalent, then $r_i$ and $c_i$ are the same in both pilings $\forall i$.

Proof: We suppose the contrary. Note that $r_i$ and $c_i$ remain invariant after each move, therefore, if any of the $r_i$ or $c_i$ are different, they will remain different.

Lemma 2: Any $2$ pilings with the same $r_i$ and $c_i$ $\forall i$ 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 $(a, b)$ in piling 1. Since $c_b$ is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at $(c, b)$, such that $c\not = a$. Similarly, we must have a wrong stone in piling 1 at row c, say at $(c, d)$ where $d \not = b$. Clearly, making the move $(a,b);(c,d) \implies (c,b);(a,d)$ in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be $0$ after a sequence of moves, so piling 1 and piling 2 are equivalent.

Lemma 3: Given the sequences $g_i$ and $h_i$ such that $\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m$ and $g_i, h_i>0 \forall i$, there is always a piling that satisfies $r_i=g_i$ and $c_i=h_i$ $\forall i$.

Proof: We take the lowest $i$, $j$, such that $g_i, h_j >0$ and place a stone at $(i, j)$, then we subtract $g_i$ and $h_j$ by $1$ each, until $g_i$ and $h_i$ become $0$ $\forall i$, which will happen when $m$ stones are placed, because $\sum_{i=1}^n g_i$ and $\sum_{i=1}^n h_i$ are both initially $m$ and decrease by $1$ after each stone is placed. Note that in this process $r_i+g_i$ and $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 $r_i$ and $c_i$ such that $\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m$ and $r_i, c_i \geq 0 \forall i$. By stars and bars, the number of ways is $\binom{n+m-1}{m}^{2}$.

Solution by Shaddoll

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_4&oldid=77497"