Комбинаторика на Турломе: графы, игры, клетчатые задачи, Дирихле

Рассмотрим множество в котором лежат все числа из увеличенные на Тогда, если то согласно условию Получается, и Отсюда условие переписывается в виде:

содержит все натуральные числа от до

если то в лежат все члены арифметической прогрессии, первый член которой равен а разность равна

Верно ли, что для любого такого множества существует такое натуральное число что в лежат все натуральные числа, не меньшие

Заметим, что арифметическая прогрессия из условия — это просто все числа, кратные Возьмём в качестве все натуральные числа, не меньшие кроме простых чисел, больших Легко видеть, что оно подходит под оба условия, но в силу бесконечности множества простых, не подходит под утверждение.

Сначала заметим, что мы можем сделать циклический сдвиг букв в слове. Действительно, пусть у нас есть слово . Удвоим его и удалим буквы слева. Получили слово .

Теперь приведём алгоритм. Пусть у нас имеется слово , имеющее вид . Сделаем копию раз, получим слово , состоящее из копий , идущих подряд. Рассмотрим самое крайнее слово справа, из него будем делать нужную перестановку. Пусть мы хотим получить некоторую перестановку . Пусть — минимальный индекс такой, что . Уберём в самом правом слове все буквы от до . Теперь сделаем циклический сдвиг, переместим в конец слова . Далее будем следовать аналогичному алгоритму, найдём в слове букву (она будет среди первых слева букв), удалим все буквы перед ней и сдвинем её в конец слова и так дальше.

Спустя не более циклических сдвигов последних букв слова будут нужной перестановкой, останется только удалить лишние буквы слева и мы получим требуемое.

Осталось объяснить, почему длины слова хватит. На первом шаге мы удаляем не более букв справа и менее букв слева, а на остальных шагах — менее букв слева. Таким образом, всего будет удалено не более букв. Длина слова равна . Неравенство вытекает из неравенства , которое можно доказать индукцией по . Таким образом, мы сможем выполнить циклических сдвигов и при этом точно останутся букв, составляющих нужную перестановку.

Оценка. Для начала докажем, что больше самопересечений быть не может. Назовём звенья одного направления горизонтальными, а звенья второго направления — вертикальными. Расположим плоскость так, чтобы горизонтальные звенья действительно стали горизонтальными. Заметим сразу две вещи:

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

Пронумеруем сверху вниз горизонтальные звенья от до . Посмотрим на звено с номером . Каждое пересекающее его вертикальное ребро должно иметь над ним конец, совпадающий с концов некоторого горизонтального ребра. Горизонтальных рёбер выше всего , поэтому на -м ребре не более точек самопересечений. Эта оценка хорошо работает для от до : на них суммарно не более

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

Для ребра с номером немного улучшим оценку: всего существует вертикальных рёбер, но два из них выходят из концов -го звена, поэтому не могут его пересекать. Итого, на звене не более точек самопересечений. Значит, суммарно их не больше

Пример. Пронумеруем и вертикальные звенья тоже. Пусть -е вертикальное ребро соединяет и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья.

Аналогичный пример для -звенной ломаной на картинке ниже:

Поскольку различных значений у слов конечное количество, то среди слов найдутся два с одинаковым значением. Пусть это слова из и букв

Докажем, что слово имеет то же значение, что и слово из букв Если для такой пары оказывается, что то это верно. В противном случае при

То есть одинаковые значения имеют слова из букв. Отсюда и следует верность утверждения, если продолжать до тех пор, пока

Тогда:

Что и требовалось доказать.

Легко видеть, что Ярослав будет находится вначале у замка потом —

Если то следующим действием Ярослав закроет замки с номерами и, возможно, ещё какие-то. В любом случае, замок под номером останется закрытым.

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

Заметим, для начала, что если на доске чётное количество чисел, то ходит Марина, а если нечётное — Саша.

Докажем, что если на доске ровно одна единица, то выигрывает Саша. Если сейчас ход Марины, то она не может убрать ровно одну единицу, поэтому после её хода тоже останется ровно одна единица. Если сейчас ход Саши, то или игра уже закончилась (и на доске всего одна единица), или помимо этой одной единицы есть ещё хотя бы два нуля, которые Саша и перемножает, передавая Марине ситуацию с одной единицей.

Тогда, если то Саша сразу находится в выигрышном для себя положении, а если то он должен первым ходом перемножить две единицы и передать Марине ситуацию ровно с одной единицей.

Докажем теперь, что если или то выигрывает Марина. Заметим, что если в какой-то момент на доске окажутся одни нули, то Марина выигрывает. Тогда при Марина точно уже выиграет.

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

Пусть сейчас ход Саши. Если он оставляет ситуацию разнообразной - хорошо. Если же он сделал ситуацию не разнообразной, то поскольку убрать ноль он не может, как и убрать сразу две единицы, то сейчас на доске ровно две единицы, а остальные нули. Марина своим следующим ходом заменяет эти две единицы на и теперь на доске одни нули.

Пусть сейчас ход Марины. Перед ней точно есть Если есть какие-то ещё числа, то их чётное количество, то есть хотя бы два, поэтому она может сделать ход с ними, оставив ситуацию разнообразной. Если же других чисел нет, то Марина меняет на оставляя Саше тогда он делает ход и оставляет и Марина выигрывает, делая после этого

Осталось заметить, что при и ситуация на доске уже разнообразная, а при Марина может сделать её разнообразной своим первым ходом.

Докажем, что если Саша переключает последовательно строки и столбцы, то количество затраченной энергии будет минимально. Для этого докажем даже более сильный факт: при таком алгоритме количество горящих лампочек в каждую минуту минимальное из возможных.

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

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

Докажем, что не может быть больше людей, совершивших ровно рукопожатий. Допустим обратное, то есть что имеется хотя бы человек, сделавший ровно рукопожатий. Рассмотрим одно из них. Кроме него имеется всего человек в классе, при этом он совершил рукопожатий и есть ещё человек, который сделали ровно столько же рукопожатий. Тогда по принципу Дирихле, так как найдётся человек, совершивший столько же рукопожатий, и которому он жал руку, что противоречит условию задачи.

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

Заметим, что , просто потому что больше, чем рукопожатий совершить невозможно. Причём если , то по утверждению, доказанному ранее. Далее получаем, что и не больше, чем причём , так как если бы было равно хотя бы то и тоже были бы равны а таких людей по доказанному утверждению может быть не более, чем Аналогично можно доказать, что

Тогда

Но сумма, стоящая справа, равна сумме степеней вершин графа из примера, приведённого выше, а она в два раза больше количества рёбер в графе (так как сумма степеней вершин графа равна удвоенному количеству его рёбер).