Kvant Math Problem 1475

Verified: yes
Verdicts: PASS + PASS
Solve time: 17m24s
Source on kvant.digital

Problem

A strip of size $1\times n$ is divided into unit squares. Numbers 1, 2, $\ldots$, $n$ are written in the squares. First, the number 1 is written in some square, then the number 2 is written in one of the neighboring squares, then the number 3 is written in one of the squares adjacent to those already occupied, and so on (the choice of the first square and the choice of a neighbor at each step are arbitrary). In how many ways can this be done?

A. H. Shen

Exploration

Let $a_n$ denote the number of admissible fillings.

For small values of $n$:

If $n=1$, there is only one square, hence $a_1=1$.

If $n=2$, we may place $1$ in either square. The second number is forced into the other square. Thus $a_2=2$.

If $n=3$, choose the position of $1$.

If $1$ is written in the middle square, then $2$ may go left or right, and afterward $3$ is forced. This gives $2$ fillings.

If $1$ is written at an end, then every subsequent choice is forced. Each end contributes $1$ filling.

Hence $a_3=4$.

The sequence $1,2,4$ suggests $a_n=2^{n-1}$.

To test this, consider $n=4$. If $1$ is placed in position $i$, the occupied cells always form a contiguous interval. At each step, the next number must be written immediately to the left or immediately to the right of this interval, provided such a square exists. Starting from position $i$, there are $i-1$ squares on the left and $n-i$ on the right. During the process we merely choose an order in which these left and right extensions are performed. For example, if $i=2$, there is one left extension and two right extensions; the number of possible orders is $\binom{3}{1}=3$. Summing over $i$ gives

$$\binom31+\binom32+\binom33+\binom30=8.$$

Again this equals $2^{3}$.

The crucial point is to justify rigorously that every filling corresponds uniquely to a sequence of left and right extensions, and that for a fixed starting position $i$ the number of such sequences is exactly $\binom{n-1}{i-1}$.

Problem Understanding

We have a row of $n$ unit squares. The numbers $1,2,\ldots,n$ are written one after another. The number $1$ may be placed in any square. After numbers $1,\ldots,k$ have been written, the occupied squares must form the set of squares containing these numbers, and the next number $k+1$ must be written in a square adjacent to at least one occupied square.

We must count all possible final fillings of the strip. This is a Type C problem, since a definite numerical quantity is sought.

The answer will be

$$a_n=2^{,n-1}.$$

Intuitively, once the position of $1$ is fixed, the occupied squares always form one interval. Each subsequent step enlarges that interval by one square on the left or on the right. The process is therefore encoded by a sequence of left and right extensions.

Proof Architecture

Lemma 1. After the numbers $1,\ldots,k$ have been written, the occupied squares form a contiguous interval of the strip. This follows because each new square is chosen adjacent to the already occupied set.

Lemma 2. If $1$ is written in position $i$, then every admissible filling corresponds uniquely to an ordering of the $i-1$ left expansions and the $n-i$ right expansions. This follows from Lemma 1, since at every step the interval can only be enlarged at one of its two ends.

Lemma 3. For fixed $i$, the number of admissible fillings equals $\binom{n-1}{i-1}$. An admissible filling is determined by the positions among the $n-1$ expansion steps at which the left expansions occur.

The hardest point is Lemma 2, because one must prove both existence and uniqueness of the correspondence between fillings and expansion sequences.

Solution

Let the squares be numbered from left to right by positions $1,2,\ldots,n$.

Suppose that after some stage the numbers $1,\ldots,k$ have been written.

We first prove that the occupied squares form a contiguous interval.

For $k=1$, the occupied set consists of a single square and is therefore an interval.

Assume the statement holds after the numbers $1,\ldots,k$ have been written. Let the occupied interval be $[L,R]$. The number $k+1$ must be written in a square adjacent to an occupied square. Since the strip is one-dimensional, every square adjacent to the interval $[L,R]$ is either $L-1$ or $R+1$, whenever such a square exists. After adding one of these squares, the occupied set becomes either $[L-1,R]$ or $[L,R+1]$, again an interval. By induction, the occupied squares always form a contiguous interval.

Now fix the position of the number $1$. Let it be position $i$.

There are exactly $i-1$ squares to the left of position $i$ and exactly $n-i$ squares to the right.

By the lemma just proved, each step enlarges the current interval by one square at its left end or at its right end. Eventually all $i-1$ left squares and all $n-i$ right squares must be added.

Hence every admissible filling determines a sequence of length $n-1$ consisting of

$$i-1$$

symbols $L$ and

$$n-i$$

symbols $R$,

where $L$ means that the interval was extended to the left and $R$ means that it was extended to the right.

Conversely, take any sequence of length $n-1$ containing exactly $i-1$ symbols $L$ and $n-i$ symbols $R$. Starting from position $i$, perform the indicated extensions one by one. Because there are exactly as many $L$ symbols as left squares and exactly as many $R$ symbols as right squares, the process fills the whole strip. At each stage the next square is adjacent to the current interval, so the construction is admissible.

Thus admissible fillings with $1$ in position $i$ are in one-to-one correspondence with sequences containing $i-1$ symbols $L$ and $n-i$ symbols $R$.

The number of such sequences is

$$\binom{n-1}{i-1}.$$

Therefore the total number of admissible fillings is

$$a_n = \sum_{i=1}^{n} \binom{n-1}{i-1}.$$

Setting $j=i-1$ gives

$$a_n = \sum_{j=0}^{n-1} \binom{n-1}{j}.$$

By the binomial theorem,

$$\sum_{j=0}^{n-1} \binom{n-1}{j} = (1+1)^{n-1} = 2^{,n-1}.$$

Hence the number of admissible fillings is

$$\boxed{2^{,n-1}}.$$

Verification of Key Steps

The first delicate step is the claim that the occupied squares always form an interval. A careless argument might assume this without proof. The inductive verification shows that if the occupied set is $[L,R]$, every square adjacent to it lies at one of its ends. No interior gap can ever be created.

The second delicate step is the bijection for fixed starting position $i$. One direction associates to a filling the sequence of left and right expansions. The reverse direction must also be checked. Given any sequence with $i-1$ symbols $L$ and $n-i$ symbols $R$, the interval never runs out of available squares prematurely. After $m$ left expansions, exactly the $m$ nearest squares to the left of $i$ have been occupied, so another left expansion is possible precisely until all $i-1$ left squares have been used. The same holds on the right. Thus every such sequence produces a valid filling.

A third possible source of error is counting. For fixed $i$, the process is not counted by $2^{n-1}$, because the numbers of left and right expansions are prescribed. The correct count is the number of placements of the $i-1$ left expansions among the $n-1$ steps, namely $\binom{n-1}{i-1}$.

Alternative Approaches

One may encode a filling directly by the position of $1$ together with the set of times at which the interval expands to the left. If $1$ is in position $i$, exactly $i-1$ left expansions occur. Choosing the moments of those expansions among the $n-1$ steps gives $\binom{n-1}{i-1}$ possibilities. Summing over all $i$ again yields

$$\sum_{i=1}^{n}\binom{n-1}{i-1}=2^{n-1}.$$

Another viewpoint is to reconstruct the process backward. In the final strip, the square containing $n$ must be an end of the occupied interval, hence an end square of the strip. Removing $n$, then $n-1$, and so on, successively removes end squares. The sequence of choices of left end or right end has length $n-1$, giving $2^{n-1}$ possibilities. This argument is shorter, but the interval-growth description makes the bijection with binary choices completely transparent.