Let $n \geq 2$ and $m$ be positive integers. $m$ ballot boxes are placed in a line. Two players $A$ and $B$ play by turns, beginning with $A$, in the following manner. Each turn, $A$ chooses two boxes and places a ballot in each of them. Afterwards, $B$ chooses one of the boxes, and removes every ballot from it. $A$ wins if after some turn of $B$, there exists a box containing $n$ ballots. For each $n$, find the minimum value of $m$ such that $A$ can guarantee a win independently of how $B$ plays.
Problem
Source: Mexico National Olympiad 2017, Problem 6
Tags: combinatorics
12.11.2017 13:19
P.S. The above solution still have an unclear part about "dead" box, will update if I know any clearer way to deal with it.
12.11.2017 14:55
@ThE-dArK-lOrD: Nice approach! I think I can fix the problem with "dead" boxes, hope this is correct: Let's say the strategy of $B$ is that if $A$ chooses two boxes with $x,y$ ballots and $B$ will remove ballots in box that has greater number of ballots than the other. We prove that with $B$ using such strategy, we need at least $2^{n-1}+1$ boxes for $A$ to obtain a box with $n$ ballots. First, we redefine $S= \sum_{i=1}^m f(i)$ where $f(i)= \begin{cases} 0 & \text{if ith box has no ballot}, \\ 2^k & \text{if ith box has k ballots.} \end{cases}$ From this, we observe that in some turn, if $A$ chooses two boxes with $x,y$ ballots: If $x=y \ge 1$ or $x=0,y=1$ or $x=1,y=0$ then $S$ does not change. If $x \ne y, x,y \ge 1$ or $x=0,y \ge 2$ or $x \ge 2, y=0$ then $S$ decreases. If $x=y=0$ then $2$ is added to $S$. Thus, note that we can add $2$ to $S$ for at most $m-1$ times (since we can turn at most $m-1$ boxes from having no ballot to have $1$ ballot by letting $A$ chooses two empty boxes) and other cases do not increase our $S$. Hence, we find $S \le 2(m-1)$. On the other hand, we want the result to have a box of $n$ ballots so $S \ge 2^n$ after some turns. Hence, $2^n \le 2(m-1)$ or $m \ge 2^{n-1}+1$. And for $2^{n-1}+1$ we can construct winning strategy for $A$ (by simply following above observation). Thus, the answer is $m=2^{n-1}+1$.
13.11.2017 06:33
I am the author of this problem, here are the two official solutions given for it. The first one is very similar to those already posted here. The second one is the solution I found originally.
14.10.2022 12:05
So B can empty the box A doesn't choose in one turn?