62nd Ukrainian National Mathematical Olympiad, Third Round, Second Tour

Question

Monica and Bogdan are playing a game that depends on two positive integers n and k. First, Monica chooses and writes k positive numbers. Bogdan wins if he manages to mark n points on the plane so that for each number m written by Monica, there are two marked points at a distance precisely m, otherwise Monica wins. Find out, depending on n and k, who wins, if both players play optimally. (Fedir Yudin)

Accepted Answer

If k < n, Bogdan can choose n points on a line so that the distance between the first and second points is equal to the first written number, between the second and third to the second written number, and so on. If k n, Monica can choose numbers 2^0, 2^1, , 2^k-1. Suppose that Bogdan can win. Then for each i = 0, k-1 connect with a segment two points at a distance 2^i. As k n, this graph contains a cycle. As the length of the longest segment in this cycle is larger than the sum of the lengths of other segments, we get a contradiction.