I Billard balls on table

[littlemathquark]

TL;DR Summary

Initially, the red table contains 111 billiard balls of different colors, while the white table is empty. Starting with the red table, operations are performed alternately on the tables. In each operation, one or more balls are selected from the current table and transferred to the other table. The same subset of balls cannot be selected more than once. Find the maximum number of operations that can be performed.

My solution like this but I'm not sure. What do you think?

In each operation, one or more balls are selected from the current table and transferred to the other table. The same subset of balls cannot be selected more than once. We want to find find the maximum number of operations that can be performed. If there are n balls in a set, the total number of subsets (including the empty subset) is: $2^n$

For the 111 balls on the red table, the total number of subsets is: $2^{111}$

However, the empty subset cannot be selected because at least one ball must be transferred in each operation. The maximum number of moves is derived by recognizing that each move alternates between tables and uses a unique subset. The alternation constraint effectively halves the number of usable subsets, leading to the formula $2^{111}−1$. Therefore, the total number of valid subsets must be $2^{111}−1$

 

[anuttarasammyak]

To understand the problem setting clear, could you show us an answer of an easy case for an example 2 or 3 balls instead of 111 ?
If empty subset is included, i.e.,”do nothing”, 2^n turns for n=0,1,2 is obvious.

 

[Office_Shredder]

I think it's interesting to consider why it's possible to move every subset over. For example if you have 3 balls and you move them go the white table one at a time, then you can move a pair back to the red table but you aren't allowed to move the last ball (and you have a lot of unused pairs). It's not the trickiest thing in the world but an algorithm for guaranteeing you get to do every subset seems like an important part of the solution.

 

[anuttarasammyak]

If empty subset is included, i.e.,”do nothing”, 2^n turns for n=0,1,2 is obvious

Mathematical induction. Say 2^n turn is right for n>0．
We add new member say A. Do the 2^n turns with no participation of A first. Reverse the 2^n same turns but this time let each subset include A. So we can perform 2^(n+1) turns.
empty set make it simple and beautiful.

 

[anuttarasammyak]

To understand the problem setting clear, could you show us an answer of an easy case for an example 2 or 3 balls instead of 111 ?

Here is the table for 2 balls case.

	Turn	Turn	Turn	Turn
｛　｝	1	2	3	4
φ			●
1		●
2				●
1,2	●

4 turns if we inovolve empty set. 2 turns if not. Do I understand the problem correctly ?


[EDIT] As pointed out in post #8, empty set be noted as $\emptyset$.

 

[littlemathquark]

Here is the table for 2 balls case.

	Turn	Turn	Turn	Turn
｛　｝	1	2	3	4
φ			●
1		●
2				●
1,2	●

4 turns if we inovolve empty set. 2 turns if not. Do I understand the problem correctly ?

Yes. I think my solution incorrect because for $3$ balls I found $6$ transfer.

 

[anuttarasammyak]

Thanks. So how we can make turn of empty set appear as late as possible, that is the question.

 

[pbuk]

Thanks. So how we can make turn of empty set appear as late as possible, that is the question.

However you decide to answer it, please use ∅, $\varnothing$, $\emptyset$ or {} to denote the empty set, not the greek letter phi.

 

[anuttarasammyak]

Yes. I think my solution incorrect because for 3 balls I found 6 transfer.

From your try, mine and post #4, I found it $2^n-2$ for n>1.

[EDIT]
$2^n$ transfers, which have to include {$\emptyset$}, is prohibited.
$2^n - 1$ transfers where $n\geq 2$ is not possible. If it were, the last transfer would be from Red to White. Finally Red has all the balls because in the tranfers any element appears $\frac{2^n}{2}$ i.e. even times. How can "Red give White (other than $\emptyset$ )" in the last transfer make Red has all the balls ?
$2^n-2$ transfers are possible and shown easily.

 

[littlemathquark]

Thank you.
Let us show that the total number of moves can not be $2^{111} − 1$. If the total numberof moves is $2^{111} − 1$ then all non-empty subsets of 111 element set should be selected.The total number of subsets containing given element is $2^{110}$, which is an even number. Therefore, at the end of all moves all balls should be on the red table. On the otherhand, since $2^{111} − 1$ is odd, the white table should contain at least one ball, a contradiction.Suppose that at the beginning the red table contains $n$ balls ${a_1, a_2, . . . , a_n}$ and the whitetable is empty. We show that the total number of moves can be equal to $2^{111} − 2$.By induction over $n$, let us show that for each $n ≥ 2$, it is possible to make $2n − 2$ moves such that the only not made move is ${a1}$ and after making all $2n − 2$ moves, all balls except $a1$ are on the red table and $a1$ is on the white table.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 apply $2k − 2$ moves to remaining $n = k$ balls by inductive hypothesis. After that make a move ${a_{k+1}}$ transferring ball $a_{k+1}$ to the white table.Then by inductive hypothesis the white table contains only two balls:$a_1$ and $a_{k+1}$. Let us make a move ${a_1, a_{k+1}}$. Finally we can repeat all $2k − 2$ moves made at the beginning by adding a ball $a_{k+1}$ to all moves. In total we will make $2k − 2 + 2 + 2k − 2 = 2k+1 − 2$ legal moves.

 

[anuttarasammyak]

I am not sure whether I catch your $2^n-2$ logic. Please find below my way for reference.

Let us include $\emptyset$ in transfer and construct the full sequence. Total n balls are named by number i.e., 1,2,3,...,n
n=1: {1},{$\emptyset$}
where the first transfer from Red to White is {1} and the second trasfer from White to Red is {$\emptyset$}.
n=2:{1},{$\emptyset$},{2},{1,2}
where the third transfer is {2} which is reverse of the second but include new member 2 and the fourth transfer is {1,2} which is reverse of the first but include new member 2.
This way, "Continue the reverse sequence but include new member in the subsets." was introduced in post #4. In this way
n=3:{1},{$\emptyset$},{2},{1,2},{1,2,3},{2,3},{3},{1,3}
n=4:{1},{$\emptyset$},{2},{1,2},{1,2,3},{2,3},{3},{1,3},{1,3,4},{3,4},{2,3,4},{1,2,3,4},{1,2,4},{2,4},{4},{1,4}
...
In general we can get $2^n$ transfer sequence for n balls in this way.

Read these acquired sequences in reverse order from the right end and stop at {$\emptyset$}.
Thus got $2^n-2$ sequences are what we're interested in.