Игра Ним
Ним – одна из самых старых и увлекательных математических игр. Для игры в Ним необходим партнер (в Ним играют вдвоем), стол и набор фишек. В качестве фишек обычно используются камешки или монетки. В наиболее известном варианте Нима 12 фишек раскладываются в три ряда так, как показано на рис. 2.3.
Рис. 2.3. Фишки, расположенные для игры в ним по схеме 3-4-5
Правила Нима просты. Игроки по очереди забирают одну или несколько фишек из любого ряда. Не разрешается за один ход брать фишки из нескольких рядов. Выигрывает тот, кто возьмет последнюю фишку (фишки).
Если Вы сыграете несколько партий в Ним, то скоро заметите, что существует некоторая оптимальная последовательность ходов, которая гарантирует победу, если только Вы начинаете игру и первым ходом берете две фишки из первого ряда. Любой другой ход даст шанс Вашему сопернику, который в этом случае наверняка победит, если, в свою очередь, воспользуется оптимальной стратегией.
Полный анализ игры с обобщением на любое число рядов с любым числом фишек в каждом ряду впервые опубликовал в 1901 г. профессор математики из Гарвардского университета Чарльз Л.Бутон, который и назвал игру "Ним" от устаревшей формы английских глаголов "стянуть", "украсть". Открытая им оптимальная стратегия основана на двоичной системе счисления и довольно проста. Каждую комбинацию фишек Бутон назвал либо опасной, либо безопасной: если позиция, создавшаяся после очередного хода игрока, гарантирует ему победу, она называется безопасной, если такой гарантии нет – опасной.
Бутон строго доказал, что любую опасную позицию всегда можно превратить в безопасную нужным ходом. Наоборот, если перед очередным ходом игрока уже сложилась безопасная позиция, то любой его ход превращает позицию в опасную. Таким образом, оптимальная стратегия состоит в том, чтобы каждым ходом опасную позицию превращать в безопасную и заставлять противника "портить" ее. Использование оптимальной стратегии гарантирует победу игроку только тогда, когда он открывает партию и начальная позиция фишек опасна или он делает второй ход, а начальная позиция безопасна.
Чтобы определить, опасна позиция или безопасна, нужно количество фишек в каждом ряду записать в двоичной системе счисления. Если сумма чисел в каждом столбце (разряде) равна нулю или четна, позиция безопасна. Если же сумма нечетна хотя бы в одном разряде, то позиция опасна. Например, для начальной позиции по схеме 3-4-5 получим:
| Десятичная запись количества фишек | Двоичная запись количества фишек |
|---|---|
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
Сумма по разрядам 212.
Сумма цифр в среднем столбце равна 1 – нечетному числу, что свидетельствует об опасности этой позиции. Поэтому первый игрок может сделать ее безопасной для себя, если он возьмет две фишки из первого ряда. В результате в первом ряду остается только 1 фишка (двоичное число также 1), и сумма чисел в среднем столбце изменится на ноль.
В привычной нам десятичной системе счисления емкость каждого разряда равна 10, а для записи значений разряда используются цифры от 0 до 9. В двоичной системе счисления емкость каждого разряда равна 2, а из всех цифр используются только 0 и 1. В этой системе число записывается в виде суммы степеней двойки и при переходе от одного разряда к соседнему левому вес разряда увеличивается в 2 раза. Если нужно записать число 2 в двоичной системе, следует действовать точно так же, как при записи числа 10 в десятичной системе: записать ноль в первом (младшем) разряде и единицу – слева от него, т.е. 10 в двоичной системе означает 2 в десятичной системе. Точно так же 100 в двоичной системе означает 4 в десятичной, 1000-8 и т.д.