«Щёлк»:407 (от англ. Chomp) — математическая игра, заключающаяся в поедании двумя игроками плитки шоколада по определённым правилам. Современная геометрическая формулировка была придумана Дэвидом Гейлом в 1974 году, а более ранняя арифметическая — Фредериком Шухом в 1952 году. Англоязычное название Chomp — буквально «Чавк» (от «чавкать») — придумал Мартин Гарднер.
Геометрическая версия
Поле игры «Щёлк» — прямоугольная плитка шоколада; двое игроков по очереди выбирают одну дольку и съедают вместе со всеми дольками выше и правее её. Проигрывает тот игрок, который съедает «отравленную» левую нижнюю дольку:407.
Ниже приведён пример игры на поле 5 × 3: «отравленная» долька отмечена красным, а съедаемые игроком дольки — пунктиром.
В этом примере первый игрок вынужден съесть «отравленную» дольку и потому проигрывает.
Арифметическая версия
Игру «Щёлк» можно переформулировать арифметически: изначально загадано натуральное число n {displaystyle n} ; двое игроков по очереди называют делители n 1 , n 2 , … {displaystyle n_{1},n_{2},ldots } числа n {displaystyle n} , которые не являются кратными уже названных n i {displaystyle n_{i}} . Проигрывает игрок, вынужденный назвать число 1.
Для чисел N {displaystyle N} с факторизацией p k q l {displaystyle p^{k}q^{l}} , то есть имеющих только два простых делителя, арифметическая версия сводится к геометрической в прямоугольнике (k+1) × (l+1). При этом делителям соответствуют дольки, запрещённым делителям — съеденные дольки, числу 1 — «отравленная» долька, см. таблицу ниже.
Анализ игры
С точки зрения теории игр, «Щёлк» — беспристрастная детерминированная игра с полной информацией. Кроме того, в игре конечное число состояний, а потому из общих утверждений теории игр следует, что у одного из игроков должна быть выигрышная стратегия.
Заимствование стратегии позволяет показать, что выигрышная стратегия есть у первого игрока (кроме случая поля 1 × 1), однако доказательство неконструктивно. А именно, пусть у второго игрока существует выигрышная стратегия; докажем, что у первого игрока она также есть. Предположим, что первым ходом первый игрок съел только правую верхнюю дольку, и рассмотрел ход второго игрока, ведущий к выигрышной стратегии; тогда первый игрок может сам походить так своим первым ходом, тем самым «позаимствовав» стратегию второго игрока. Значит, у второго игрока не может быть выигрышной стратегии, а потому она есть у первого:410.
По состоянию на 1974 год известны выигрышные стратегии первого только для частных форм поля:408:
Также на компьютере найдены выигрышные стратегии для небольших размеров поля. Наименьший известный размер поля, для которого выигрышная стратегия не единственна — (8, 10).