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

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

@@ Line 1: / Line 1: @@
-According to the given, f(x-a)+f(x+0.5a)=f(x-0.5a)+f(x), where x and a are rational. Likewise f(x-0.5a)+f(x+a)=f(x+0.5a)+f(x). Hence f(x+a)-f(x)= f(x)-f(x-a), namely 2f(x)=f(x-a)+f(x+a). Let f(0)=C, then consider F(x)=f(x)-C, where F(0)=0, 2F(x)=F(x-a)+F(x+a).
+===Problem===
+Steve is piling <math>m\geq 1</math> indistinguishable stones on the squares of an <math>n\times n</math> 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 <math>(i, k), (i, l), (j, k), (j, l)</math> for some <math>1\leq i, j, k, l\leq n</math>, such that <math>i<j</math> and <math>k<l</math>. A stone move consists of either removing one stone from each of <math>(i, k)</math> and <math>(j, l)</math> and moving them to <math>(i, l)</math> and <math>(j, k)</math> respectively,j or removing one stone from each of <math>(i, l)</math> and <math>(j, k)</math> and moving them to <math>(i, k)</math> and <math>(j, l)</math> respectively.
-F(2x)=F(x)+[F(x)-F(0)]=2F(x),
+Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves.
-F(3x)=F(2x)+[F(2x)-F(x)]=3F(x).
-Easily, by induction, F(nx)=nF(x) for all integers k.
+How many different non-equivalent ways can Steve pile the stones on the grid?
-Therefore, for nonzero integer m, (1/m)F(mx)=F(x) , namely F(x/m)=(1/m)F(x)
+==Solution==
-Hence F(n/m)=(n/m)F(1). Let F(1)=k, we obtain F(x)=kx, where k is the slope of the linear functions, and f(x)=kx+C.
+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 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.
+Lemma 2: Any <math>2</math> pilings with the same <math>r_i</math> and <math>c_i</math> <math>\forall i</math> 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> 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 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> 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

Page

Toolbox

Search

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

Latest revision as of 19:09, 10 March 2016

Problem

Solution