2576
Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/
Любую гладкую кривую можно увидеть, нарисовав не саму кривую, а множество касательных к ней. Понятие огибающей подробно описано в сюжете «Парабола: изонить», в котором в качестве огибающей семейства прямых возникает парабола.
Но построение касательных не такое простое дело. Продемонстрируем, как увидеть конические сечения — эллипс, гиперболу, параболу — ничего не считая и не рисуя, а просто складывая листок бумаги. Сюжет сегодняшнего Математического вторника: «Эллипс, гипербола, парабола: складывание листа бумаги» https://etudes.ru/models/conic-sections-paper-folding/ . Для эллипса и гиперболы понадобится вырезать кружок из бумаги, для параболы – просто прямоугольный лист.
Похожие картинки можно уже было видеть в миниатюрах Эллипс как огибающая, Гипербола как огибающая, Парабола как огибающая. Но в них надо уметь строить перпендикуляр к отрезку, а в указанном сегодня способе складывания листочка эта операция «зашита» в сам способ складывания.
Три дня назад на небе можно было увидеть аккуратную половинку Луны (почти точно в фазе первой четверти) — и очень яркую «звёздочку» рядом. Первое, что приходит в голову при виде чего-то столь яркого, это Венера и Юпитер. (Вообще, Марс иногда бывает очень ярким, но не так часто; есть ещё Сириус, но давайте мы его временно заметём под ковёр).
Так вот: допустим, мы ограничили выбор Венерой и Юпитером. Интересно, что написанного выше достаточно, чтобы один из этих вариантов исключить! Как думаете, какой?
(image credit: NASA, вырезано из What’s Up video)
https://mccme.ru/nir/seminar/
в четверг (11.01) продолжится семинар учителей математики:
А.Д.Блинков будет рассказывать про книжку «Площади без формул», которая скоро выйдет в серии «Школьные математические кружки»
как обычно: 19:00, столовая МЦНМО, приглашаются все желающие
Нерегулярная рубрика «рабочие картинки» (они красивые, хочется поделиться): часть поверхности Маркова
x^2+y^2+z^2-xyz = D
и некоторые слоения на ней.
Давайте посмотрим на один пример применения этой науки.
Есть такая стандартная кружковская задача:
Есть ромашка с 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) с нулевым суммарным ним-значением.
А как эта проигрышная позиция находится? В столбце будут выигрышные позиции, приходящие из проигрышных клеток в столбцах ниже (в смысле плоскости — если хотите, севернее) или левее (западнее). И первая из клеток, которая таким образом « выбита » не будет, и будет проигрышной.
Если заполнять таблицу «какой игре *n равняется сумма *k+*m» (как мы уже знаем, на самом деле это таблица значений XOR двоичных записей), то правило выше превращается в правило наименьшего исключенного:
в клетке (k,m) стоит первое из неотрицательных целых чисел, которое не появляется ни в одной из клеток (k’,m’), которые из неё можно получить за один ход.
Следствие/упражнение. Пусть 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.
Если есть сложение, есть ноль, дальше хочется иметь противоположный элемент.
Определение. Игра B противоположна игре A, если A+B=0.
Пример/предложение. Если игра A равноправная, то A+A=0.
Доказательство. Симметричная стратегия: каждый раз повторяем ход первого игрока на другой доске.
Теорема. Для любой игры A найдётся противоположная ей игра B.
Набросок доказательства. Берём доску для игры в A и меняем правила, меняя игроков местами. То, что раньше мог делать Правый, теперь может делать Левый, и наоборот. После этого применяем симметричную стратегию.
Да — я тут буду следовать дубнинской брошюре Пьера Деорнуа, "Комбинаторная теория игр", а более подробно это (и не только!) описано в книгах
* 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).
А вообще что об этой операции можно сказать? Скажем, кто будет выигрывать в сумму игр, которые мы насколько-то понимаем?
Сразу можно заметить, что игра ним с несколькими кучками камней — это сумма нимов с одной кучкой каждый. И поэтому ясно, что сумма может быть гораздо менее тривиальной, чем складываемые игры по отдельности.
А ещё — четыре кубика на этом рисунке, если их считать единичными (ну, или их левые нижние уголки) образуют график функции "сумма по модулю 2".
Пусть мы смотрим на проигрышные позиции в кубе со стороной 2^{n+1}. Тогда то, в какой из кубов со стороной 2^n мы попадаем, определяется старшими — отвечающими 2^n — битами в двоичных записях координат. А то, где именно мы в меньшем кубе со стороной 2^n находимся — частью двоичной записи без старшего бита.
И отсюда мгновенно получается описывающее проигрышные позиции в кубе правило: двоичная запись третьей координаты это XOR двоичных записей первых двух.
Если теперь опять всё сжать в 2^n раз, чтобы куб стал единичным — XOR останется XOR-ом, только будет применяться не до двоичной запятой, а после. А если перейти к пределу по n, то получится ещё одно описание тетраэдра Серпинского: это замыкание графика функции
z_2 = XOR (x_2, y_2)
(где "_2" соответствует тому, что мы берём двоичную запись, а необходимость брать замыкание возникает из-за неоднозначностей двоичной записи).
Геометрическая картинка — а что будет, если мы при разных 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)
большого куба.
Но эти вершины образуют правильный тетраэдр — так что получается буквально процедура построения тетраэдра Серпинского, который мы обсуждали раньше!
Давайте я продолжу (и попробую закончить) историю про ним с тремя кучками камней — или, что то же самое, про игру "ладью в угол" в кубе.
Мы выше видели, что в кубе размера 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 )
Теорема Михалкина говорит, что такая максимальная кривая, максимальная по отношению к трем прямым -- одна (с точностью до гомеоморфизма проективной плоскости). И это та кривая, которую нашел еще Харнак! Очень красивая -- и по формулировке и по доказательству теорема, ради таких теорем стоит изучать математику.
А в вещественной алгебраической геометрии много еще красивого.
https://ems.press/books/standalone/272
выложены труды ICM-2022
«Following the long and illustrious tradition of the International Congress of Mathematicians, these proceedings include contributions based on the invited talks that were presented at the Congress in 2022.
Published with the support of the International Mathematical Union and edited by Dmitry Beliaev and Stanislav Smirnov, these seven volumes present the most important developments in all fields of mathematics and its applications in the past four years. In particular, they include laudations and presentations of the 2022 Fields Medal winners and of the other prestigious prizes awarded at the Congress.»
появление эллипса на круглом листе бумаги ( via vk.com/thebeautyoftruth )
Читать полностью…
Ответ:
Луна в первой четверти означает, что направление на неё почти под прямым углом к направлению на Солнце. А Венера — внутренняя планета, так что на 90 градусов выйти не может.
Если говорить более аккуратно, то радиус орбиты у неё — чуть больше 0.7 радиуса орбиты Земли (точнее, большая полуось 0.723 а.е., но я наизусть только 0.7 помню — одну цифру помнить проще 🙂 ; ну и на уровне прикидки в уме эллиптичностью пренебрегаем, всё-таки там эксцентриситеты порядка процента)
Значит, Венера не может быть от Солнца на угловом расстоянии, большем, чем (примерно) arcsin 0.7.
Ну а sqrt{2}/2=0.707..., так что этот угол это с отличной точностью 45 градусов.
Итак, максимальный угол между направлениями на Венеру и Солнце это чуть больше, чем 45 градусов (на самом деле 47, но это я уже потом посмотрел — а тут прикидывал на ходу, и кажется, неплохо получилось).
Итого:
*) угол Солнце-Земля-Луна в этот момент примерно равен 90 градусам (потому что от Луны освещена половина),
*) угол Солнце-Земля-Венера никогда не больше 47 градусов.
Значит, в момент наблюдения угол Венера-Земля-Луна был не меньше 43 градусов. А не единицы градусов, которые « рядом » на небе! Так что Венеру исключаем.
St. Petersburg mathematicians and their discoveries
Книжка про математиков Петербурга и их открытия — завершена.
Теперь напечатаем малым тиражом и разошлём авторам и всем причастным.
Кому интересно иметь её в бумажном виде — печатайте сами себе в каком-нибудь самиздате (вроде есть сайты, куда можно pdf загрузить, и потом в мягком переплёте получить по почте).
Женя Кац напомнила про видео — мыльные пузыри в сильный мороз можно заморозить(!). Я вот вживую такого никогда не видел…
Читать полностью…
https://mccme.ru/free-books/
Дед Мороз напоминает про страницу, на которой бесплатно доступны файлы множества книг (в основном издательства МЦНМО)
брошюры библиотеки «Математическое просвещение» и Летней школы «Современная математика», доклады семинара «Глобус» и материалы выездного семинара учителей, книги Арнольда и Гельфанда, Прасолова и Шеня и многое другое.
новогодние каникулы — как раз хорошая возможность спокойно почитать
Так вот — на самом деле, то, что мы тут исследовали ним на двух кучках, совершенно неважно! То же самое правило наименьшего исключенного (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; в игре в правой части очевидно выигрывает начинающий (т.е. мы — ход сейчас наш), а у нас есть теорема, что замена игры на равную не изменяет победителя. Но так у нас есть не только теорема, но и явная конструкция стратегии.
Итак, мы увидели, что ним с несколькими кучками камней эквивалентен ниму с одной кучкой из правильно выбранного количества (XOR-а) камней. А случайно ли, что у нас так получилось? Оказывается, нет — существование такой эквивалентности это общее утверждение.
Теорема Шпрага-Гранди. Для любой равноправной игры существует эквивалентная ей игра в ним с одной кучкой (правильно выбранного начального количества) камней.
Замечание. Если это количество камней нулевое — то в игре выигрывает второй игрок, если нет — то начинающий.
Но прежде, чем доказывать эту теорему — давайте посмотрим с этой точки зрения на нахождение проигрышных позиций в ниме с тремя кучками камней. В каждом столбце есть проигрышная позиция — и то, на каком она уровне, как раз и указывает нам, сколько камней нужно взять в третьей кучке, чтобы она равнялась сумме игр-первой и второй кучек (потому что тогда всё в целом даёт нулевую игру, a.k.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 выигрывает один и тот же игрок.
Если у нас равноправная игра (где мы в слово "игра" включаем и начальную позицию), то в ней либо выигрывает начинающий, либо второй игрок. А вот если игра не обязательно равноправная (такие игры называют пристрастными), то вариантов больше.
Следуя всем текстам выше, будем называть игроков Левый и Правый — скоро станет понятно, почему.
Так вот — вариантов 4, но вместо того, чтобы группировать их как "начинает Левый, выигрывает Правый", и т. д., мы их сгруппируем так:
- кто бы ни начинал, он выигрывает ("выигрывает начинающий")
- кто бы ни начинал, он проигрывает ("выигрывает второй игрок")
- кто бы ни начинал, выигрывает Левый
- кто бы ни начинал, выигрывает Правый.
И вот то, ради чего всё затевалось:
Определение. Игра называется нулевой, если в ней выигрывает второй игрок.
Теорема. Пусть игра B нулевая. Тогда для любой игры A в сумме игр A+B выигрывает тот же игрок, что и в самой A.
Доказательство. Тот, кто выигрывает в A, следует там своей выигрышной стратегии — а на доске для B ходит только в ответ, следуя выигрышной стратегии как второго игрока.
Эта теорема показывает, почему мы называем такие игры нулевыми — их прибавление ничего не изменяет. И да — логично обозначать то, что игра A нулевая, записью A=0.
Правило проигрышной позиции можно переформулировать в более симметричном виде:
в ниме позиция (x,y,z) проигрышная тогда и только тогда, когда побитовая сумма количеств камней XOR(x,y,z) — нулевая.
На самом деле — это правило работает и для большего количества кучек, причём дословно так же: побитовая сумма всех количеств должна быть нулевой. И это несложно доказать по индукции — проверив, что если мы объявим такие позиции проигрышными, то:
- из проигрышной все ходы будут вести в выигрышные (достаточно посмотреть на любой из изменившихся битов в той кучке, где был сделан ход),
- из выигрышной всегда есть ход в проигрышную (смотрим на то, откуда пришёл старший бит у ненулевого XOR-а, и делаем ход в эту кучку — зная из XOR-а, докуда именно мы хотим её уменьшить).
И из этого несложно увидеть, что это действительно выигрышные и проигрышные позиции. (Собственно, я в детстве в какой-то из детских математических книг — кажется, у Гарднера? — как раз такое рассуждение и увидел.)
Но мне хочется это увидеть другим способом — потому что на этом пути возникает красивая наука: сложение игр, хакенбуш, сюрреальные числа, и так далее.
И помните, мы видели, что проекция тетраэдра Серпинского вдоль линии, соединяющей середины противоположных рёбер, которая оказывается квадратом (и это соответствие почти что взаимно-однозначное, кроме довольно немногих точек)? Это как раз соответствует правилу "в каждом столбце в кубе со стороной 2^n ровно одна проигрышная позиция".
Читать полностью…
После этого, из каждого из уголков
(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) — в котором опять в каждом столбце уже есть одна проигрышная позиция. Вот и шаг индукции.
вот как эта кривая выглядит (два варианта картинки: для четной и для нечетной степени)
Читать полностью…
📝 Запись лекции про геометрические неравенства
🎤 Неделю назад Григорий Мерзон прочел очень интересную лекцию про изопараметрическое неравенство и формулу Штейнера.
📚 Все материалы лекции выложены на страничке докладчика. Там вы найдёте слайды с лекции, ссылки на популярные книги и статьи в Кванте, видео 3Blue1Brown и серьезный обзор по теме.
#открытые_лекции #YouTube
https://mccme.ru/nir/seminar/
в четверг (21.12) последний в этом году семинар учителей математики
Николай Андреев и друзья. Геометрия: шарнирные механизмы; особенности; картография; модели сезона-2023
как обычно: 19:00, столовая МЦНМО, приглашаются все желающие