IMO 1996 SL C6

Origin: CAN | Category: Combinatorics

Problem

A finite number of beans are placed on an infinite row of squares. A sequence of moves is performed as follows: at each stage a square containing more than one bean is chosen. Two beans are taken from this square; one of them is placed on the square immediately to the left, and the other is placed on the square immediately to the right of the chosen square. The sequence terminates if at some point there is at most one bean on each square. Given some initial configuration, show that any legal sequence of moves will terminate after the same number of steps and with the same final configuration.

Solution

Let the squares be indexed serially by the integers:

$$\ldots,-1,0,1,2,\ldots$$

When a bean is moved from $i$ to $i+1$ or from $i+1$ to $i$ for the first time, we may assign the index $i$ to it. Thereafter, whenever some bean is moved in the opposite direction, we shall assume that it is exactly the one marked by $i$, and so on. Thus, each pair of neighboring squares has a bean stuck between it, and since the number of beans is finite, there are only finitely many pairs of neighboring squares, and thus finitely many squares on which moves are made. Hence we may assume without loss of generality that all moves occur between $0$ and $l \in \mathbb{N}$ and that all beans exist at all times within $[0,l]$.

Defining $b_i$ to be the number of beans in the $i$th cell $(i \in \mathbb{Z})$ and $b$ the total number of beans, we define the semi-invariant

$$S=\sum_{i\in\mathbb{Z}} i^2 b_i.$$

Since all moves occur above $0$, the semi-invariant $S$ increases by $2$ with each move, and since we always have

$$S<b\cdot l^2,$$

it follows that the number of moves must be finite.

We now prove the uniqueness of the final configuration and the number of moves for some initial configuration ${b_i}$. Let $x_i\geq0$ be the number of moves made in the $i$th cell $(i\in\mathbb{Z})$ during the game. Since the game is finite, only finitely many of the $x_i$ are nonzero. Also, the number of beans in cell $i$, denoted by $e_i$, at the end is

$$(\forall i\in\mathbb{Z})\qquad e_i=b_i+x_{i-1}+x_{i+1}-2x_i\in{0,1}. \tag{1}$$

Thus it is enough to show that, given $b_i\geq0$, the sequence ${x_i}_{i\in\mathbb{Z}}$ of nonnegative integers satisfying $(1)$ is unique.

Suppose the assertion is false, i.e., that there exists at least one sequence $b_i\geq0$ for which there exist distinct sequences ${x_i}$ and ${x_i'}$ satisfying $(1)$. We may choose such a ${b_i}$ for which

$$\min\left{ \sum_{i\in\mathbb{Z}} x_i, \sum_{i\in\mathbb{Z}} x_i' \right}$$

is minimal (since $\sum_{i\in\mathbb{Z}} x_i$ is always finite).

Choose any index $j$ such that $b_j>1$. Such an index $j$ exists, since otherwise the game is over. Then one must make at least one move in the $j$th cell, which implies that

$$x_j,x_j'\geq1.$$

However, the sequences ${x_i}$ and ${x_i'}$ with $x_j$ and $x_j'$ decreased by $1$ also satisfy $(1)$ for a sequence ${b_i}$ where

$$b_{j-1},b_j,b_{j+1}$$

is replaced with

$$b_{j-1}+1,\ b_j-2,\ b_{j+1}+1.$$

This contradicts the assumption of minimal

$$\min\left{ \sum_{i\in\mathbb{Z}} x_i, \sum_{i\in\mathbb{Z}} x_i' \right}$$

for the initial ${b_i}$.