When can player $A$ win this game

Question

There are $n$ positive integers on the blackboard.

For each round, player $A$ splits the integers into two groups, $X$ and $Y$. One of the groups can be empty. Player $B$ erases one group of integers, and reduces each remaining integers by one.

$A$ wins when one of the integers becomes $0$. B wins when every integer is erased.

Under what circumstances does $A$ have a must-win strategy?

I can think of the case where there are two $1$'s. $A$ just needs to keep these two $1$'s in separate groups, then he will win. But what kind of configurations can be reduced into this case?

Answer 1

(Fill in the gaps as needed. If you're stuck, show your work and explain why you're stuck.)

Let the integers be $ a_i$.
Claim: $A$ wins iff $\sum \frac{1}{2^{a_i}} \geq 1$

Proof: Suppose the condition holds.
Show that $A$ can split into 2 groups such that no matter what group $B$ chooses, the condition holds again at the next step. (See Useful lemma below.)
Then, because the game is finite, eventually we must have one term equal to 0, so A wins.

Suppose the condition doesn't holds.
Show that no matter how $A$ splits the 2 groups, B can find a group so that the condition doesn't hold at the next step.
Thus, B will eventually erase every number, so B wins.

---

Notes:

• Useful lemma: If we have positive integers $a_i$ such that $ \sum \frac{1}{2^{a_i}} \geq 1$, then we can find a subsequence such that $ \sum_{j \in J } \frac{1}{ 2^{a_j} } = 1 $.
• This lemma, suitably applied (IE needs 1 more step), ensures that we can split into 2 groups such that $\sum_{j\in J } \frac{2}{ 2^{a_j} } = 1 \geq 1, \sum_{j \not \in J } \frac{2}{ 2^{a_j} } \geq 1$.
• Note: The useful lemma isn't true if we merely have $ \sum b_i \geq 1$. We can't always find $ \sum_{j\in J} 2b_j \geq 1, \sum_{j \not \in J} 2b_j \geq 1$.
• Coming up with the invariance is pretty natural from studying the winning conditions, and how we go from one to the next.
• Hint to useful lemma: Greedy Algorithm. Arrange $a_i$ in non-decreasing order. Show that if $ \sum_{i=1}^T \frac{1}{ 2^{a_i} } = \frac{ b_T} { 2^{c_T}} < 1$, then $ a_{T+1} \leq \frac{1}{ 2^{c_T}}$, so $\sum_{i=1}^{T+1} \frac{1}{ 2^{a_i} } \leq 1 $. Since we eventually go over 1, hence at some point we must hit exactly 1.

Answer 2

Any time there are at least $2^k$ copies of $k$ $A$ can win. The approach is like your two $1$s. Split the copies evenly. $B$ will erase one half and leave $2^{k-1}$ copies of $k-1$.

If there is a $1$ and two $2$s $A$ can win. Put the $1$ in one group and the two $2$s in the other. If $B$ erases the group with the $1$, there will be two $1$s left and $A$ will win.

If there is a $1$, a $2$, and two $3$s $A$ can win. Put the $1$ in one group and the others in the second group.

This suggests a general criterion. For all the numbers $i$ on the board, compute $2^{-i}$ and add them up. If the sum is $1$ or greater $A$ can win. $A$ should divide the numbers into two groups that each have the sum of $2^{-1}$ at least $\frac 12$. Then when $B$ erases one group and subtracts $1$ from each of the remaining numbers, the sum will be at least $1$ again. There must then be a time that $0$ appears.

If the sum of the $2^i$ is less than $1$, one of the two groups will have a sum less than $\frac 12$ and the sum will be less than $1$ when each number is decreased. If $B$ always selects the group with sum less than $\frac 12$, no $0$ can then appear.