Competition problem — Combinatorics

Library / /17 of 31

Combinatorics Difficulty 8.4 Shortlist Prove it Baltic Way

Positive integers from $1$ to $n$ are written on the blackboard. The first player chooses a number and erases it. Then the second player chooses two consecutive numbers and erases them. After that the first player chooses three consecutive numbers and erases them. And finally the second player chooses four consecutive numbers and erases them. What is the smallest value of $n$ for which the second player can ensure that he completes both his moves?

Solution

Answer: $n = 14$ .

At first, let's show that for $n = 13$ the first player can ensure that after his second move no $4$ consecutive numbers are left. In the first move he can erase number $4$ and in the second move he can ensure that numbers $8$ , $9$ and $10$ are erased. No interval of length $4$ is left.

If $n = 14$ the second player can use the following strategy. Let the first player erase number $k$ in his first move, because of symmetry assume that $k \le 7$ . If $k \ge 5$ then the second player can erase $k+1$ and $k+2$ and there are two intervals left of length at least $4$ : $1..(k-1)$ and $(k+3)..14$ , but the first player can destroy at most one of them. But if $k \le 4$ , then the second player can erase numbers $9$ and $10$ in his first move and again there are two intervals left of length at least $4$ : $(k+1)..8$ and $11..14$ .

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.