Олимпиадная задача про стратегию в домино: теория алгоритмов для 7–9 классов
В коробке лежит полный набор костей домино. Два игрока по очереди выбирают из коробки по одной кости и выкладывают их на стол, прикладывая к уже выложенной цепочке с любой из двух сторон по правилам домино. Проигрывает тот, кто не может сделать очередной ход. Кто выиграет при правильной игре?
Показать ответ
Выигрывает первый игрок.
Разобрать решение
Опишем выигрышную стратегию I игрока. Вначале он выкладывает на стол0:0,
II отвечает0:a , тогда I выкладывает кость a:a . Теперь II делает
ход либо0:n , либо a:n . В первом случае I выкладывает кость n:a
к концу, содержащему n , во втором – n:0к тому же концу. Тогда
после хода I игрока на концах цепочки будут 0 или a . Это же произойдет
после того, как на ход II игрока0:m ( a:m ) I ответит m:a (
m:0). Кости вида0:n и a:n ( n
0,a ) разбиваются на пары,
поэтому последний ход останется за первым игроком.
Обсуждение
0Комментариев пока нет.