Let $N$ be a positive integer. Two persons play the following game. The first player writes a list of positive integers not greater than $25$, not necessarily different, such that their sum is at least $200$. The second player wins if he can select some of these numbers so that their sum $S$ satisfies the condition $200-N\le S\le 200+N$. What is the smallest value of $N$ for which the second player has a winning strategy?
Problem
Source: Baltic Way 2002
Tags: combinatorics proposed, combinatorics
09.01.2011 21:55
I reckon that $N_{0} = 11$. If player 1 writes 23 six times, 24 once and 25 twice, the sum is 212. By subtracting 23, P2 can get to $200 - 11$, but it is clearly impossible to get any closer (as there is nothing smaller than 23 to subtract). This will give P1 victory if $N \leq 10$. Now, suppose that $N = 11$. To win, player 1 needs to write numbers, in such a way that player 2 cannot land in the region $200 - 11 \leq S \leq 200 + 11$, which is of size 23. Now, suppose that P1 has written any numbers less than or equal to 23. Player 2 can write all of the numbers in increasing order, until 200 is surpassed for the first time. Clearly, if the greatest partial sum is greater than or equal to $200 - 11$, then player 2 can take those numbers, and likewise, if the smallest number is less than or equal to $200 + 11$, then player 2 can take those numbers. Therefore, Player 1 must jump past all 23 numbers in that range in one number. But this means that the maximum he can get to is $200 + 13$, as he started with at most $200 - 12$ and can jump at most 25, and otherwise the total is at $200 + 12$. In the former case, P2 can remove the smallest number (which is less than or equal to 23) and win, and in the latter, he can remove either the smallest number besides 1 (which is not 25) or remove two 1s. If there is only one 1 and then 25s to remove, the total cannot be $213 \neq 1 \mod 25$. Otherwise, all the numbers are 24 or 25. However, it is clearly impossible to reach 212 (which is 12 mod 25, so thirteen 24s are needed, making the total too big), so the first time 200 is surpassed (using the same ordering principle as before), a 24 can be removed to bring the total within the region (if it is not there already). So with $N \leq 10$ player 1 can use the numbers given at the start, and if $N = 11$ player 2 can always win.