Олимпиадная задача о фишке на поле 1×100 — теория алгоритмов
Задача
Игровое поле представляет собой горизонтальную полоску размером 1×100 клеток. В самой левой клетке стоит фишка. Двое по очереди двигают фишку вправо, причём за один ход разрешается сдвинуть фишку вправо на расстояние от 1 до 10 клеток. Проигрывает тот, кто не может сделать ход (то есть перед его ходом фишка находится в самой правой клетке). Кто выиграет при правильной игре?
Решение
Выигрышная стратегия второго игрока такова: после каждого хода первого игрока на k клеток вправо сдвигать фишку на 11 – k клеток. Таким образом, после пары ходов, которые сделали первый и второй игроки, фишка сдвинется вправо на 11 клеток. В начальном положении справа от фишки было 99 пустых клеток. Поэтому через 9 пар ходов первого и второго игроков фишка будет находиться в самой правой клетке.
Ответ
Второй.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь