Maths Olympiad Prep

Library / /385 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Find the answer

Let n2n \geq 2 and mm be positive integers. mm ballot boxes are placed in a line. Two players AA and BB play by turns, beginning with AA, in the following manner. Each turn, AA chooses two boxes and places a ballot in each of them. Afterwards, BB chooses one of the boxes, and removes every ballot from it. AA wins if after some turn of BB, there exists a box containing nn ballots. For each nn, find the minimum value of mm such that AA can guarantee a win independently of how BB plays.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. **Establishing the minimum value of m m such that A A can guarantee a win:**

We need to show that m2n1+1 m \geq 2^{n-1} + 1 must hold. To do this, we will use a sum S S defined as follows:
S=i=1r2ai1 S = \sum_{i=1}^{r} 2^{a_i - 1}
where ai a_i represents the number of ballots in the i i -th non-empty box.

2. **Analyzing the changes in S S based on A A 's and B B 's moves:**

- If A A chooses two non-empty boxes with r r and s s ballots (assume rs r \geq s ), then after A A 's turn, S S increases by 2r1+2s1 2^{r-1} + 2^{s-1} . B B can then remove the box with r+1 r+1 ballots, decreasing S S by 2r 2^r . Since 2r2r1+2s1 2^r \geq 2^{r-1} + 2^{s-1} , S S does not increase.

- If A A chooses an empty box and a non-empty box with r r ballots, then B B can remove the box with r+1 r+1 ballots, decreasing S S by 2r2r1=2r1 2^r - 2^{r-1} = 2^{r-1} . Since 2r11 2^{r-1} \geq 1 , S S does not increase.

- If A A chooses two empty boxes, S S increases by 2. If some box contains more than one ballot, B B can remove it, decreasing S S by at least 2. Otherwise, B B removes a box with one ballot, and S S increases by 1.

3. **Bounding S S :**

Since B B always empties one box, A A can guarantee at most m1 m-1 boxes with one ballot. After this point, S S may not increase and thus S S is bounded above by m1 m-1 . If some box eventually contains n n ballots, then S2n1 S \geq 2^{n-1} . Combining this with Sm1 S \leq m-1 , we get:
m12n1    m2n1+1 m-1 \geq 2^{n-1} \implies m \geq 2^{n-1} + 1

4. **Constructing a winning strategy for A A when m=2n1+1 m = 2^{n-1} + 1 :**

- A A can first repeatedly choose two empty boxes until 2n1 2^{n-1} of them contain exactly one ballot.
- Then, A A chooses pairs of boxes containing one ballot. B B may remove at most one box at a time, so A A can obtain 2n2 2^{n-2} boxes with 2 ballots.
- Inductively, A A can obtain 2nk 2^{n-k} boxes with k k ballots, eventually leading to a box with n n ballots.

5. **Proving that A A cannot force a win for m=2n1 m = 2^{n-1} :**

- Assume B B always empties the box with the greatest number of ballots.
- By induction on k k , we show that after each of B B 's turns, there are at most 2nk1 2^{n-k} - 1 boxes with k k ballots.
- For k2 k \geq 2 , if a a boxes contain k k or more ballots, then at most 2nk+12a1 2^{n-k+1} - 2a - 1 boxes contain exactly k k ballots.
- If this inequality becomes false, consider the first moment where there are a a boxes with k k or more ballots and at least 2nk+12a 2^{n-k+1} - 2a with exactly k1 k-1 ballots.
- After A A 's turn, the number of boxes with k k or more ballots increases by \ell , and B B removes one, so the number of boxes with k k or more ballots increases by 1 \ell - 1 .
- This leads to a contradiction, proving that A A cannot guarantee a win for m=2n1 m = 2^{n-1} .

\blacksquare

The final answer is m=2n1+1 \boxed{ m = 2^{n-1} + 1 }

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.