Turkish Mathematical Olympiad

Answer: $2^{29}-2$.

Let us show that the total number of moves cannot be $2^{29}-1$. If the total number of moves is $2^{29}-1$ then all non-empty subsets of a $29$ element set should be selected. The total number of subsets containing a given element is $2^{28}$, which is an even number. Therefore, at the end of all moves all balls should be in the box which was full at the beginning. On the other hand, since $2^{29}-1$ is odd, a box which was empty at the beginning should contain at least one ball, a contradiction.

Suppose that at the beginning box $A$ contains $n$ balls $\{a_1, a_2, \dots, a_n\}$ and box $B$ is empty. We show that the total number of moves can be equal to $2^{29}-2$.

Solution 1:

Let us prove the following lemma.

Lemma: Let $n > 2$. It is possible to make all moves containing a fixed ball $a$ and after these $2^{n-1}$ moves return to the initial position with empty $B$.

Proof: We will use induction over $n$. If $n=3$ it can be done by applying moves $\{a_1, a_2\}$, $\{a_1\}$, $\{a_1, a_3\}$, $\{a_1, a_2, a_3\}$.

Now suppose that for $n=k$ the inductive hypothesis is correct. Let us fix balls $a$ and $b$. By inductive hypothesis, by applying all $2^{n-2}$ moves containing $a$ and not containing $b$ it is possible to return to the initial position. After that, again by inductive hypothesis, by applying all $2^{n-2}$ moves containing both $a$ and $b$ it is possible to return to the initial position. Thus, by applying all $2^{n-1}$ moves containing $a$ we return to the initial position. The lemma is proved.

By the lemma, we can make all moves containing ball $a_1$ and return to the initial position, after that make all moves not containing $a_1$ but containing $a_2$ and return to the initial position, after that make all moves not containing $a_1, a_2$ but containing $a_3$ and return to the initial position, ..., and make all moves not containing $a_1, a_2, ..., a_{26}$ but containing $a_{27}$ and return to the initial position. Finally, by making two moves with ball groups $\{a_{28}, a_{29}\}$ and $\{a_{28}\}$ we will make all possible moves except a move $\{a_{29}\}$. Done.

Solution 2:

By induction over $n$, let us show that for each $n \ge 2$, it is possible to make $2^n - 2$ moves such that the only not made move is $\{a_1\}$ and after making all $2^n - 2$ moves, all balls except $a_1$ are in box $A$ and $a_1$ is in box $B$.

If $n=2$ it can be done by applying moves $\{a_1, a_2\}, \{a_2\}$.

Now suppose that for $n=k$ the inductive hypothesis is correct and $n=k+1$. Let us separate ball $a_{k+1}$ and to the remaining $n=k$ balls apply $2^k-2$ moves existing by inductive hypothesis. After that make a move $\{a_{k+1}\}$ transferring ball $a_{k+1}$ to box $B$. By inductive hypothesis the box will contain two balls: $a_1$ and $a_{k+1}$. Let us make a move $\{a_1, a_{k+1}\}$. Finally, we can repeat all $2^k-2$ moves made at the beginning by adding ball $a_{k+1}$ to all of them. In total we will make $2^k-2+2+2^k-2=2^{k+1}-2$ legal moves. Done.