Initially, one of the two boxes on the table is empty and the other contains $29$ different colored marbles. By starting with the full box and performing moves in order, in each move, one or more marbles are selected from that box and transferred to the other box. At most, how many moves can be made without selecting the same set of marbles more than once?
Problem
Source: Turkey National Mathematical Olympiad 2021 P1
Tags: combinatorics
electrovector
06.01.2022 19:33
We will show that for $n$ different marbles we will have $2^n-2$ moves. It is obvious that we cannot have more than $2^n-1$ moves.
Proof
Assume that we can make $2^n-1$ moves. Label the initial boxes with $A$ and $B$ such that $A$ is the full box and label marbles with $1, 2,... n$. Each move will include a unique nonempty subset of these numbers. There are $2^n-1$ such sets thus all sets will be used. Since we have an odd number of moves the last move will be from $A$ to $B$ so at the end $B$ won't be empty. However for marble $i$, we will make $2^{n-1}$ which is even. That's why all marbles will end up in $A$ at the end which is a contradiction.
Construction
Now I will prove a construction for $2^n-2$ by induction. Our induction hypothesis is a little bit complicated so I will write it down clearly: We can make moves to all subsets other than the subset $\{n \}$ and at the end $n$ will end up on $B$ and the others will be in $A$. That will give us $2^n-2$ different subsets which means $2^n-2$ moves.
It is not hard to check cases where $n$ equals to 2 and 3.
Assume it is true for $n$ and let's try to prove it for $n+1$. Let's apply the induction hypothesis to the numbers $1, 2, ..., n$. After that move $n+1$ to $B$ and move the subset $\{n, n+1\}$ back to $A$. After that apply the exact induction hypothesis for $\{1, 2, ..., n\}$ but put ${n+1}$ into all those subsets. It is clear that we have $2^{n+1}-2$ different moves and one subset containing exactly one element (which is the subset $\{n\}$) is not used. $n$ will be in $B$ and all other marbles will be in $A$. Since all marbles are equal we can change $n$ and $n+1$ and all process will still be true and we are done.
Cookierookie
07.01.2022 15:36
electrovector wrote: Construction Now I will prove a construction for $2^n-2$ by induction. Our induction hypothesis is a little bit complicated so I will write it down clearly: We can make moves to all subsets other than the subset $\{n \}$ and at the end $n$ will end up on $B$ and the others will be in $A$. That will give us $2^n-2$ different subsets which means $2^n-2$ moves. It is not hard to check cases where $n$ equals to 2 and 3. Assume it is true for $n$ and let's try to prove it for $n+1$. Let's apply the induction hypothesis to the numbers $1, 2, ..., n$. After that move $n+1$ to $B$ and move the subset $\{n, n+1\}$ back to $A$. After that apply the exact induction hypothesis for $\{1, 2, ..., n\}$ but put ${n+1}$ into all those subsets. It is clear that we have $2^{n+1}-2$ different moves and one subset containing exactly one element (which is the subset $\{n\}$) is not used. $n$ will be in $B$ and all other marbles will be in $A$. Since all marbles are equal we can change $n$ and $n+1$ and all process will still be true and we are done. Here is another construction without using induction: Denote the marbels by $a,b,c,d,...,z$ (There are exactly 29 letters in the Turkish alphabet ). Let $A$ be the subset of the Marbels such that it contains every marble except $a$ and $b$, and define $S_{k}$ to be the set of all subsets of $A$ that have size $k$. Since $|A| = 27$ which is odd, it follows that there is a one-to-one bijection $\psi$ which maps the elements of $S_{k}$ with $S_{27-k}$. Consider the case when every marble is in one box. Choose a subset $B$ of $A$ which is not chosen and has $|B| > 14$, first carry $\{a,b\} \cup B$, take back $B \cup \{b\}$, rethrow $\psi(B) \cup \{b\}$ and again retreat $\psi(B) \cup \{a,b\}$. Carry out this procedure until you can't which means either all the marbles were not in one box or there weren't any subsets $B$ remaining, since the procedure ends again with all marbels in one box it means that you will achieve $B \cup \{b\}, B \cup \{a,b\}$ for all subsets $B$ of $A$. Now do a similiar argument with moves $B \cup \{a\}$, $B$, $\psi(B)$, $\psi(B) \cup \{a\}$, this time giving us $B, B \cup \{a\}$ for all subsets $B$ of $A$, Except the cases when $B$ and $\psi(B)$ are empty this time because we cannot make moves with empty sets, so we don't have $\{\}, \{c,d,...\}, \{a\}, \{a,c,d,...\}$ right now. But this is not a problem because we can now make the moves $\{a,c,d,...\}$, $\{a\}$ $\qedsymbol$