[Перевод] Для победы в этой игре с числами нужно научиться избегать закономерностей
Тяжело оценивать последовательности, не содержащие закономерностей, поэтому математики в поисках ответов на свои вопросы полагаются на простые ограничения
Если за окошком дождь, или объявлена самоизоляция, то рекомендуем вам такую простую числовую игру. Допустим, вы и я по очереди вычёркиваем числа из списка {1, 2, 3, …, 9}. Победит последний человек, вычеркнувший число так, чтобы три вычеркнутые числа не шли подряд. Играем! Вы первый.
Допустим, после четырёх ходов мы вычеркнули следующие числа:
1 2 3 4 5 6 7 8 9
Снова ваш ход. Если вы вычеркнете 4, вы проиграете, поскольку тогда вы составите последовательность из трёх чисел, 3–4–5. Также вы проиграете, вычеркнув 7, из-за последовательности 7–8–9. Безопасно будет вычеркнуть только 1, 2 или 6. Однако вне зависимости от того, какое число вы вычеркнете, я вычеркну одну из оставшихся и выиграю, не оставив вам безопасных ходов.
Это простая игра с интересной математической подоплёкой. Один из подходов — делать промежутки, так, чтобы у соперника не оставалось вариантов, кроме как вычёркивать третье число из последовательности, типа такого:
1 2 3 4 5 6 7 8 9
Другой подход — делать ходы рядом с ходами противника, чтобы заставить его закончить последовательностью из трёх чисел с любой стороны, к примеру:
1 2 3 4 5 6 7 8 9
Но вне зависимости от стиля игры, один факт будет математически предопределён: после шести ходов кто-то должен выиграть. Невозможно вычеркнуть семь или девять чисел так, чтобы среди них не оказалось идущих подряд трёх чисел (проверьте, если не верите — в конце статьи будут упражнения на этот счёт). В этом случае мы говорим, что 6 является «верхней границей» количества ходов, которые можно сделать в этой игре.
Так что, хотя иногда наилучший ход нам и не известен, мы точно знаем, что наша игра не продлится больше шести ходов. Мы можем расширить эту задачу. Игра, использующая числа от 1 до 15, не может идти дольше 10 шагов, и в целом, если размер игрового поля делится на 3, то вычеркнуть можно максимум 2/3 чисел. Обнаружение подобной верхней границы — это шаг к пониманию игры. К примеру, мы могли бы использовать верхнюю границу для поисков выигрышной стратегии, или как основу для рассуждений о том, что будет, если игровое поле не является множителем тройки. И хотя может показаться, что информация о верхней границе не такая уж ценная, это гораздо больше, чем можно сказать о похожих играх с немного другими правилами.
Давайте, к примеру, изменим правила так, чтобы проигрывал первый игрок, зачёркивающий три числа, идущих в последовательности с любым шагом. То есть, вы проигрываете, если зачёркиваете не только 2–3–4 (шаг 1), как в оригинале, но и 1–3–5 (шаг 2), или 1–4–7 (шаг 3). Такие последовательности называются арифметическими прогрессиями. Это последовательность чисел с одинаковым размером шага, или «разности прогрессии».
Вернёмся к самому первому игровому полю и применим новые правила. Вы ходите первым. И вы проиграли.
1 2 3 4 5 6 7 8 9
Если зачеркнуть 1, получится последовательность 1–3–5. Если 2 — 2–5–8. Если 4 — 3–4–5. Если 6 — 3–6–9. Если 7 — 7–8–9. Любой ход завершает арифметическую прогрессию. Обратите внимание, что в такой игре приходится отслеживать уже гораздо больше. В итоге игра значительно усложняется. А верхнюю границу количества безопасных шагов найти становится гораздо труднее.
Самое интересное для математиков — это превратить простую игру с числами в игру против самой математики. Их цель — выяснить, как долго можно играть в игру, пока кто-нибудь не проиграет, на игровой доске произвольного размера. Иначе говоря, если у нас есть список чисел любой длины, сколько чисел вы сможете вычеркнуть, пока не наткнётесь на арифметическую прогрессию? Правила звучат довольно просто, но на самом деле ответа на этот вопрос мы не знаем. А о вариантах этой игры нам известно ещё меньше. Давайте ещё немного поиграем и увидим, куда нас заведёт математика.
В нашей игре с арифметической прогрессией набор безопасных ходов представляет собой, по сути, множество Салема-Спенсера. Это подмножество множества {1, 2, 3, 4, 5, 6, 7, 8, 9}, не содержащее арифметическую прогрессию. Тогда верхняя граница — это просто наибольшее из возможных подмножеств Салема-Спенсера на нашем игровом поле. Однако поиск правильных ходов, позволяющих нам найти это множество, может оказаться довольно трудным делом. Посмотрим, почему.
Начнём с нового поля. Никто не может проиграть в первые два хода, поэтому давайте просто вычеркнем 3 и 5.
1 2 3 4 5 6 7 8 9
Теперь нам надо выбрать третье число — и тут пора начинать думать. Как и в оригинальной игре, нам нужно не закончить прогрессию, и не зачёркивать число между зачёркнутыми или с любой стороны от уже зачёркнутых. К примеру, мы не можем выбрать 4, потому что получим последовательность 3–4–5; мы не можем выбрать 1, поскольку получим 1–3–5; мы не можем выбрать 7, поскольку получим 3–5–7. 8 — безопасный выбор, так что давайте сделаем его.
1 2 3 4 5 6 7 8 9
Теперь всё усложняется. Беспокойство у нас всё по тому же поводу — нужно постараться не закончить прогрессию, и не зачёркивать числа между зачёркнутыми или с обеих сторон от них. Однако нам нужно отслеживать уже гораздо больше прогрессий. Теперь нужно постараться не закончить прогрессию, учитывая три существующие пары зачёркнутых чисел.
С одной стороны, понятно, чего можно ожидать. Для каждой пары нам надо избегать таких ходов, которые дадут нам прогрессию в середине или с обоих концов. Однако всё не так предсказуемо, как нам хотелось бы. 3 и 5 устраняют три варианта: 1, 4 и 7. Но 3 и 8 ничего не устраняют, поскольку с ними нам нужно избегать таких чисел, как −2, 5.5 и 13, а их даже на поле нет. 5 и 8 устраняют только 2, поскольку мы не можем выбрать 6.5 или 13.
Мы знаем, что каждый из вариантов выбора устраняет какие-то варианты в будущем, однако, сколько именно — зависит от того, что выбрать. Из-за такой неоднородности сложно подсчитать все возможности и определить верхнюю границу для всех возможных игровых полей.
Вернёмся к нашей игре. Видно, что 6 — ход безопасный, поэтому мы его вычёркиваем.
1 2 3 4 5 6 7 8 9
Вот и всё. Больше безопасных ходов не осталось. Мы уже знаем, что 1, 2, 4 и 7 проигрывают, а выбор 9 даёт нам прогрессию 3–6–9. Мы зашли так далеко, как могли.
Это означает, что множество наших ходов, {3, 5, 6, 8}, является множеством Салема-Спенсера. Но максимально ли оно? Мы не можем увеличить это множество, однако может ли другая стратегия привести к большему множеству? Есть ли у {1, 2, 3, 4, 5, 6, 7, 8, 9} такое подмножество большего размера, в котором никакая тройка чисел не даёт арифметическую прогрессию?
Есть: {1, 2, 6, 8, 9}. Это множество из пяти безопасных ходов в нашей игре, и, следовательно, множество Салема-Спенсера. И оно максимально, поскольку уже известно, что для {1, 2, 3, 4, 5, 6, 7, 8, 9} максимальным размером множества Салема-Спенсера будет 5. Но в общем случае для множества из n элементов {1, 2, 3, …, n}, ответ нам не всегда известен. На самом деле на сегодняшний момент нам известны ответы для множеств с n ≤ 209.
Математики хотели бы знать точный размер максимального подмножества Салема-Спенсера для {1, 2, …, n}, но в общем случае лучшее, на что они способны — это установить определённые границы. И даже это сложно сделать, в частности из-за нерегулярного поведения, которое мы с вами уже наблюдали. Вычёркивание нового числа может устранить много вариантов, или же немного. Нерегулярность можно оценить по графикам ниже, показывающим размеры крупнейшего из возможных подмножества Салема-Спенсера для множества {1, 2, 3, …, n} для разных n.
В нашей игре, где n = 9, размер крупнейшего возможного множества Салема-Спенсера равняется 5. Однако посмотрите — если мы добавим на игровое поле 10, это не поменяет размер крупнейшего возможного множества Салема-Спенсера. Он так и останется равным 5.
С другой стороны, при переходе с 12 до 13 и 14, максимальный размер растёт с 6 до 7 и 8. А потом придётся добавить ещё целых шесть чисел к множеству, чтобы увеличить максимальный размер подмножества Салема-Спенсера всего на 1.
Такие достижения, как теорема Рота и теорема Семереди устанавливают границы размеров этих множеств и их вариаций, часто используя для этого сложную математику (к примеру, эргодическая теория и преобразования Фурье) и огромные значения. К примеру, обладатель филдсовской премии Тимоти Гауэрс в своей работе об обобщении теоремы Семереди установил важную верхнюю границу размера множества длины k, не содержащего арифметическую прогрессию. Но если бы мы захотели вычислить эту верхнюю границу для нашей игры, где n=9 (размер игрового поля), а k = 3 (длина арифметической прогрессии, которой мы хотим избежать), нам пришлось бы проводить вычисления, в которые вошла бы величина 24096 — число, состоящее из более чем 1200 цифр!
Эти границы нельзя назвать полезными для повседневных задач, однако они дают нам некий математический контроль над множествами, которые мы пока ещё не очень хорошо понимаем. К примеру, до недавнего времени у нас не было таких границ для «многочленных последовательностей», обобщения арифметической прогрессии, в котором также используется сложение и возведение в степень. Оказывается, что многочленные последовательности, такие, как 2+3, 2+3², 2+3³, и так далее, ещё сложнее отслеживать, чем наши простые арифметические прогрессии, что делает игру с выбором подмножеств, свободных от многочленных последовательностей, ещё более сложной для понимания. Однако установление верхнего предела — это ещё один шаг к их пониманию, а это и есть цель математиков в любой игре с числами.
Упражнения
1. Докажите, что в игре с использованием {1, 2, 3, 4, 5} по первоначальным правилам (проигрывает тот, кто первым вычеркнет три числа из последовательности с шагом 1), у первого игрока есть выигрышная стратегия.
Если первый игрок вычёркивает 3, он всегда может выиграть. Если в ответ второй игрок вычёркивает 1 или 5, то первый вычёркивает другое число из этой пары. Если второй игрок вычёркивает 2, первый вычёркивает 5. Если второй вычёркивает 4, первый вычёркивает 1.
2. Есть ли у кого-либо из игроков выигрышная стратегия в игре с использованием {1, 2, 3, 4, 5, 6} по первоначальным правилам?
У второго. Допустим, первый выбирает одно из чисел {1, 2, 3}. Тогда второй должен выбрать число из того же набора рядом с тем, что выбрал первый. К примеру, если первый выбрал 3, то второй выбирает 2. Теперь первому приходится выбирать число из {4, 5, 6}. Какое бы он ни выбрал, у второго игрока будет выигрышный ход. Если первый сразу выбирает число из {4, 5, 6}, то та же стратегия срабатывает для второго игрока — он тоже должен выбрать число из {4, 5, 6}.
3. Докажите, что в игре с {1, 2, 3, 4, 5, 6, 7, 8, 9} по первоначальным правилам невозможно сходить семь раз. Подсказка: поделите игровое поле на следующие подмножества: {1, 2, 3}, {4, 5, 6} и {7, 8, 9}.)
Если вычеркнуть три числа из любого из трёх подмножеств из подсказки, то вы проиграете. Мы можем теоретически сделать шесть ходов, вычеркнув по два числа из каждого подмножества. Но какое бы подмножество вы ни выбрали седьмым ходом, вы получите три числа подряд. Такой аргумент известен под названием «леток в голубятне» — чтобы распихать семь голубей по трём отверстиям, в одно из них придётся запихнуть трёх голубей. Заметьте, что это рассуждение напоминает выигрышную стратегию из 2-го упражнения.
4. Найдите подмножество Салема-Спенсера максимального размера для {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.
Одна из стратегий — начать с крайних чисел, поскольку они никогда не могут оказаться в середине арифметической прогрессии. Берём 1 и 11, что устраняет вариант 6. Применим такую же стратегию, вычеркнем 2 и 10, что устранит 3 и 9, но и только. Из оставшихся вариантов {4, 5, 7, 8} можно выбрать ещё два, например, 4 и 5. Судя по таблице выше, 6 — это максимальный из возможных размеров подмножества Салема-Спенсера.
