Математические байки

Нерегулярная рубрика «рабочие картинки» (они красивые, хочется поделиться): часть поверхности Маркова x^2+y^2+z^2-xyz = D и некоторые слоения на ней.

https://mccme.ru/free-books/ Дед Мороз напоминает про страницу, на которой бесплатно доступны файлы множества книг (в основном издательства МЦНМО) брошюры библиотеки «Математическое просвещение» и Летней школы «Современная математика», доклады семинара «Глобус» и материалы выездного семинара учителей, книги Арнольда и Гельфанда, Прасолова и Шеня и многое другое. новогодние каникулы — как раз хорошая возможность спокойно почитать

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

Есть ромашка с 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) с нулевым суммарным ним-значением.

Так вот — на самом деле, то, что мы тут исследовали ним на двух кучках, совершенно неважно! То же самое правило наименьшего исключенного (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 равняется сумма *k+*m» (как мы уже знаем, на самом деле это таблица значений XOR двоичных записей), то правило выше превращается в правило наименьшего исключенного: в клетке (k,m) стоит первое из неотрицательных целых чисел, которое не появляется ни в одной из клеток (k’,m’), которые из неё можно получить за один ход.

Итак, мы увидели, что ним с несколькими кучками камней эквивалентен ниму с одной кучкой из правильно выбранного количества (XOR-а) камней. А случайно ли, что у нас так получилось? Оказывается, нет — существование такой эквивалентности это общее утверждение. Теорема Шпрага-Гранди. Для любой равноправной игры существует эквивалентная ей игра в ним с одной кучкой (правильно выбранного начального количества) камней. Замечание. Если это количество камней нулевое — то в игре выигрывает второй игрок, если нет — то начинающий. Но прежде, чем доказывать эту теорему — давайте посмотрим с этой точки зрения на нахождение проигрышных позиций в ниме с тремя кучками камней. В каждом столбце есть проигрышная позиция — и то, на каком она уровне, как раз и указывает нам, сколько камней нужно взять в третьей кучке, чтобы она равнялась сумме игр-первой и второй кучек (потому что тогда всё в целом даёт нулевую игру, a.k.a. проигрышную позицию).

Следствие/упражнение. Пусть 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.

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

Если есть сложение, есть ноль, дальше хочется иметь противоположный элемент. Определение. Игра B противоположна игре A, если A+B=0. Пример/предложение. Если игра A равноправная, то A+A=0. Доказательство. Симметричная стратегия: каждый раз повторяем ход первого игрока на другой доске. Теорема. Для любой игры A найдётся противоположная ей игра B. Набросок доказательства. Берём доску для игры в A и меняем правила, меняя игроков местами. То, что раньше мог делать Правый, теперь может делать Левый, и наоборот. После этого применяем симметричную стратегию.

Если у нас равноправная игра (где мы в слово "игра" включаем и начальную позицию), то в ней либо выигрывает начинающий, либо второй игрок. А вот если игра не обязательно равноправная (такие игры называют пристрастными), то вариантов больше. Следуя всем текстам выше, будем называть игроков Левый и Правый — скоро станет понятно, почему. Так вот — вариантов 4, но вместо того, чтобы группировать их как "начинает Левый, выигрывает Правый", и т. д., мы их сгруппируем так: - кто бы ни начинал, он выигрывает ("выигрывает начинающий") - кто бы ни начинал, он проигрывает ("выигрывает второй игрок") - кто бы ни начинал, выигрывает Левый - кто бы ни начинал, выигрывает Правый. И вот то, ради чего всё затевалось: Определение. Игра называется нулевой, если в ней выигрывает второй игрок. Теорема. Пусть игра B нулевая. Тогда для любой игры A в сумме игр A+B выигрывает тот же игрок, что и в самой A. Доказательство. Тот, кто выигрывает в A, следует там своей выигрышной стратегии — а на доске для B ходит только в ответ, следуя выигрышной стратегии как второго игрока. Эта теорема показывает, почему мы называем такие игры нулевыми — их прибавление ничего не изменяет. И да — логично обозначать то, что игра A нулевая, записью A=0.

Да — я тут буду следовать дубнинской брошюре Пьера Деорнуа, "Комбинаторная теория игр", а более подробно это (и не только!) описано в книгах * 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). А вообще что об этой операции можно сказать? Скажем, кто будет выигрывать в сумму игр, которые мы насколько-то понимаем? Сразу можно заметить, что игра ним с несколькими кучками камней — это сумма нимов с одной кучкой каждый. И поэтому ясно, что сумма может быть гораздо менее тривиальной, чем складываемые игры по отдельности.

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

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

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

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

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

Геометрическая картинка — а что будет, если мы при разных 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^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) — в котором опять в каждом столбце уже есть одна проигрышная позиция. Вот и шаг индукции.

Давайте я продолжу (и попробую закончить) историю про ним с тремя кучками камней — или, что то же самое, про игру "ладью в угол" в кубе. Мы выше видели, что в кубе размера 1,2,4,8 возникает по одной проигрышной позиции в каждом столбце. И хочется сказать, что так же будет для куба любого размера 2^n. Это оказывается несложно (и очень естественно) доказать просто по индукции. Действительно — если это так для какого-то размера куба N=2^n, то на продолжениях этих столбцов все позиции оказываются выигрышными. И из-за симметрии так будет в каждом из трёх направлений (см. рис.).

вот как эта кривая выглядит (два варианта картинки: для четной и для нечетной степени)

Первая часть шестнадцатой проблемы Гильберта содержит в себе вопрос о взаимном расположении овалов вещественной алгебраической кривой на вещественной проективной плоскости -- у нас все кривые вещественны сейчас. Если кривая задана однородным многочленом P(x,y,z)=0 и степень многочлена P равна n, то число ее компонент связности не больше 1/2(n-1)(n-2)+1. Это теорема Харнака, Харнак же построил и пример максимальной кривой степени n. Насколько я понимаю, эта задача Гильберта -- какие "картинки" могут реализовываться кривыми данной степени -- специалистами признается безнадежной. Для степени 8 максимальная кривая состоит из 22 овалов и осталось реализовать или доказать что невозможно реализовать 6 случаев. И за последние двадцать лет прогресса нет. А с большими степенями все совсем плохо. Тем самым, следующая теорема Г.Михалкина выглядит совершенно удивительной. Пусть есть максимальная кривая степени n. А кроме того на проективной плоскости заданы три прямые (не проходящие через одну точку) -- например "оси координат и бесконечноудаленная прямая". Кривая называется максимальной по отношению к этой тройке прямых, если у этой кривой есть компонента, на которой можно выбрать три непересекающиеся дуги, каждая из которых пересекает свою прямую в n точках. (рисунки в комментариях и статье Михалкина https://arxiv.org/pdf/math/0010018.pdf ) Теорема Михалкина говорит, что такая максимальная кривая, максимальная по отношению к трем прямым -- одна (с точностью до гомеоморфизма проективной плоскости). И это та кривая, которую нашел еще Харнак! Очень красивая -- и по формулировке и по доказательству теорема, ради таких теорем стоит изучать математику. А в вещественной алгебраической геометрии много еще красивого.