Chomp ©

Поле — это точка пересечения строки и столбца, обозначенная как (row, col).
Плитка – это картинка на некоторых полях.
Позиция состоит из всех полей с плитками.

Начнем с простых задач, т.е. небольших позиций. Чтобы их создать, мы нажимаем «Компьютер: Выкл.». Если мы затем нажмем на (2,1), останется только один ряд плиток.

Что может сделать следующий игрок, т.е. ваш соперник?
- При нажатии на (1,2) остается только плитка на (1,1), поэтому вы проиграли.

Затем давайте нажмем «Новая игра» и на (3,1) и (2,2), чтобы получить одну плитку в строке 2 и всю строку 1.

Что может сделать следующий игрок?
- При нажатии на (1,3) остается только три плитки. Видите ли вы, что у вас нет шансов?

Давайте нажмем на «Новую игру» и нажмем на (3,1) и (2,3).

Что может сделать следующий игрок?
- Ваш противник может нажать на (1,4). Видите ли вы, что у вас нет шансов?

Можете ли вы подытожить, в каких позициях с плитками всего в 2 ряда у вас нет шансов на победу в игре?
- Если в верхнем ряду на одну плитку больше, чем во 2-м ряду, то что бы вы ни делали, ваш соперник всегда может сделать ход так, чтобы в верхнем ряду было на одну плитку больше, чем во 2-м ряду. Затем, что бы вы ни делали, в конечном итоге вам придется выбрать плитку (1,1) и проиграть игру.

Если щелкнуть плитку, все плитки ниже и справа также удаляются. Это правило имеет симметрию; Т.е. вся игра имеет следующую симметрию: если мы меняем местами строки и столбцы, то правило остается прежним: все плитки справа становятся всеми плитками ниже, а все плитки ниже становятся всеми плитками справа от удаленной плитки. Другими словами, если мы отразим положение вдоль линии, проходящей через (1,1) и (2,2), то новая позиция может выглядеть по-другому, но она будет иметь тот же статус. Выигрышным ходом будет тот же ход, только зеркальный.

Позиция с 3 плитками в первом ряду и 2 плитками во втором ряду, как мы знаем, безнадежна. Какие плитки есть у зеркальных позиций?
- После зеркального отражения у него есть 3 плитки в левой колонке и 2 плитки во 2-й колонке.

Мы знаем все безнадежные позиции, в которых плитки находятся только в первых двух рядах. Что симметрия говорит нам обо всех безнадежных позициях с плитками только в первых двух столбцах?
- Безнадежные позиции с плитками в первых двух колонках — это те, где в первой колонке на одну плитку больше, чем во второй.

Вот еще одна позиция без шансов: нажмите «Новая игра» и на (4,1), (2,2) и (1,4).

Если соперник делает ход в этой позиции, что вы ответите?
- Вам нужно убедиться, что после вашего хода верхний ряд и первый столбец снова имеют одинаковую длину. Повторяя эту схему, противник в конечном итоге должен будет взять плитку (1,1) и проиграть.

Таким образом, если в первом ряду и первом столбце одинаковое количество плиток, а других плиток нет, то позиция безнадежна. Какие позиции можно изменить на такую позицию?
- Если позиция имеет одинаковое количество строк и столбцов, независимо от того, сколько плиток есть где-либо еще: ход на (2,2) оставляет только первый ряд и первую колонку одинаковой длины, не оставляя сопернику шансов. Таким образом, если позиция имеет такое же количество фишек в верхнем ряду, как и в левом столбце, то вы играете на (2,2) и выигрываете игру.

Чтобы хорошо играть в Chomp, нужно знать о выигрышных и проигрышных позициях. Выигрышная позиция – это позиция, в которой можно закрепить победу, если играть оптимально, независимо от того, что делает другая сторона. Проигрышная позиция – это позиция, в которой у одного нет шансов, если другая сторона играет оптимально. Следующие пункты в математике называются определением. В Chomp проигрышные и выигрышные позиции определяются через эти 3 пункта:
1. Если осталась только одна плитка (в левом верхнем углу), то это проигрышная позиция.
2. Позиция является выигрышной, если существует ход, который приводит к проигрышной позиции для соперника.
3. Позиция является проигрышной, если каждый ход приводит к выигрышной позиции для соперника.
На первый взгляд вышеперечисленные пункты могут показаться бесполезными, потому что выигрышные позиции объясняются проигрышными позициями, а убыточные позиции – выигрышными. Тем не менее, определение основано на выполнении ходов, и каждая последовательность ходов в конечном итоге приводит к одной позиции, которая, согласно пункту 1, является проигрышной.

Возможно ли, что существуют позиции, в которых ни одна из сторон не может добиться победы? (сложно)
- Мы сформулируем небольшую теорему и докажем ее. Доказательство покажет нам, как достичь идеальной силы игры. Доказательство — это индуктивное доказательство, в котором мы показываем, что утверждение, которое мы хотим доказать, истинно для одной плитки, а затем показывается, что если оно верно для любого числа N плиток, то оно также должно быть истинно для еще одной плитки, т.е. N+1 плитки. Поскольку это утверждение верно для N=1 плитки, оно должно быть верно для N+1=1+1=2 плиток. Но если это верно для N=2, то оно должно быть также верно для N+1=2+1=3 плиток и так далее; т.е. для любого количества плиток.
- Лемма (малая теорема): Каждая позиция является либо выигрышной, либо проигрышной.
- Индукционное доказательство:
- Индукционная база: Если позиция имеет только одну плитку, то эта плитка находится в верхнем левом углу, и тогда позиция является проигрышной в соответствии с правилом Chomp (показывая, что лемма истинна, если присутствует только N=1 плитка).
- Гипотеза индукции: Мы предполагаем, что лемма справедлива для всех позиций с N плитками, т.е. позиции с 1,2,..., N плитками являются либо выигрышными, либо проигрышными.
- Шаг индукции: Теперь мы хотим показать, что и тогда все позиции с N+1 плитками должны быть либо проигрышными, либо выигрышными.
- В следующем P — произвольная позиция с N+1 плитками. Если P уменьшается на один ход, то новая позиция должна иметь ≤N плиток, то есть это проигрышная или выигрышная позиция в соответствии с гипотезой индукции. Если P можно свести за один ход к убыточной позиции, то P является выигрышной позицией. Если нет, то P можно сократить за один ход только до выигрышной позиции. Но если позиция может быть сокращена на ходу только до выигрышной позиции, то P должна быть проигрышной позицией. Это доказывает, что P (имея N+1 фишек) является либо выигрышной, либо проигрышной позицией. Это показывает, что все позиции (с N+2,N+3,... плитки) являются либо выигрышными, либо убыточными позициями.
  
  Окончание проверки ∎
- Дополнительный комментарий: Шаг индукции предоставляет метод для определения для всех позиций (до определенного размера), являются ли они выигрышными или убыточными позициями. Он определяется следующим:
  
  Вы начинаете с N=1 и обозначаете эту позицию как убыточную. Затем вы определяете состояние всех позиций с помощью 2 плиток, затем с помощью 3 плиток и так далее, каждый раз используя знания о состоянии меньших позиций и добавляя вновь найденную убыточную позицию в список известных убыточных позиций.
- Это очень эффективный способ найти все выигрышные и проигрышные позиции с точностью до определенного размера. По мере того, как цифры становятся все больше в размере, компьютерная программа будет полезна. Необходимые ингредиенты следующие:
  - Процедура, которая может эффективно создавать все позиции N тайлов, зная все позиции менее N тайлов
  - Процедура, которая может эффективно проверить, может ли позиция быть уменьшена до другой заданной позиции.
  Мы оставим вам возможность подумать над этим подробнее и, возможно, написать такую компьютерную программу.

Сколько проигрышных и выигрышных позиций имеют ровно 2 плитки?
- Есть только две возможные позиции, которые имеют ровно 2 плитки, 2 плитки в верхнем ряду или две плитки вдоль левого столбца. Обе эти позиции являются выигрышными.

В скольких проигрышных и выигрышных позициях ровно 3 плитки?
- Всего есть 3 возможные позиции, которые имеют ровно 3 плитки. Они состоят из 2 выигрышных позиций, и 1 убыточной. Можете ли вы разобраться, какие это позиции?

В скольких проигрышных и выигрышных позициях ровно 4 плитки?
- Есть 5 возможных позиций, которые имеют ровно 4 плитки. Все эти позиции являются выигрышными.

Сколько проигрышных и выигрышных позиций имеют ровно 5 фишек?
- Всего есть 7 возможных позиций, которые имеют ровно 5 плиток. Из этих позиций 3 являются убыточными позициями и 4 – прибыльными. Сможете ли вы разобраться, какие именно?

Прямоугольные позиции являются выигрышными или убыточными?
- Следующая лемма отвечает на этот вопрос. Доказательство – это доказательство существования. Он будет только доказывать существование выигрышного хода, не показывая, что это за ход. Тем не менее, знание леммы полезно для вашей игры, как описано ниже.
- Лемма: Все прямоугольные позиции, кроме позиции 1 плитки, являются выигрышными.
- Доказательство: Чтобы показать, что это так, нам нужно рассмотреть два возможных случая:
  1. Удаление плитки в правом нижнем углу доски является выигрышным ходом.
  2. Удаление плитки в правом нижнем углу не является выигрышным ходом.
- Если случай 1 истинен, то это означает, что прямоугольник является выигрышной позицией, и это поддерживает лемму.
- Если случай 1 не верен, то нам нужно рассмотреть случай 2. Согласно доказательству, которое мы сделали ранее, позиция, полученная в результате удаления плитки в правом нижнем углу, должна быть выигрышной, что означает, что у нее должен быть существующий выигрышный ход. Но, поскольку каждый ход в прямоугольнике удаляет плитку в правом нижнем углу, проигрышная позиция, полученная в результате 2-го хода (выигрышного хода), одинакова независимо от того, был ли выигрышный ход сыгран после углового хода или вместо углового. Это означает, что выигрышный ход мог быть разыгран сразу, тем самым доказывая, что выигрышный ход существовал для прямоугольной позиции.
- Окончание проверки ∎
- Дополнительные комментарии: Хотя лемма не говорит нам, что является выигрышным ходом, уже полезно знать, что прямоугольные позиции являются выигрышными. Поэтому не следует делать ход, который создает прямоугольную позицию (за исключением позиции 1х1).

Можете ли вы определить для любой квадратной доски, какой ход является выигрышным?
- Для всех квадратов размера >1 единственным выигрышным ходом является ON (2,2).

Для каких позиций, подобных квадрату, один и тот же ход является выигрышным?
- Ход (2,2) также является выигрышным ходом для любой позиции, где 1-й ряд и 1-й столбец имеют одинаковую длину.

Может ли позиция иметь более одного выигрышного хода?
- Да, в позиции может быть более одного выигрышного хода. Рассмотрим следующую позицию:
  
  ###
  ##
  #
  
  Эта позиция на борде имеет 3 различных выигрышных хода, которые могут быть сделаны. Можете ли вы определить, что это такое?

Общая стратегия для выигрыша в Chomp заключается в том, чтобы создать убыточные позиции для своего оппонента, чтобы у него не было шансов. Мы также хотим избежать создания выигрышных позиций, которые соперник может превратить обратно в проигрышные для нас.

Ключ к победе заключается в том, чтобы знать как можно больше проигрышных позиций и определить, как их создать, прежде чем это сделает ваш оппонент. Рассмотрим следующую возможную доску, которая является заведомо убыточной позицией:

#######
###
###
#
#
Рисунок 1

Какие все позиции можно превратить в эту убыточную позицию за один ход?

Вышеуказанная проигрышная позиция может возникнуть в результате любого движения, отмеченного знаком + ниже:

#######+
###
###
#
#

#######
###+
###
#
#

#######
###
###
#+
#

#######
###
###
#
#
+

Рисунок 2

Все эти ходы расположены в вырезанных углах. Любое такое перемещение + также вырежет плитки, которые могут появиться на изображениях ниже с помощью ?:

#######+?
###
###
#
#

#######
###+???
###????
#
#

#######
###
###
#+?
#??

#######
###
###
#
#
+
?

Рисунок 3

Плитки + являются обязательными, а ? Плитки не являются обязательными. В левой выигрышной позиции верхний ряд может быть произвольно расширен вправо с помощью большего количества '?', а в правой выигрышной позиции первый столбец может быть произвольно расширен вниз с помощью большего количества '?'. Все эти позиции также являются выигрышными. Если мы должны сделать ход в такой позиции, мы возьмем фишку +, и, следовательно, все ? Соединенные плитки также будут удалены, что приведет к убыточной позиции, с которой мы начали.

Есть ли больше выигрышных или больше проигрышных позиций?
- Для каждой убыточной позиции существует бесконечно много позиций, которые могут быть превращены в эту убыточную позицию одним движением. Таким образом, все эти бесконечно многочисленные позиции являются выигрышными.
- Поэтому выигрышных позиций намного больше, чем проигрышных. Поэтому эффективнее всего запомнить как можно больше убыточных позиций, все остальные позиции являются выигрышными.

Составьте список убыточных позиций, которые вам известны, и для каждой позиции запишите все соответствующие выигрышные позиции и способы их обнаружения

Следующий пример показывает, что мы имеем в виду:

Как было показано ранее, когда позиция имеет всего 2 ряда, а верхний ряд имеет на одну плитку больше, чем второй ряд, то это проигрышная позиция, как показано ниже:

#####
####
Взяв эту известную проигрышную позицию, мы можем определить, что соответствующими выигрышными позициями являются:

#####+?
####

#####
####+

#####
####
+???
????

В левой позиции может быть любое количество ? справа от верхнего ряда, и в правильном положении, может быть любое количество рядов ? под. Мы можем кратко изложить в словах, как определить эти выигрышные позиции (о чем вы должны помнить для своей игры):

- Позиция – это выигрышная позиция, которая сводится к
  #####
  ####
- - Если в позиции всего два ряда, и первый ряд не на одну плитку длиннее второго ряда, или
- - Если позиция состоит из более чем двух рядов, а первый ряд ровно на одну плитку длиннее второго ряда.
Но есть и о чем подумать. Мы не только хотим правильно играть в таких выигрышных позициях, но и хотим избежать хода, который создает такие выигрышные позиции. Это означает, что мы не должны делать ход там, где осталось только два ряда, или где второй ряд имеет ровно на одну плитку меньше, чем первый.

Подводя итог, можно сказать, что мы хотим создавать убыточные позиции, но мы также хотим избежать создания позиций, которые находятся на расстоянии одного движения от убыточной позиции.

Еще один момент, на который следует обратить внимание: из-за упомянутой ранее зеркальной симметрии все вышеуказанные комментарии можно повторить, просто заменив слово «строка» на слово «столбец».

Вам остается собрать больше убыточных позиций и соответствующих им выигрышных позиций, которые находятся на расстоянии одного хода.

Что делать, если вам придется играть в проигрышной позиции?
- Если вы осознаете, что вам нужно сделать ход в проигрышной позиции, то в теории у вас нет шансов. Все, что вы можете сделать, это надеяться, что ваш противник не знает всех выигрышных ходов для позиций, которые вы можете создать своим следующим ходом. Что вы можете сделать, так это удалить только одну плитку из угла. Это дает вашему противнику результирующую позицию максимального размера, и это затрудняет для вашего противника определение соответствующего выигрышного хода.

Как научиться убыточным позициям самостоятельно?
- Необходимо выполнить то, что известно как полный поиск по дереву. Первый игрок начинает с угадывания хода, затем второй игрок угадывает ход и так далее, пока один игрок, скажем, игрок А, не выиграет. Затем игроку В разрешается изменить последний сделанный ход, и следующим наступает очередь игрока А. Если в одной позиции у игрока, играющего следующим, скажем, В, заканчиваются ходы, потому что все ходы ведут к проигрышу, то это проигрышная позиция, и игрок Б может изменить последний ход, сделанный до того, как была достигнута эта проигрышная позиция.
- Этот «поиск дерева» продолжается до тех пор, пока не станет ясно, является ли начальная позиция проигрышной или какой ход игрока 1 превращает ее в проигрышную.
- Это может быть очень долгим процессом, если попытаться сделать это на начальной доске с большим количеством плиток. Однако, чем больше убыточных позиций мы знаем, тем короче последовательности движений до достижения такой позиции, и, таким образом, весь поиск происходит гораздо быстрее. Если бы мы знали все содержащиеся в них убыточные позиции, то либо начальная позиция была бы признана убыточной, либо понадобился бы всего один ход, чтобы свести ее к убыточной.

Как узнать убыточные позиции с помощью компьютера?
- На уровне сложности «Очень сложно» и позициях не больше 8 x 15 компьютер играет идеально, поэтому каждая позиция, которая является результатом компьютерного хода, является проигрышной позицией! Следует начать с очень маленьких досок и играть против компьютера на уровне «Очень сложно» и изучить все позиции, которые генерирует компьютер. Для каждой такой позиции подумайте о том, как компьютер будет реагировать на каждый ваш ход, превращая ее в меньшую убыточную позицию. Для каждой проигрышной позиции также является проигрышной позиция зеркальная позиция ( <--> строки, столбцы).
- Каков оптимальный первый шаг?
  - В конкурсе стартовой позицией будет прямоугольник из конфет. Как было доказано ранее, прямоугольник – это выигрышная позиция, но что такое первый ход, превращающий его в проигрышную позицию для соперника? Ранее мы узнали, что оптимальным ходом для квадрата является плитка (2,2), но что, если прямоугольник не является квадратом?
  - Просто переключитесь на «очень сложный» уровень сложности и позвольте компьютеру сделать первый шаг. Пока прямоугольник не больше 8х15, компьютер играет оптимально и покажет идеальный первый ход. Попробуйте разные размеры прямоугольника и запомните оптимальный первый ход, потому что компьютерная игра будет недоступна в дни соревнований :).
- В скором времени вы станете непобедимым на легком и среднем уровне сложности.

Существуют ли бесконечные семейства убыточных позиций?
- Мы уже встречались с этими двумя семействами проигрышных позиций. N — любое положительное целое число.
- Вот еще несколько примеров:

Встроенный в игру компьютерный плеер использует разные техники для разных игровых уровней.

- Лёгкий- Делает случайные ходы каждый ход. Если будет обнаружена простая выигрышная позиция, она переместится туда.
- Терпимая- По-прежнему движется случайным образом, но обладает большими знаниями о выигрышных и проигрышных позициях. Будет избегать ходов, которые открывают сопернику доступ к простому выигрышному ходу.
- Трудный- Обладает еще большими знаниями о выигрышных позициях. Активно ищет на доске ходы, которые могут заставить соперника сделать проигрышный ход самому.
- Каторжный- Всегда сделает оптимальный ход для любой позиции, которая помещается в прямоугольник размером 8х15.
Чем выше уровень сложности, тем сложнее будет принудить компьютер в проигрышное положение. На каждом уровне известно гораздо больше выигрышных и проигрышных позиций, чем на предыдущем уровне, и чем сложнее сложность, тем больше выигрышных и проигрышных позиций вам нужно будет знать, чтобы попытаться заставить компьютер оказаться в проигрышной позиции.

Следующие комментарии не помогут вам стать сильнее в Чомпе, но они предоставят вам некоторые интересные факты и дадут нам еще одну возможность попрактиковаться в доказательствах с помощью индукции.

Сколько различных позиций, включая пустую доску, помещается в прямоугольник с P строками и Q столбцами?
- Если мы включим пустой прямоугольник, то сможем рассчитать общее количество возможных позиций по следующей формуле: \[\frac{(P+Q)!}{P!Q!}\]Можете ли вы вычислить это число для малых P и Q и проверить его правильность?
- Первый вывод рекурсивной формулы
  - Пусть f(P,Q) — количество позиций в прямоугольнике размера PxQ. Важным наблюдением является то, что все позиции имеют форму лестницы, где в каждом ряду не более столько плиток, сколько в ряду выше, но не больше.
  - Давайте начнем с того, как мы можем представить все эти лестницы. Один из способов легко создать лестницу — начать с левого нижнего угла доски и двигаться либо вправо, либо вверх. Можно продолжать делать эти ходы вправо и вверх, пока они не дойдут до верхнего правого угла доски. Мы будем называть это путем , который мы выбрали, чтобы перейти от (P,0) к (0,Q).
  - Количество позиций равно количеству путей от (P,0) до (0,Q), при условии, что можно двигаться только вверх или вправо. Число путей f(P,Q+1) для перехода от (P,0) к (0,Q+1) — это количество f(P,Q) путей для перехода от (P,0) к (0,Q), а затем к (0,Q+1) + количество f(P-1,Q) путей для перехода от (P,0) к (1,Q), а затем к (1, Q+1) и (0,Q+1), и так далее. Соответствующая формула выглядит следующим образом:\[f(P,Q+1) = f(P,Q) + f(P-1,Q) + f(P-2,Q) + \ldots + f(1,Q) + f(0,Q)\]
  - Теперь мы возьмем эту формулу и заменим P на P + 1. Если вместо P подставить в формулу P + 1, то получится следующее: \[f(P+1,Q+1) = f(P+1,Q) + f(P,Q) + f(P-1,Q) + \ldots + f(0,Q)\] \[f(P+1,Q+1) = f(P+1,Q) + f(P,Q+1)\]Из этого нового вывода мы можем определить формулу \(f(P,Q) = f(P,Q-1) + f(P-1,Q)\) где \(f(P,0) = 1\) и \(f(0,Q) = 1\).
- Альтернативный вывод рекурсивной формулы
  - Часто существует несколько способов подсчета в комбинаторных задачах. Следующий вывод обеспечит другой, более элегантный способ получения формулы.
  - Мы будем использовать то же представление, которое мы использовали ранее, где мы хотим найти общее количество путей, которые ведут нас от (P,0) к (0,Q). Мы можем организовать эти пути в две группы.
  - Пути, которые начинаются с первого хода, идущего вправо от (P,0) до (P,1). Мы знаем, что в этой группе у нас будет всего f(P,Q-1) путей от (P,1) до (0,Q). Мы знаем это, потому что оставшийся прямоугольник после перемещения прямоугольника вправо имеет размер P x (Q-1).
  - Другая группа – это пути, которые начинаются с первого хода и поднимаются на один ход вверх от (P,0) до (P-1,0). Мы знаем, что в этой группе всего f(P-1,Q) путей, так как результирующий прямоугольник будет иметь размер (P-1) x Q.
  - Следовательно, поскольку каждый возможный путь будет попадать в одну из этих двух групп, общее количество путей является суммой этих групп. Это дает нам ту же формулу \(f(P,Q) = f(P,Q-1) + f(P-1,Q)\).
- Вывод явной формулы
  - Вместо того, чтобы начинать контуры с правого нижнего угла, давайте поворачиваем прямоугольник так, чтобы точка (P,0) была наверху. Теперь мы можем визуализировать пути с помощью следующей диаграммы:
  - Этот тип диаграммы известен как дерево. Эта закономерность будет повторяться до тех пор, пока мы не перейдем от (P,0) к (0,Q). Когда это произойдет, дерево будет содержать все возможные пути, по которым можно пройти.
  - Количество способов добраться от вершины (P,1) до узла (I,J) в этом дереве — это количество способов, которыми можно добраться до (I-1,J), а затем спуститься вправо к (I,J), плюс количество способов добраться до (I,J-1), а затем спуститься влево к (I,J). Другими словами, это число в треугольнике Паскаля.
  - Каждое число в треугольнике Паскаля является суммой двух чисел выше. Числа в левом столбце подсчитывают ряды доски, начиная с 0 с пустой доски. Цифры под треугольником обозначают положение слева, также начиная с 0. Число в N'м ряду в позиции K равно \({N \choose K} = \frac{N!}{(N-K)!K!}\).
  - Мы хотим найти число f(p,q), которое является числом способов перехода от (P,0) к (0,Q). Чтобы сделать это, нужно пройти сверху вверх: P раз вниз вправо и Q умножить вниз влево. Используя структуру дерева, которую мы определили ранее, это то же самое, что переход от (0,0) к (P,Q) только влево и вправо в дереве.
  - Однако это заставляет нас делать шаги P+Q, поэтому мы находимся в строке P+Q в дереве. Поскольку мы знаем, что мы переместили Q раз вправо, число в треугольнике Паскаля в этой позиции равно \({P+Q \choose Q} = \frac{(P+Q)!}{P!Q!}\).
- Доказательство явной формулы с помощью индукции
  - Мы покажем, что следующие формулы эквивалентны. \[f(P,Q) = \begin{cases}1 & for & P=0 \\1 & for & Q=0 \\f(P,Q-1) + f(P-1,Q) & for & \text{P>0 and Q>0}\end{cases} = \Bigg\{{P+Q \choose Q} = \frac{(P+Q)!}{P!Q!}\]
  - Индукционная база: Мы уже знаем, что f(0,0) = 1 по определению формулы. Если мы подставим в формулу P=0 и Q=0, то получим \(\frac{(0+0)!}{0!0!} = \frac{0!}{1} = 1\). Это показывает, что формулы основания эквивалентны, что завершает индукционную базу.
  - Гипотеза индукции: Предположим, что формулы эквивалентны для всех значений P,Q при P+Q = N.
  - Шаг индукции: Используя гипотезу индукции, мы доказываем эквивалентность для всех величин P,Q с P+Q=N+1. Для любых значений P,Q с P+Q=N+1 имеем 3 случая:
  - Случай 1:
  - Случай 2:
  - Кейс 3: \(P,Q > 0\) \[ \begin{align} f(P,Q) &= f(P,Q-1) + f(P-1,Q)\qquad\qquad (+)\\ &= \frac{(P+Q-1)!}{P!(Q-1)!} + \frac{(P-1+Q)!}{(P-1)!Q!}\\ &= \frac{(P+Q-1)!Q}{P!(Q-1)!Q} + \frac{(P-1+Q)!P}{(P-1)!PQ!}\\ &= \frac{(P+Q-1)!}{P!Q!} (Q+P)\\ &= \frac{(P+Q)!}{P!Q!} \end{align} \]
  - (+): Если P + Q = N + 1, то P + Q-1 = N, т.е. по гипотезе индукции.
    f(P,Q-1) = \(\frac{(P+(Q-1))!}{(P!(Q-1)!)}\), и аналогично для f(P-1, Q)
  - Это показывает, что две формулы для f(P,Q) эквивалентны.
  - Конец доказательства. ∎

Сколько различных позиций имеют P строк и Q столбцов?
- Можно просто использовать одну и ту же формулу для всех позиций, помещающихся в прямоугольник со строками P-1 и столбцами Q-1, который равен f(P-1,Q-1).

Есть ли больше выигрышных или больше проигрышных позиций?

# плиток	# позиций	# убыточных позиций	% убыточных позиций
20	627	42	6.69
30	5604	220	3.92
40	37338	1022	2.73
50	204226	4976	2.43
60	966467	20106	2.08
70	4087968	76688	1.87
80	15796476	270142	1.71
90	56634173	897964	1.58

Гипотеза Карибу

Ранее мы показали, что каждая позиция является либо выигрышной, либо проигрышной. Доказательство дало нам прямой метод, позволяющий шаг за шагом определить для всех позиций, являются ли они убыточными или выигрышными. Особенность заключалась в том, что этот метод не нуждался в поиске (перебое ходов). Это напомнило нам «Решето Эратосфена» для определения всех простых чисел с точностью до некоторого размера.

Почитайте про решето Эратосфена, например в интернете
- Чтобы найти все простые числа до размера N², где N — некое целое число, нужно сделать следующее:
- - О: Начните с простого числа p=2.
  - Б: Вычеркните все кратные p до N².
  - C: Найдите следующее по величине число > p, которое еще не зачеркнуто. Если это число равно > N, то алгоритм останавливается. В противном случае позвоните по этому номеру p и перейдите к шагу B.
- Все числа до N² , которые не зачеркнуты, являются простыми числами < N². Симуляцию этого алгоритма можно найти на https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Эта аналогия вдохновила нас на мысль о большем сходстве между простыми числами и проигрышными позициями. Это привело к гипотезе о проигрыше позиций, которая похожа на «теорему о простых числах». Вот подробности.

Таблица: Аналогии между убыточными позициями в чомпе и простых числах:

Числа	Чавкать
Существует бесконечное множество целых чисел.	Существует бесконечное количество позиций Chomp.
Существуют простые числа и числа, разлагаемые на множители.	Есть убыточные позиции и выигрышные позиции.
Существует бесконечное множество простых чисел.	Убыточных позиций бесконечно много.
Факторизуемое число — это произведение простого числа и числа.	Выигрышная позиция — это сумма проигрышной позиции и позиции (потому что то, что вырезается в ходе, имеет форму лестницы, а значит, является позицией).
Как только простое число известно, мы мгновенно узнаем бесконечное количество мнотворных чисел (все кратные простому числу).	Как только убыточная позиция известна, мы мгновенно узнаем бесконечно много выигрышных позиций (все позиции, полученные в результате заполнения угловых прямоугольников, включая бесконечно длинные прямоугольники в верхнем ряду и левом столбце).
Большое число с гораздо большей вероятностью делится на малое простое число, чем на большое простое число.	Большая позиция с гораздо большей вероятностью может быть сведена к небольшой убыточной позиции, чем к большой убыточной позиции.
Чтобы определить, является ли число N простым числом, очень эффективно знать все простые числа P с точностью до квадратного корня из N. Тогда можно проверить, можно ли N свести к P путем деления, т.е. с помощью пробного деления N / P.	Чтобы определить, является ли позиция P убыточной, необходимо знать все убыточные позиции L, которые содержатся в P. Затем можно эффективно проверить, можно ли уменьшить P до L за один ход.
«Решето Эратосфена» — это эффективный способ определить все простые числа с точностью до некоторого числа N, а также проверить, является ли данное число простым. Этот алгоритм описан выше.	Как и в «Решете Эратосфена», человек начинает с проигрышной позиции {1} и зачеркивает все выигрышные позиции, которые превращаются в эту проигрышную позицию, за один ход. Затем вы проверяете все позиции с помощью еще одной плитки. Все позиции, которые не зачеркнуты, являются убыточными позициями.
Оставшаяся неэффективность ситового алгоритма заключается в многократном вычеркивании числ, которые можно разложить на множители.	Оставшаяся неэффективность алгоритма сита заключается в многократном зачеркивании выигрышных позиций.
Плотность простых чисел уменьшается с увеличением их размера; т.е. отношение (# простых чисел до некоторого целого числа N) / N уменьшается с увеличением N.	Плотность убыточных позиций уменьшается с их размером; т.е. соотношение (# убыточных позиций с количеством до N плиток) / (# всех позиций с N плитками) уменьшается с увеличением N. (Задача: Какова формула зависимости этого отношения от N и как она соотносится с формулой плотности простых чисел?).
Теорема о простых числах: (# простых чисел ≤ N) / (N / log(N)) → 1 как N → бесконечности.	Аналогичная гипотеза: (# убыточных позиций с N плитками) / (((# позиций с N плитками) / log(# позиций с N плитками)) → 0.283... как N → бесконечности.

Таблица: Различия между убыточными позициями в Чомпе и простых числах:

Числа	Чавкать
Множество всех целых чисел является полностью упорядоченным множеством; Т.е. между любыми двумя числами известно, какое из них больше.	Множество всех позиций Chomp является частично упорядоченным множеством. Позиции могут полностью содержаться в других позициях, но не обязательно.
Операцией по сведению числа к одному из его простых факторов является деление.	Операцией по приведению позиции в убыточную является вычитание плиток.
Число можно визуализировать в виде отрезка на одномерной числовой прямой.	Позиция определяется с помощью списка чисел, отсортированных по размеру, и, таким образом, является 2D-объектом.

Открытые вопросы:

Является ли гипотезой (# убыточных позиций с N плитками) / (((# позиций с N плитками) / log(# позиций с N плитками)) → 0.283... как N → бесконечность истинна?

Можете ли вы это доказать? (Мы пока не можем :-) )

Игра Chomp, в которую играется выше, является версией 2D Chomp. Это значит, что доска бывает только 2-х мерной, имеющей ширину и высоту.

Можете ли вы представить себе версию 3D Chomp?
- Самый простой способ представить себе добавление нового измерения в игру — это добавить третье измерение на игровое поле. Вместо просто ширины и высоты, новая доска будет иметь длину, ширину и высоту. Если бы у кого-то были маленькие кубики для игры, например, игральные кости, он мог бы играть в эту 3D-игру, как показано на картинке ниже.
- При совершении хода нужно удалить выбранный куб, а также все кубики слева, выше и выше выбранного куба. Пример хода на изображении выделяется желтым цветом, что также удаляет все зеленые плитки на изображении. Человек, который берет последнюю плитку, показанную красной плиткой на изображении, является игроком, который проигрывает игру.
- Чтобы облегчить игру с настоящими кубиками, можно прижать кубики к углу, например, к углу коробки из-под обуви, так что красная плитка находится в самом углу коробки и доступна только после того, как все остальные кубики также будут удалены. Использовать коробку это не обязательно, но она бы стабилизировала кубики и облегчила бы извлечение куба, не опрокинув всю конструкцию.

А как насчет игры в Chomp в еще большем количестве измерений?
- Ранее мы определили, что достаточно просто добавить новое измерение в игру Chomp. Если бы кто-то хотел играть в Chomp в еще более высоком измерении, чем 3D, он бы продолжал добавлять новые измерения на игровую доску Chomp. Однако после 3D больше нет возможности смоделировать доску Chomp с помощью блоков. Тем не менее, есть способ смоделировать игру в чавканье с помощью карандаша и бумаги, и этот метод позволяет нам играть в игру в любом количестве измерений, а не только в 2D или 3D.
- Мы начнем с игры в 2D Chomp на бумаге. Чтобы смоделировать игру, сначала выберите число, которое имеет только 2 различных простых множителя. Например, 72 = 2³ x 3². Затем мы записываем все делители этого числа в виде прямоугольника, как показано ниже.
- 72 36 18 9
  24 12 6 3
  8 4 2 1
- Любой правый соседний номер меньше в 2 раза, а любой соседний номер ниже меньше в 3 раза. Чтобы сделать ход на этой доске, нужно выбрать число. Затем вы должны удалить это число вместе с любыми его множителями. Тот, кто возьмет число 72, проигрывает игру.
- Чтобы получить больший начальный прямоугольник, можно найти большее число, используя формулу 2^P x 3^Q. Заменив P и Q на большие числа, можно получить все большие и большие платы для 2D Chomp.
- Как можно обобщить эту симуляцию для более высоких размерностей?
  - Чтобы расширить эту версию Chomp с карандаша и бумаги с 2D на 3D, нужно просто расширить формулу, используемую для поиска начального числа. Вместо того, чтобы выбирать число, которое имеет только 2 различных простых делителя, следует выбрать число, которое имеет 3 различных простых делителя. Мы можем использовать новую формулу, чтобы найти это число, которое выглядит следующим образом: 2^P x 3^Q x 5^R. Затем, используя те же методы, что и раньше, игру можно смоделировать в 3 измерениях. Переход к еще большим размерностям просто требует добавления новых простых чисел в формулу, в зависимости от количества измерений, которое вы хотите.