Re: Combi Marathon
Posted: Sun Feb 26, 2017 4:59 pm
The following solution is not completely mine. I solved it partially and then saw the solu in AOPS.
Solution to problem 8
Wlog, we rearrange the piles such that the piles are nonincreasing and we place them on the coordinate system such that every pile starts from the x axis and the leftmost pile starts from the origin.
Define the value of a stone to be the sum of the coordinates. Similarly, define the sum of a collection to be the sum of the values of all squares.
Lemma: The value sum of any collection of piles does not increase (either stays the same or decreases) with each move.
Proof: Shifting the squares one unit down and one unit right keeps the sum invariant. Now, there is a row of stones below the x axis. Reflecting those squares about the line $y = x-1$ keeps the sum invariant again. Now if the first pile contains as many stones as any other pile, the piles are properly ordered, and the sum remains as it was before. Otherwise, some stones will be shifted to the left, decreasing the sum.
Let $K = (n, n-1, ..., 1)$. Suppose that there exist collections of piles with $\frac{n(n+1)}{2}$ stones that do not lead to $K$ after performing some number of moves. Pick the collection with minimal sum, call it $C$. Notice that all collections formed after some number of moves on $C$ have the same level sum as $C$ because by assumption they never lead to $K$. This is important because it means that all squares cycle with a period equivalent to their level (for example, if we label the top stone in the first pile of $K$ as $a$, we see that after successive moves, stone $a$ either moves South-East or North-East to its initial position - which preserves its value). Now the key observation is that $(1)$ there is a stone in $C$ which has value $n$, call it $x'$, that does not occur in $K$ (obviously, $K$ only contains stones of value $\le n-1$), and $(2)$ a stone in $K$, call it $y'$ with value $n-1$ that does not occur in $C$. To see $(1)$, notice that if all stones in $C$ had value $\le n-1$, than since $C$ contains $\frac{n(n+1)}{2}$ stones, $C = K$, so $C$ must contain a stone of value $\ge n$. If that stone has value $> n$, it has a square below it with level $n$. The argument for $(2)$ is identical (if all stones of value $n-1$ which occur in $K$ were also in $C$, $C = K$).
Finally, after $n+1$ moves, $x'$ stays in its initial position, while $y'$ moves $SE$. After so finite number of moves, therefore, $y'$ will be directly below $x'$, which is a contradiction, since $y'$ is a hole (it is not actually in $C$).
Solution to problem 8
Wlog, we rearrange the piles such that the piles are nonincreasing and we place them on the coordinate system such that every pile starts from the x axis and the leftmost pile starts from the origin.
Define the value of a stone to be the sum of the coordinates. Similarly, define the sum of a collection to be the sum of the values of all squares.
Lemma: The value sum of any collection of piles does not increase (either stays the same or decreases) with each move.
Proof: Shifting the squares one unit down and one unit right keeps the sum invariant. Now, there is a row of stones below the x axis. Reflecting those squares about the line $y = x-1$ keeps the sum invariant again. Now if the first pile contains as many stones as any other pile, the piles are properly ordered, and the sum remains as it was before. Otherwise, some stones will be shifted to the left, decreasing the sum.
Let $K = (n, n-1, ..., 1)$. Suppose that there exist collections of piles with $\frac{n(n+1)}{2}$ stones that do not lead to $K$ after performing some number of moves. Pick the collection with minimal sum, call it $C$. Notice that all collections formed after some number of moves on $C$ have the same level sum as $C$ because by assumption they never lead to $K$. This is important because it means that all squares cycle with a period equivalent to their level (for example, if we label the top stone in the first pile of $K$ as $a$, we see that after successive moves, stone $a$ either moves South-East or North-East to its initial position - which preserves its value). Now the key observation is that $(1)$ there is a stone in $C$ which has value $n$, call it $x'$, that does not occur in $K$ (obviously, $K$ only contains stones of value $\le n-1$), and $(2)$ a stone in $K$, call it $y'$ with value $n-1$ that does not occur in $C$. To see $(1)$, notice that if all stones in $C$ had value $\le n-1$, than since $C$ contains $\frac{n(n+1)}{2}$ stones, $C = K$, so $C$ must contain a stone of value $\ge n$. If that stone has value $> n$, it has a square below it with level $n$. The argument for $(2)$ is identical (if all stones of value $n-1$ which occur in $K$ were also in $C$, $C = K$).
Finally, after $n+1$ moves, $x'$ stays in its initial position, while $y'$ moves $SE$. After so finite number of moves, therefore, $y'$ will be directly below $x'$, which is a contradiction, since $y'$ is a hole (it is not actually in $C$).