Игра на вычеркивание чисел: олимпиадная задача по теории алгоритмов
Задача
Двое играют в следующую игру. Каждый игрок по очереди вычеркивает 9 чисел (по своему выбору) из последовательности 1,2,...,100,101. После одиннадцати таких вычеркиваний останутся 2 числа. Первому игроку присуждается столько очков, какова разница между этими оставшимися числами. Доказать, что первый игрок всегда сможет набрать по крайней мере 55 очков, как бы ни играл второй.
Решение
Первым ходом нужно вычеркнуть 9 чисел от 47 до 55. Остальные числа разбиваются на пары: 1 - 56, 2 - 57,..., 46 - 101. После каждого хода второго игрока, первый может вычеркнуть числа таким образом, чтобы в каждой паре было вычеркнуто либо оба числа, либо ни одного. Таким образом, в конце останется пара чисел, разность которых равна 55.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь