Browse · MathNet
PrintBaltic Way shortlist
Baltic Way counting and probability
Problem
Positive integers from to 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 for which the second player can ensure that he completes both his moves?
Solution
Answer: .
At first, let's show that for the first player can ensure that after his second move no consecutive numbers are left. In the first move he can erase number and in the second move he can ensure that numbers , and are erased. No interval of length is left.
If the second player can use the following strategy. Let the first player erase number in his first move, because of symmetry assume that . If then the second player can erase and and there are two intervals left of length at least : and , but the first player can destroy at most one of them. But if , then the second player can erase numbers and in his first move and again there are two intervals left of length at least : and .
At first, let's show that for the first player can ensure that after his second move no consecutive numbers are left. In the first move he can erase number and in the second move he can ensure that numbers , and are erased. No interval of length is left.
If the second player can use the following strategy. Let the first player erase number in his first move, because of symmetry assume that . If then the second player can erase and and there are two intervals left of length at least : and , but the first player can destroy at most one of them. But if , then the second player can erase numbers and in his first move and again there are two intervals left of length at least : and .
Final answer
14
Techniques
Games / greedy algorithms