Математические игры и головоломки — страница 2

  • Просмотров 5151
  • Скачиваний 600
  • Размер файла 1019
    Кб

игр, в которых двое играющих A и B, руководствуясь определёнными правилами, по очереди вынимают то или иное число фишек из одной или нескольких кучек – побеждает тот, кто берёт последнюю фишку. Простейшая такая игра – это игра с одной кучкой фишек, и сделать ход в ней – значит взять из кучки любое число фишек от 1 до m включительно. Многие подобные игры поддаются исследованию с помощью числа Шпрага-Гранди G(C). Пустой позиции O, не

содержащей фишек, отвечает G(O)=0. Комбинацию кучек, состоящих соответственно из x, y, … фишек, обозначим C=(x, y, …) и предположим, что допустимые ходы переводят C в другие комбинации: D, E, … Тогда G(C) есть наименьшее неотрицательное число, отличное от G(D), G(E), … Это позволяет по индукции определить G(C) для любой комбинации C, разрешённой правилами игры. Так, в упомянутой задаче G(x)=x mod (m+1). Если G(C)>0, то игрок, делающий следующий ход, допустим,

это игрок A, может обеспечить себе выигрыш, если ему удастся перейти к «безопасной» комбинации S с G(S)=0. Действительно, по определению G(S) в этом случае либо S – пустая позиция, и тогда A уже выиграл, либо B следующим ходом должен перейти к «опасной» позиции U с G(U)>0 – и тогда всё повторяется снова. Такая игра после конечного числа ходов заканчивается победой A. К подобным играм относится ним. Имеется произвольное число кучек фишек, и

игроки по очереди выбирают одну какую-то кучку и вынимают из неё любое число фишек (но хотя бы одну обязательно). Более общий случай представляет игра Мура, которую также можно назвать k-ним. Правила её те же, что и в обычном ниме (1-ним), но здесь разрешается бать фишки из любого количества кучек, не превосходящего k. Ещё одна подобная игра – Кегли. В ней фишки разложены в ряд, и при каждом ходе убирается одна какая-либо фишка или две

соседние. При этом ряд может разбиться на два меньших ряда. Выигрывает тот, кто возьмёт последнюю фишку. Обобщённая вариация этой игры известна под именем игры Витхоффа. Есть интересная вариация игры ним под названием «звёздный ним». Она довольно проста, но стратегия в ней видна не сразу. Играют в эту игру на звездообразной фигуре, изображённой на рис. 1, слева. Поставьте по одной фишке на каждую из девяти вершин звезды. Игроки A и B

делают ходы по очереди, снимая при каждом ходе либо одну, либо две фишки, соединённые отрезком прямой. Тот, кто снимает последнюю фишку выигрывает. рис. 1 Звёздный ним (слева) и выигрышная стратегия для него (справа) У игрока B при игре в звёздный ним есть выигрышная стратегия, использующая симметрию игровой доски (вообще, выигрышные стратегии многих математических игр строятся на этом). Представим, что отрезки прямых, соединяющие