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 | + | 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 | + | 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 20:09, 10 March 2016
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
and
, there is always a piling that satisfies
and
.
Proof: We take the lowest ,
, such that
and place a stone at
, then we subtract
and
by
each, until
and
become
, which will happen when
stones are placed, because
and
are both initially
and decrease by
after each stone is placed. Note that in this process
and
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 and
such that
and
. By stars and bars, the number of ways is
.
Solution by Shaddoll