Solution:
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}$.

Solution:
Denote by $\sigma_n$ the number of numbers on the blackboard after $n$ steps (thus $\sigma_0 = \sigma_1 = 1$, $\sigma_2 = 2$, $\sigma_3 = 3$, $\ldots$). Regard all points in the plane with coordinates $(m, n)$, where $m, n$ are defined as follows: the number $n$ is written on the blackboard after $m$ steps ($m, n$ are positive integers by the condition). At each node, i.e. each point with integer coordinates of the above type, write the number of occurrences of $n$ after $m$ steps. Thus the number written at $(3,2)$ will be the number of occurrences of $2$ directly after step $3$, which is $2$. Observe that the number at each node is equal to the number of ways to reach this node from the point $(0,1)$, walking from one node to another one step at the time, from left to right and either up or down, without going down to the horizontal axis.

(Since all zeroes are erased, we can never reach the horizontal axis.) For each $m$ we want to find the total number of paths $\sigma_m$, reaching the vertical line $y = m$.

If we were to remove the constraint that we are not allowed to step on the horizontal axis (i.e. that all zeroes are erased), we would get Pascal's triangle, and the total number of paths would be $2^m$. The binomial coefficient at each node is then the total number of paths to reach this node, without constraint.

We need to find and subtract the number of paths from $A(0,1)$ to a point $B$ among the allowed nodes, which go down to the horizontal axis. Choose such a path, and find a new one by reflecting in the horizontal axis the part between the starting point $(0,1)$ and the path's first contact with the horizontal axis. The original path and the reflected one will end at the same point (among the allowed nodes); the reflected one will start at $A'(0,-1)$. We have constructed a bijection between the original set of paths from $A$ to $B$ that reach down to the horizontal axis and the set of paths from $A'$ to $B$. Observe that starting at $A'$ we can get another copy of Pascal's triangle, which is the original one, translated two units down. It is easier to count the number of paths from $A'$ to $B$, since they are not subject to any constraints. Thus the number of "positive" paths from $A$ to the points above the horizontal axis for $m = 2k$ will be

$$\begin{gathered} \left(\binom{2k}{2k} + \binom{2k}{2k-1} + \cdots + \binom{2k}{k+1} + \binom{2k}{k}\right) - \\ - \left(\binom{2k}{2k} + \binom{2k}{2k-1} + \cdots + \binom{2k}{k+1}\right) = \binom{2k}{k} \end{gathered}$$

In case $m$ is odd, a modification of the above argument gives the answer obtained in Solution I.