
Problem 4. The number 1 is written on the blackboard. After that a sequence of numbers is created as follows: at each step each number $a$ on the blackboard is replaced by the numbers $a-1$ and $a+1$; if the number 0 occurs, it is erased immediately; if a number occurs more than once, all its occurrences are left on the blackboard. Thus the blackboard will show 1 after 0 steps; 2 after 1 step; 1,3 after 2 steps; 2, 2, 4 after 3 steps, and so on. How many numbers will there be on the blackboard after $n$ steps?


Solution I. Let $S$ be a set of different numbers, all of them less than $2^{n-1}$, and create two new sets as follows: $S_{1}$, consisting of all the numbers in $S$ except
the smallest one, and $S_{2}$, with elements the smallest element of $S$ and all the numbers we get by adding $2^{n-1}$ to each number in $S$. Note that if the number of elements in $S$ is $a$, then $S_{1}$ has $a-1$ elements, and $S_{2}$ has $a+1$ elements. This corresponds to the operations we are allowed to perform on the blackboard, if we throw away all empty sets. If we now operate simultaneously on the sets and on the numbers, then after $n$ steps the number of sets will be exactly equal to the number of numbers on the blackboard.

Let us see what the set operations look like. We must start with a set, consisting only of the number 0 . Next we get an empty set (thrown away), and the set $\{0,1\}$; next the sets $\{1\}$ and $\{0,2,3\}$; next again (an empty set and) $\{1,5\},\{2,3\},\{0,4,6,7\}$, etc.

It is now fairly easy to prove by induction that after $n$ steps

(1) each number less than $2^{n}$ appears in exactly one set;

(2) the number of elements in the sets corresponds exactly to the numbers on the blackboard;

(3) if the numbers in each set are written in increasing order, then the difference between two neighbours is a power of 2 ; thus the binary representations of two neighbours differ in exactly one position (in the binary system the example above looks like this: $\{0\} ;\{0,1\} ;\{01\},\{00,10,11\} ;\{001,101\},\{010,011\}$, $\{000,100,110,111\}) ;$

(4) if $k$ is the number of ones in the binary code of the smallest number of a set, and $l$ the number of ones in the largest number of the same set, then $k+l=n$; (5) each set contains exactly one number with $\left\lfloor\frac{n}{2}\right\rfloor$ ones.

The last property tells us that the number of sets after $n$ steps is equal to the number of numbers such that their binary representation contains exactly $\left\lfloor\frac{n}{2}\right\rfloor$ ones out of $n$ digits, i.e. the number of numbers on the blackboard after $n$ steps will be equal to $\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}$.
