Двудольные графы и переформулировки к ним

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

Рассмотрим граф, в котором вершинами являются префиксы. Ребром соединим префиксы, у которых разная чётность. Получился двудольный граф, в котором вершин соответствуют чётным префиксам и — нечётным. В двудольном графе не более рёбер. То есть всего не более промежутков. В качестве примера можно сделать все дни дождливыми.

Пусть осталось дорог между городами. Заметим, что такой граф является деревом(связность между вершинами не исчезает при выполнении операции), а значит, двудольным. Причём обратная операция к исходной будет такая, что находится три смежных ребра и проводится четвёртое между крайними, чтобы получался цикл из четырёх рёбер. Но в таком случае двудольность будет сохраняться, потому что будут появляться только чётные циклы. Докажем это утверждение по индукции. Будем ввести её по количеству добавленных рёбер при обратной операции. База, когда у нас есть просто дерево, и мы проделываем одну обратную операцию, очевидна. Предположение, пусть на -ой обратной операции у нас получались так же только чётные циклы. Рассмотрим граф с -ой операцией и уберём последнее добавленное ребро. По предположению остался граф только с чётными циклами. Попробуем вернуть ребро. Если мы выбрали три ребра, не входящие ни в какой цикл, то получается чётный цикл. Допустим теперь обратное. Тогда получается, что мы на самом деле заменяем три ребра в цикле чётной длины на одно ребро. Чётность количества рёбер не меняется, а значит, и нечётных циклов появиться не могло. Таким образом, так как двудольность сохраняется на протяжении всего процесса, то и изначальный граф должен быть двудольным, но это не так(он полный). Противоречие.

Посмотрим на чёрные клетки. Покрасим их в красный и синий цвета в “шахматном” порядке: угловая клетка пусть будет красной, и далее соседние клетки красим в другой цвет. Мы получим 25 красных клеток и 16 чёрных. Назовём 25 красных клеток первой долей, а 16 чёрных — второй долей. Тогда слон каждым ходом меняет долю, в которой он находится. Значит, обойти все клетки не получится.

Обозначим количество мальчиков через , а девочек — через . Тогда количество рёбер со стороны мальчиков равно , а со стороны девочек оно равно . Так как это на самом деле все рёбра в графе, мы получаем . Из этого равенства следует, что делится на 4. Пусть , тогда из равенства выше получаем, что , а общее количество детей равно — число, делящееся на 7.

Раскрасим черные клетки доски в два цвета. Тогда слон каждый раз будет менять цвет, на котором стоит. Клеток второго цвета 16, поэтому всего слон сможет посетить не более клеток. Слон может посетить 33 клетки.

Обозначим через количество мальчиков, через — количество девочек. Тогда из условия , то есть . Тогда всего детей — делится на 8. С другой стороны всего детей не меньше 17 и не больше 30. Единственное число, делящееся на 8, которое подходит под условие это 24.

Раскрасим кубики в шахматном порядке (угловые кубики считаем черными). Тогда мышка съела 12 белых кубиков и 14 черных кубиков. Но при переходе к следующему кубику меняется цвет, поэтому мышка не сможет съесть весь куб кроме центрального кубика.

Раскрасим треугольнички в шахматном порядке (все крайние треугольнички считаем черными). Тогда легко видеть, что белых треугольничков будет 45. Причем при переходе в новый зал цвет всегда меняется. Тогда турист сможет посетить не более зал. Легко видеть, что турист действительно сможет посетить 91 зал.

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

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

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

Количество допустимых составов, в которых четное число людей , а количество допустимых составов с нечетным числом — . Четность количества людей в команде каждый раз меняется, поэтому и должны отличаться не более, чем на 1, что не так. Поэтому перебрать все допустимые составы команд нельзя.

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

Заметим, что ответ “лжец” мог прозвучать только от рыцаря про лжеца, либо от лжеца про рыцаря. Рассмотрим двудольный граф, в одной доле вершины — рыцари, в другой — лжецы. Так как в каждой паре дважды прозвучало “лжец”, имеем , где — число одних, — число других. Не умаляя общности, вчера не было одного из учеников, аналогично получаем . Решив получившуюся систему, получаем .