Suppose a table with one row and infinite columns. We call each $1\times1$ square a room. Let the table be finite from left. We number the rooms from left to $\infty$. We have put in some rooms some coins (A room can have more than one coin.). We can do $2$ below operations: $a)$ If in $2$ adjacent rooms, there are some coins, we can move one coin from the left room $2$ rooms to right and delete one room from the right room. $b)$ If a room whose number is $3$ or more has more than $1$ coin, we can move one of its coins $1$ room to right and move one other coin $2$ rooms to left. $i)$ Prove that for any initial configuration of the coins, after a finite number of movements, we cannot do anything more. $ii)$ Suppose that there is exactly one coin in each room from $1$ to $n$. Prove that by doing the allowed operations, we cannot put any coins in the room $n+2$ or the righter rooms.
Problem
Source:
Tags: combinatorics proposed, combinatorics
13.12.2018 20:11
/bump......
14.12.2018 16:14
Rephrasing: Quote: There is a $1 \times \infty$ board, bounded on the left, with cells numbered $1, 2, 3, 4, \ldots$ from the left. Initially there are some coins on the board. We can make two kinds of operations, where $k$ is a positive integer: - If cell $k, k+1$ both have at least 1 coin, remove 1 coin from each cell and add 1 coin to cell $k+2$. - If cell $k+2$ has at least 2 coins, remove 2 coins from it and add 1 coin each to cells $k, k+3$. Prove that: - We cannot do infinitely many operations, - If we start with 1 coin on each cell $1, 2, 3, \ldots, n$, we can't have a coin on cell numbered $n+2$ or larger. Let $c_n$ be the number of coins in cell $n$. Part 1: The quantity $\sum (n+1) c_n$ is strictly decreasing: - Operation 1 decreases the sum by $(k+1)+(k+2)$ and increases it by $k+3$, for a net decrease of $k$. - Operation 2 decreases the sum by $2(k+3)$ and increases it by $(k+1)+(k+4)$, for a net decrease of 1. But this quantity is a positive integer (unless there's no coin on the board). Since there is no strictly decreasing sequence of positive integers, at some point the quantity cannot go lower; that's when there is no operation left to make. Part 2: Let $\phi = \frac{1+\sqrt{5}}{2}$ be the positive root of $x^2 - x - 1 = 0$. Then the quantity $\sum \phi^n c_n$ is an invariant, since the two operations both preserve this: - Operation 1 is the identity $\phi^k + \phi^{k+1} = \phi^{k+2}$. - Operation 2 is the identity $2 \phi^{k+2} = \phi^k + \phi^{k+3}$. At the beginning this sum is $\phi + \phi^2 + \ldots + \phi^n = \frac{\phi^{n+1}-\phi}{\phi-1} = \phi^{n+2}-\phi^2$, so it's impossible to have any coin in cell $n+2$ or larger as it would make the sum at least $\phi^{n+2}$.