The integers from $1$ to $n$ are written, one on each of $n$ cards. The first player removes one card. Then the second player removes two cards with consecutive integers. After that the first player removes three cards with consecutive integers. Finally, the second player removes four cards with consecutive integers. What is th smallest value of $n$ for which the second player can ensure that he competes both his moves?
Problem
Source: Baltic Way 2018, Problem 10
Tags: combinatorics, sets of integers
XbenX
22.12.2018 17:18
Answer: $n=14$ works . First I'll show that $n=13$ doesen't work. Let the first player take card with number $4$ first. If the second player takes one of the pair $(8,9) $ or $(9,10)$ then the first player takes $(10,11,12)$ and $(5,6,7) $ respectively ,and it can't take 4 consecutive numbers. If the second player doesn't take $ (8,9)$ or $(9,10)$ then the first takes $(8,9,10)$ and then the second player is left with $(1,2,3) , (5,6,7) $ and $(11,12,13)$ ,so it can't take $4$ consecutive numbers. To show that $n=14$ works : Let the first player take card with number $k$ on his move . We have on one hand $k-1$ consecutive numbers , and the other $ 14-k$ . W.L.O.G let $k-1 \leq 14-k \Longleftrightarrow k \leq 7$ If $k-1 \geq 4$ then the second player takes $(k+1,k+2)$ , and now there are 2 groups $(1,2,3,4,\dots ,k) $ and $(k+3,k+4,\dots,14)$ each with more than $4$ elements , so second player can always take $4$ consecutive numbers. If $k=4$ or $3 $ then second player takes $(1,2)$ and if $k=1,2$ then second player takes $(3,4)$ and in both cases we are left with at least with $10$ consecutive numbers , and no matter of how one takes $3$ consecutive numbers , there are still left 4 consecutive numbers . $\blacksquare$