Дискретная математика | Александр Куликов. Лекция 1

31:20 На поле любого размера n≥1, для любых m≥0, k≥0, количество жёлтых и синих фишек соответственно, всё поле заполнено m+k=n^2, всегда найдётся путь. Не умаляя общности можно доказывать только для k≤m. При k=1 и любом n≥2 есть жёлтый путь. Докажем индукцией по n. При n=2 очевидно выполняется, пусть есть жёлтый путь для n−1, ситуация n сводится к n−1 вычёркиванием крайних столбца и строки жёлтых фишек, поэтому существующий путь n−1 можно одной клеткой из крайнего столбца или строки достроить до пути в n. Теперь n фиксировано, докажем по индукции по k, база k=1 уже доказана, теперь индукционный переход. Назовём жёлтую клетку ключевой, если все существующие жёлтые пути проходят только через неё. Рассмотрим произвольное заполнение поля с k синими фишками, перекрасим какую-нибудь фишку в жёлтый цвет. Мы получим заполнение с k−1 фишками, для которого по индукционному предположению существует путь. Если этот путь синий, то ничего не изменится после возврата цвета фишки. Если путь жёлтый, но не проходящий через перекрашенную фишку, то тоже ничего не изменится. Наконец, если перекрашенная фишка была ключевым элементом, то можно утверждать, что в исходном заполнении нет ни одного жёлтого пути. Рассмотрим рёбра ключевого элемента, они делятся на три группы, первая − синие границы с синими фишками или синими краями поля, вторая − жёлтые входящие, откуда приходят все жёлтые пути и третья − жёлтые исходящие. Пусть все жёлтые пути идут в направлении снизу вверх. Очевидно жёлтые входящие рёбра с исходящими не могут иметь общей вершины, иначе фишка не была бы ключевым элементом, поэтому жёлтых граней не больше четырёх и если их четыре, то они не могут чередоваться через один относительно своего направления, следовательно есть как минимум два синих ребра, разделяющих входящие и исходящие грани. Если через эту пару рёбер провести прямую, то жёлтые грани определённых направлений будут лежать по одну сторону от прямой, а противоположенных по другую. Рассмотрим синюю грань, пойдём вдоль неё и возможно дальше по другому смежному с ней синему ребру против часовой стрелки вокруг центра симметрии до границы с жёлтой гранью, назовём последнюю начальной, двигаясь по часовой стрелки найдём конечную грань. Если начальная и конечная грани одного направления, то назовём такое синее ребро нижним для входящих и верхним для исходящих. В случае разных направлений для исходящего и входящего начала, назовём их соответственно правое и левое ребро. Всегда найдётся пара синих граней, одна из которых правое, а другое левое ребро, такова разделяющая направления пара. Пойдём по правому ребру против часовой стрелки, пока не упрёмся в жёлтую исходящую грань, пойдём дальше вдоль границы между жёлтыми и синими фишками или краем поля, держа синюю область по правую руку от направления обхода, тогда возможны случаи: 1) В синий левый край поля попасть не можем, потому что начинали обход с правого ребра, а вся правая связная область синих фишек лежит по одну сторону от жёлтого пути, противоположенную левому краю. Мы можем вернуться к правому ребру, сделав замкнутый цикл и возможно пройдя вдоль жёлтых краёв поля. 2) Но цикл невозможен из-за ключевого элемента. Цикл подошёл бы к входящей грани, тем самым получили бы другой путь в обход ключевого элемента, а их не должно быть. 3) Остаётся вариант, когда обход упирается в синий правый край поля. Аналогично поступаем с левым ребром, идём против часовой стрелки, упираемся в жёлтую входящую грань, обходим синюю область с правой стороны и необходимо попадаем на левую границу поля. Очевидно в этом случае возвращение цвета ключевому элементу создаёт синий путь. Можно поменять направление вращения по синим рёбрам с против на по часовой стрелке, тогда упрёмся в конечную грань, входящую для правого и исходящую для левого, а обход синих областей будет левый (область лежит по левую руку относительно направления обхода).

Ещё одна игра с выигрышной стратегией у первого игрока.
Прямоугольная доска mxn заполнена фишками. Игроки ходят по очереди, выбирая одну из фишек на доске и снимая с доски её и все фишки над ней или правее (то есть все фишки в квадранте, левым нижним углом которого она является). Кто берёт последнюю фишку, проигрывает. Докажите, что в этой игре у первого игрока есть выигрышная стратегия (за исключением очевидно проигрышного случая m=n=1).
41:10 Вот ещё задачи на вероятностный метод доказательства:
а) Докажите, что степень тройки с натуральным показателем может начинаться на любую комбинацию цифр.
б) Докажите, что степень двойки может начинаться на те же 2021 цифр, что и оканчиваться (конечно, число при этом должно быть минимум 4042-значное).
в) Докажите, что при любом вещественном α число [αn^2] ([ . ] − целая часть числа) чётно для бесконечного множества натуральных чисел n.
1:05:00 Опечатка, неравенство n!/k!(n−k)!≤n!/k! надо заменить на n!/k!(n−k)!≤n!/(n−k)!≤n^k.