Let and be positive integers. ballot boxes are placed in a line. Two players and play by turns, beginning with , in the following manner. Each turn, chooses two boxes and places a ballot in each of them. Afterwards, chooses one of the boxes, and removes every ballot from it. wins if after some turn of , there exists a box containing ballots. For each , find the minimum value of such that can guarantee a win independently of how plays.
Solution
1. **Establishing the minimum value of such that can guarantee a win:**
We need to show that must hold. To do this, we will use a sum defined as follows:
where represents the number of ballots in the -th non-empty box.
2. **Analyzing the changes in based on 's and 's moves:**
- If chooses two non-empty boxes with and ballots (assume ), then after 's turn, increases by . can then remove the box with ballots, decreasing by . Since , does not increase.
- If chooses an empty box and a non-empty box with ballots, then can remove the box with ballots, decreasing by . Since , does not increase.
- If chooses two empty boxes, increases by 2. If some box contains more than one ballot, can remove it, decreasing by at least 2. Otherwise, removes a box with one ballot, and increases by 1.
3. **Bounding :**
Since always empties one box, can guarantee at most boxes with one ballot. After this point, may not increase and thus is bounded above by . If some box eventually contains ballots, then . Combining this with , we get:
4. **Constructing a winning strategy for when :**
- can first repeatedly choose two empty boxes until of them contain exactly one ballot.
- Then, chooses pairs of boxes containing one ballot. may remove at most one box at a time, so can obtain boxes with 2 ballots.
- Inductively, can obtain boxes with ballots, eventually leading to a box with ballots.
5. **Proving that cannot force a win for :**
- Assume always empties the box with the greatest number of ballots.
- By induction on , we show that after each of 's turns, there are at most boxes with ballots.
- For , if boxes contain or more ballots, then at most boxes contain exactly ballots.
- If this inequality becomes false, consider the first moment where there are boxes with or more ballots and at least with exactly ballots.
- After 's turn, the number of boxes with or more ballots increases by , and removes one, so the number of boxes with or more ballots increases by .
- This leads to a contradiction, proving that cannot guarantee a win for .
The final answer is