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

Difference between revisions of "2015 USAMO Problems/Problem 4"

(Leaving space between lemmas and proofs)
m (minor hole in solution)
 
(8 intermediate revisions by the same user not shown)
Line 8: Line 8:
 
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>
 
Let the number of stones in row <math>i</math> be <math>r_i</math> and let the number of stones in column <math>i</math> be <math>c_i</math>. Since there are <math>m</math> stones, we must have <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>
  
−
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are equivalent <math>\forall i</math>.
+
Lemma 1: If any <math>2</math> pilings are equivalent, then <math>r_i</math> and <math>c_i</math> are the same in both pilings <math>\forall i</math>.
  
 
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.
 
Proof: We suppose the contrary. Note that <math>r_i</math> and <math>c_i</math> remain invariant after each move, therefore, if any of the <math>r_i</math> or <math>c_i</math> are different, they will remain different.
Line 16: Line 16:
 
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 <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 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 <math>(a, b)</math> in piling 1. Since <math>c_b</math> is the same for both pilings, we must have a wrong stone in piling 2 at column b, say at <math>(c, b)</math>, such that <math>c\not = a</math>. Similarly, we must have a wrong stone in piling 1 at row c, say at <math>(c, d)</math> where <math>d \not = b</math>. Clearly, making the move <math>(a,b);(c,d) \implies (c,b);(a,d)</math> in piling 1 decreases the number of wrong stones in piling 1. Therefore, the number of wrong stones in piling 1 must eventually be <math>0</math> after a sequence of moves, so piling 1 and piling 2 are equivalent.
  
−
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.
+
Lemma 3: Given the sequences <math>g_i</math> and <math>h_i</math> such that <math>\sum_{i=1}^n g_i=\sum_{i=1}^n h_i=m</math> and <math>g_i, h_i\geq 0 \forall i</math>, there is always a piling that satisfies <math>r_i=g_i</math> and <math>c_i=h_i</math> <math>\forall i</math>.
  
−
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone there, then we subtract <math>r_i</math> and <math>c_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each step. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> remain invariant, thus, the final piling satisfies the conditions above.
+
Proof: We take the lowest <math>i</math>, <math>j</math>, such that <math>g_i, h_j >0</math> and place a stone at <math>(i, j)</math>, then we subtract <math>g_i</math> and <math>h_j</math> by <math>1</math> each, until <math>g_i</math> and <math>h_i</math> become <math>0</math> <math>\forall i</math>, which will happen when <math>m</math> stones are placed, because <math>\sum_{i=1}^n g_i</math> and <math>\sum_{i=1}^n h_i</math> are both initially <math>m</math> and decrease by <math>1</math> after each stone is placed. Note that in this process <math>r_i+g_i</math> and <math>c_i+h_i</math> 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 <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.
+
By the above lemmas, the number of ways to pile is simply the number of ways to choose the sequences <math>r_i</math> and <math>c_i</math> such that <math>\sum_{i=1}^n r_i=\sum_{i=1}^n c_i=m</math> and <math>r_i, c_i \geq 0 \forall i</math>. By stars and bars, the number of ways is <math>\binom{n+m-1}{m}^{2}</math>.
  
 
Solution by Shaddoll
 
Solution by Shaddoll

Latest revision as of 19:09, 10 March 2016

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\geq 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=77499"