После этого, из каждого из уголков
(2^n,2^n,0),
(2^n,0,2^n),
(0,2^n,2^n),
начинает расти точно такой же куб размера 2^n с выигрышными и проигрышными позициями: пока мы по третьей координате не отошли от соответствующей грани больше, чем на 2^n, процесс заполнения выигрышных/проигрышных позиций повторяет процесс заполнения из (0,0,0). Потому что первые две координаты нельзя уменьшать ниже 2^n — мы попадём как раз в те самые лучи выигрышных позиций, идущие из углового куба, которые нарисованы синим на картинке выше.

Так что три новых куба со стороной 2^n будут заполнены выигрышными/проигрышными позициями точно так же, как и исходный угловой. А их объединение даёт куб со стороной 2^(n+1) — в котором опять в каждом столбце уже есть одна проигрышная позиция. Вот и шаг индукции.

Геометрическая картинка — а что будет, если мы при разных n будем рисовать проигрышные позиции в единичном кубе, разбитом на кубики-пиксели (точнее, воксели) со стороной 1/2^n?
При n=0 это весь куб (позиция (0,0,0) проигрышная!), при n=1 это буквально рисунок выше. А при переходе от n к n+1 нужно взять предыдущюю (трёхмерную) картинку, и объединить её четыре сжатых в два раза копии (потому что сторона маленького кубика теперь вдвое меньше). А центры гомотетии расположены в четырёх вершинах
(0,0,0), (0,1,1), (1,0,1), (1,1,0)
большого куба.

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

И помните, мы видели, что проекция тетраэдра Серпинского вдоль линии, соединяющей середины противоположных рёбер, которая оказывается квадратом (и это соответствие почти что взаимно-однозначное, кроме довольно немногих точек)? Это как раз соответствует правилу "в каждом столбце в кубе со стороной 2^n ровно одна проигрышная позиция".

А ещё — четыре кубика на этом рисунке, если их считать единичными (ну, или их левые нижние уголки) образуют график функции "сумма по модулю 2".

Пусть мы смотрим на проигрышные позиции в кубе со стороной 2^{n+1}. Тогда то, в какой из кубов со стороной 2^n мы попадаем, определяется старшими — отвечающими 2^n — битами в двоичных записях координат. А то, где именно мы в меньшем кубе со стороной 2^n находимся — частью двоичной записи без старшего бита.
И отсюда мгновенно получается описывающее проигрышные позиции в кубе правило: двоичная запись третьей координаты это XOR двоичных записей первых двух.

Если теперь опять всё сжать в 2^n раз, чтобы куб стал единичным — XOR останется XOR-ом, только будет применяться не до двоичной запятой, а после. А если перейти к пределу по n, то получится ещё одно описание тетраэдра Серпинского: это замыкание графика функции
z_2 = XOR (x_2, y_2)
(где "_2" соответствует тому, что мы берём двоичную запись, а необходимость брать замыкание возникает из-за неоднозначностей двоичной записи).

Правило проигрышной позиции можно переформулировать в более симметричном виде:

в ниме позиция (x,y,z) проигрышная тогда и только тогда, когда побитовая сумма количеств камней XOR(x,y,z) — нулевая.

На самом деле — это правило работает и для большего количества кучек, причём дословно так же: побитовая сумма всех количеств должна быть нулевой. И это несложно доказать по индукции — проверив, что если мы объявим такие позиции проигрышными, то:
- из проигрышной все ходы будут вести в выигрышные (достаточно посмотреть на любой из изменившихся битов в той кучке, где был сделан ход),
- из выигрышной всегда есть ход в проигрышную (смотрим на то, откуда пришёл старший бит у ненулевого XOR-а, и делаем ход в эту кучку — зная из XOR-а, докуда именно мы хотим её уменьшить).
И из этого несложно увидеть, что это действительно выигрышные и проигрышные позиции. (Собственно, я в детстве в какой-то из детских математических книг — кажется, у Гарднера? — как раз такое рассуждение и увидел.)

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

Да — я тут буду следовать дубнинской брошюре Пьера Деорнуа, "Комбинаторная теория игр", а более подробно это (и не только!) описано в книгах
* Berlekamp E. R., Conway J. H., Guy R. K. Winning Ways for your Mathematical
Plays
и
* Conway J. H., On Numbers and Games

Так вот — давайте рассматривать игры в математическом смысле этого слова, причём достаточно хорошие. Пусть они всегда заканчиваются за конечное число ходов, в них нет никакой случайности, скрытой информации, и так далее. Пусть игроки ходят по очереди — и пусть (это важное соглашение!) всегда проигрывает тот, кто не может сделать ход.

Иногда — как в игре ним — разрешённые ходы для игроков одни и те же; такие игры называют равноправными. Но вообще-то это не обязательно: может быть, один игрок может двигать только синие фишки, а другой только красные.

На играх есть очень естественная операция суммы. Чтобы сложить две игры A и B, нужно просто поставить доску для игры в A рядом с доской для игры в B — и договориться, что каждый игрок ходит там, где хочет. Понятно, что эта операция коммутативная (всё равно, с какой стороны какую доску ставить) и ассоциативная (что так, что так для суммы A+B+C будут стоять рядом три доски, A, B и C).

А вообще что об этой операции можно сказать? Скажем, кто будет выигрывать в сумму игр, которые мы насколько-то понимаем?

Сразу можно заметить, что игра ним с несколькими кучками камней — это сумма нимов с одной кучкой каждый. И поэтому ясно, что сумма может быть гораздо менее тривиальной, чем складываемые игры по отдельности.

Если у нас равноправная игра (где мы в слово "игра" включаем и начальную позицию), то в ней либо выигрывает начинающий, либо второй игрок. А вот если игра не обязательно равноправная (такие игры называют пристрастными), то вариантов больше.
Следуя всем текстам выше, будем называть игроков Левый и Правый — скоро станет понятно, почему.

Так вот — вариантов 4, но вместо того, чтобы группировать их как "начинает Левый, выигрывает Правый", и т. д., мы их сгруппируем так:
- кто бы ни начинал, он выигрывает ("выигрывает начинающий")
- кто бы ни начинал, он проигрывает ("выигрывает второй игрок")
- кто бы ни начинал, выигрывает Левый
- кто бы ни начинал, выигрывает Правый.

И вот то, ради чего всё затевалось:

Определение. Игра называется нулевой, если в ней выигрывает второй игрок.

Теорема. Пусть игра B нулевая. Тогда для любой игры A в сумме игр A+B выигрывает тот же игрок, что и в самой A.

Доказательство. Тот, кто выигрывает в A, следует там своей выигрышной стратегии — а на доске для B ходит только в ответ, следуя выигрышной стратегии как второго игрока.

Эта теорема показывает, почему мы называем такие игры нулевыми — их прибавление ничего не изменяет. И да — логично обозначать то, что игра A нулевая, записью A=0.

Если есть сложение, есть ноль, дальше хочется иметь противоположный элемент.

Определение. Игра B противоположна игре A, если A+B=0.

Пример/предложение. Если игра A равноправная, то A+A=0.

Доказательство. Симметричная стратегия: каждый раз повторяем ход первого игрока на другой доске.

Теорема. Для любой игры A найдётся противоположная ей игра B.

Набросок доказательства. Берём доску для игры в A и меняем правила, меняя игроков местами. То, что раньше мог делать Правый, теперь может делать Левый, и наоборот. После этого применяем симметричную стратегию.

Когда мы работаем с группой (или векторным пространством, или полем), то нулевой элемент один. А из определения выше видно, что нулевых игр много. Так что естественно, что мы сейчас захотим говорить о равенстве игр (в том же смысле, в каком в геометрии есть равенство треугольников — то есть, формально, нужно было бы говорить об эквивалентности игр, но это сделает текст менее читаемым).

А как проверить, что A=B? Можно перенести B в левую часть — и получится A-B=0. А « =0 » у нас уже определено!
Точнее — операции « минус » у нас ещё нет, зато есть « плюс » и определение противоположного. Приходим к такому:
Почти-определение. Игры A и B равны, если A+(-B)=0, где (-B) — противоположная игре B игра.

У этого почти-определения есть проблема: вообще-то, противоположных B игр (как и нулевых) тоже много. Так что мы не оговорили, это должно быть верным — для любой противоположной B игры? Для какой-то? Давайте это сделаем:

Определение. Игры A и B равны, если найдётся игра D, такая, что A+D=0 и B+D=0.

Ну и давайте из этого определения извлечём какую-нибудь пользу. А именно — равные игры можно заменять друг на друга в качестве слагаемых, и это не влияет на то, кто будет выигрывать.

Теорема. Пусть игры A и B равны. Тогда для любой игры C в суммах игр A+C и B+C выигрывает один и тот же игрок.

Следствие. Взяв в качестве C пустую игру (ходить вообще нельзя никак; конечно же, это самый естественный представитель класса нулевых игр!), видим, что в самих играх A и B, в частности, выигрывает один и тот же игрок.

(Ну, собственно, если бы это утверждение не выполнялось — я бы сказал, это было бы поводом отказаться от такого « равенства ».)

Доказательство теоремы. Давайте рассмотрим сумму четырёх игр:
A+C+B+D.

С одной стороны, можно сгруппировать слагаемые как (A+C)+(B+D), и раз игра B+D нулевая — мы уже знаем, что в сумме выигрывает тот же, что и в (A+C).

С другой — можно их сгруппировать как (B+C)+(A+D), и раз игра A+D тоже нулевая — мы знаем, что в сумме выигрывает тот же, что и в (B+C).

Значит, в A+C и в B+C выигрывает один и тот же игрок.

Следствие/упражнение. Пусть A=B, т.е. есть такая игра D, что A+D=0 и B+D=0. Тогда для любой игры D’, такой, что A+D’=0, выполнено B+D’=0.

Решение 1. Достаточно рассмотреть сумму A+B+D+D’ и по-разному сгруппировать слагаемые.
Решение 2. Применить теорему к суммам D+B и D’+B, заметив, что D=D’, поскольку D+A=D’+A=0.

Замечание к решению 2. Кстати — все противоположные к данной игре A игры равны друг другу. Что хорошо в смысле разумности наших определений.

Упражнение. Если A=B, и C=D, то A+C=B+D.

Упражнение. Равенство игр — отношение эквивалентности.

Так что мы получили группу по сложению (классов эквивалентности) игр.

А ещё мы сейчас можем разобраться с нимом с произвольным количеством кучек.
Действительно, мы уже знаем, как устроены проигрышные позиции для нима с тремя кучками камней: это тройки количеств камней (k,m,n), связанные соотношением
n=XOR(k,m),
где XOR применяется к двоичным записям.

Но ним с несколькими кучками камней это сумма игр-отдельных кучек. Поэтому (и вспоминая про равноправность нима) мы получаем такое утверждение. Пусть *n обозначает ним с одной кучкой из n камней (в частности, *0 это игра с пустой кучкой камней — т.е. нулевая игра). Тадаммм:

Теорема. *k + *m = *n, где n=XOR(k,m).

Следствие. *n_1 + … + *n_k = *XOR(n_1,…,n_k).

Доказательство. Индукция по числу слагаемых k. База k=2 это утверждение выше, а для шага мы выделяем первые k слагаемых:
*n_1 + … +*n_k + *n_{k+1} = (*n_1 + … +*n_k) + *n_{k+1} =
*XOR(n_1,…,n_k) + *n_{k+1} = *XOR(n_1+…+n_k,n_{k+1}).

В частности, позиция проигрышная тогда и только тогда, когда ей соответствует ним с пустой кучкой камней, *0 — и вот и критерий того, что позиция (n_1,…,n_k) проигрышная: необходимо и достаточно, чтобы выполнялось
XOR(n_1,…,n_k)=0.

Итак, мы увидели, что ним с несколькими кучками камней эквивалентен ниму с одной кучкой из правильно выбранного количества (XOR-а) камней. А случайно ли, что у нас так получилось? Оказывается, нет — существование такой эквивалентности это общее утверждение.

Теорема Шпрага-Гранди. Для любой равноправной игры существует эквивалентная ей игра в ним с одной кучкой (правильно выбранного начального количества) камней.
Замечание. Если это количество камней нулевое — то в игре выигрывает второй игрок, если нет — то начинающий.

Но прежде, чем доказывать эту теорему — давайте посмотрим с этой точки зрения на нахождение проигрышных позиций в ниме с тремя кучками камней. В каждом столбце есть проигрышная позиция — и то, на каком она уровне, как раз и указывает нам, сколько камней нужно взять в третьей кучке, чтобы она равнялась сумме игр-первой и второй кучек (потому что тогда всё в целом даёт нулевую игру, a.k.a. проигрышную позицию).

А как эта проигрышная позиция находится? В столбце будут выигрышные позиции, приходящие из проигрышных клеток в столбцах ниже (в смысле плоскости — если хотите, севернее) или левее (западнее). И первая из клеток, которая таким образом « выбита » не будет, и будет проигрышной.

Если заполнять таблицу «какой игре *n равняется сумма *k+*m» (как мы уже знаем, на самом деле это таблица значений XOR двоичных записей), то правило выше превращается в правило наименьшего исключенного:
в клетке (k,m) стоит первое из неотрицательных целых чисел, которое не появляется ни в одной из клеток (k’,m’), которые из неё можно получить за один ход.

Так вот — на самом деле, то, что мы тут исследовали ним на двух кучках, совершенно неважно! То же самое правило наименьшего исключенного (mex-rule) строит соответствующее *n (ним на одной кучке из n камней) и для любой равноправной игры. А именно: пусть у нас есть какая-то равноправная игра, будем сопоставлять ей ним-игру *n по индукции. Если уже построены сопоставления для всего, что можно из данной позиции получить за один ход, и это *n_1,…,*n_m, то самой позиции сопоставляем *n, где n — наименьшее неотрицательное целое число, не встречающееся среди n_1,…,n_m.

Доказательство теоремы Шпрага-Гранди. Построить-то соответствующие ним-игры мы построили, но остаётся проверить, что построенная игра действительно равна исходной — то есть что их сумма нулевая. А для этого в их сумме мы предъявим выигрышную стратегию для второго игрока.

Пусть из исходной позиции A нашей игры можно пойти в A_1,…,A_m — которым соответствуют ним-игры *n_1,…,*n_m, и мы уже знаем, что
A_j + *n_j =0.
Мы взяли n = mex(n_1,…,n_m), и рассматриваем сумму A+*n. Докажем, что в ней выигрывает второй игрок.

Действительно, что может сделать первый игрок? Он может сделать ход со стороны A, переведя её в одну из A_j с n_j<n. Тогда мы отвечаем, оставляя *n_j из n камней в *n — и тем самым отдаём противнику позицию A_j + *n_j, проигрышную по предположению.

Он может сделать ход со стороны ним-кучки, перейдя от *n к какому-то *n’. Но раз n было наименьшим исключённым из n_1,…,n_m, значит, найдётся j такое, что n’=n_j. И тут уже мы отвечаем, переходя из A в A_j и опять приводя игру в проигрышную позицию A_j + *n_j.

Наконец, первый игрок мог сделать ход со стороны A, переведя её в одну из A_j, но с n_j>n. Тогда мы ответим ходом из A_j. А именно — n<n_j, поэтому найдётся позиция A_j’, куда мы из A_j можем пойти, которой сопоставлена *n (потому что n_j — наименьшее исключённое). Вот туда мы и пойдём — приведя игру к
A_j’+*n=0.

На самом деле, разбора вариантов n_j<n и n_j>n можно было и не делать, ограничившись замечанием, что *A_j + *n = *n_j + *n; в игре в правой части очевидно выигрывает начинающий (т.е. мы — ход сейчас наш), а у нас есть теорема, что замена игры на равную не изменяет победителя. Но так у нас есть не только теорема, но и явная конструкция стратегии.

Давайте посмотрим на один пример применения этой науки.
Есть такая стандартная кружковская задача:

Есть ромашка с n лепестками, и двое по очереди отрывают либо один лепесток, либо два соседних. Кто не может сделать ход — проиграл. Кто выигрывает при правильной игре?

Решение: при n>2 выигрывает второй игрок. После первого хода первого игрока второй отрывает лепестки строго напротив — разбивая окружность лепестков на два одинаковых участка, и остаётся применить симметричную стратегию.

Это, конечно, решает исходную задачу. Но представим себе, что нам досталась позиция после нескольких ходов. Например, пусть нам достался набор лепестков, образующий отрезки длиной 4, 5, 9 и 20. Кто выигрывает при правильной игре? А если (допустим, ромашка была очень большая) нам достались отрезки длиной 12, 70 и 180?
Попытка исследовать эти игры «от начальной позиции», исследуя дерево вариантов сверху, приводит к не очень подъёмному перебору. (Навскидку, первый вариант вручную и без оптимизации уже неподъёмный, но ещё должен перебираться на компьютере; а второй даже и компьютер не потянет.)

А вот применение конструкции из теоремы Шпрага-Гранди позволяет справиться даже и вручную! А именно — мы хотим для любого n узнать, какому числу камней a_n соответствует игра для одного отрезка из n последовательных лепестков. За один ход мы можем получить из него два отрезка длин s и t, где либо s+t=n-1, либо s+t=n-2.
(Если отрываем лепестки с края, то кто-нибудь из s и t будет нулём.)
Двум отрезкам соответствует сумма игр, и ним-сумма (a.k.a. XOR) соответствующих количеств камней. Соответственно, получаем рекуррентное соотношение
a_n = mex ( XOR(a_s,a_t) | s+t = n-1 или s+t = n-2 ).

Во-первых, при необходимости его и до 180 можно дотащить «вручную». Да, априори это могло бы быть оочень занудно, но это явно посильная задача даже без компьютера.

Во-вторых: давайте посчитаем первые несколько членов последовательности.
n=0 -> пустая игра, ходов нет,
a_0=0.
n=1 -> единственный ход приводит к 0, значит,
a_1=1.
n=2 -> можно получить либо пустую позицию, либо один лепесток, значит,
a_2=mex(0,1) = 2.
n=3 -> можно получить конфигурации (1), (2), (1,1), которым соответствуют ним-значения 1, 2 и 0 соответственно. Значит,
a_3=mex(0,1,2)=3.
n=4 -> можно получить конфигурации (2), (1,1), (3), (1,2), которым соответствуют ним-значения 2, 0, 3 и 3 соответственно. Значит,
a_4= mex(0,2,3)=1.
n=5 -> можно получить конфигурации (3), (2,1), (4), (1,3), (2,2) которым соответствуют ним-значения 3, 3, 1, 2 и 0 соответственно. Значит,
a_5= mex(0,1,2,3)=4.

После чего можно ввести начало найденной последовательности — 0,1,2,3,1,4 — в OEIS, онлайн-энциклопедию целочисленных последовательностей (коллеги цитировали текст к 50-летию энциклопедии — начинавшейся ещё не как онлайн!).
И первой ссылкой этот поиск выдаст последовательность A002186 — после чего, посмотрев на то, что такое упоминаемая там game of Kayles, становится понятно, что это буквально то, что нам нужно. И кстати — начиная с n=71 последовательность становится периодичной с периодом 12.

(For the record: подумав, что я хочу привести тут пример с игрой с ромашкой, я ещё не знал названия Kayles — выше описан буквально тот путь, которым я прошёл.)

Если возвращаться именно к нашим позициям из примеров выше — наборам (4,5,9,20) и (12,70,180) — то первому из них соответствует ним-сумма 1, 4, 4 и 1, и выигрывает второй игрок. А второму — ним-сумма 4, 4 и 6, так что выигрывает первый. Один из выигрышных ходов — превратить третий отрезок в 180 лепестков с ним-значением 6 во что-то с нулевым ним-значением, вырвав два лепестка посередине: мы получим позицию (12,70,89,89) с нулевым суммарным ним-значением.

https://mccme.ru/free-books/

Дед Мороз напоминает про страницу, на которой бесплатно доступны файлы множества книг (в основном издательства МЦНМО)

брошюры библиотеки «Математическое просвещение» и Летней школы «Современная математика», доклады семинара «Глобус» и материалы выездного семинара учителей, книги Арнольда и Гельфанда, Прасолова и Шеня и многое другое.

новогодние каникулы — как раз хорошая возможность спокойно почитать