На доске написаны числа 1, 2, 3, ..., 13. Два игрока по очереди стирают по одному числу, пока не останется три числа. Если эти три числа могут быть сторонами невырожденного треугольника, то выигрывает первый игрок, если нет - то второй. У кого из игроков есть выигрышная стратегия?

Предыдущий
вопрос Следующий
вопрос

Пусть у нас на доске остались числа a, b, c, где a < b < c. Для того чтобы эти числа могли быть сторонами треугольника, необходимо и достаточно, чтобы выполнялось неравенство a + b > c.

Если оставшиеся на доске числа являются концами арифметической прогрессии с шагом d (то есть b - a = c - b = d), то игрок, у которого очередь делать последний ход, может победить, просто стирая центральные элементы арифметической прогрессии после хода противника. Действительно, после хода противника рассмотрим самое маленькое число, стоящее на доске (пусть это a). Оно может стоять только в начале или в конце арифметической прогрессии, не содержащей других элементов изначального набора (которая изначально была [1, 2, ..., 13]). Поскольку прогрессия содержит нечетное число элементов (так как после хода противника остается четное число элементов), предположим, что на доске стоит b (которое не равно началу арифметической прогрессии). Тогда на доске стоит еще c - это следующее число после b в прогрессии. После удаления из прогрессии числа, стоящего перед a, и числа, стоящего после c, получаем прогрессию длины (13 - 3)/2 = 5, что противоречит тому, что число элементов прогрессии нечетное. Значит, на доске стоит элемент, который равен началу прогрессии (то есть a), и следующий за ним. Итак, набор [a, b, b + d] является прогрессией, удаление центрального элемента которой позволяет победить после следующего хода.

Так как изначально на доске 13 элементов, не являющихся в прогрессией из трех элементов, арифметической с шагом 1, выигрывает первый игрок.