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

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример. Пусть все волшебники с -го по -го поменяют сущность -го. Легко видеть, что в результате он в любом случае станет рыцарем.

Применим принцип крайнего: выберем среди всех троек точек треугольник с самым большим углом

Предположим, что точки , , не подходят. Тогда существует точка в объединении частей плоскости, одна из которых заключена между прямыми и а другая — между прямыми и

При этом не может лежать внутри треугольника , иначе .

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

получаем противоречие. То же работает для случая, когда лежит между лучами и .

Оставшиеся два случая (когда и лежат в разных полуплоскостях относительно ) рассматриваются аналогично: в них

Рассмотрим раскраску таблицы в три цвета, как показано на рисунке:

1	2	3	…	1
2	3	1	…	2
3	1	2	…	3
1	2	3	…	1

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

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

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

Итак, пусть выбрано наборов. Рассмотрим произвольную карточку Меняя некоторые наборы на дополнительные, можно добиться того, что карточка будет присутствовать во всех наборах. Перечислим с учётом кратности все остальные карточки, встречающиеся в этих наборах. Всего будет перечислено карточек. Кроме карточки у нас имеется карточек, значит, какая-то из них встретится не менее раз(так как ), назовём её карточкой Напишем на карточках и число тогда те (или более) наборов, в которых встречаются обе эти карточки, будут плохими. Уберём карточки и останется карточек и (или менее) набора, среди которых должен найтись хотя бы один хороший.

Аналогично зафиксируем одну из оставшихся карточек и переделаем наборы так, чтобы карточка входила во все наборы. Выписав все остальные карточки, встречающиеся в наборах, получим карточки. Поскольку, помимо карточки у нас имеется карточек, какая-то из них — назовём её — встретится раз(так как ). Напишем на карточках и число 7 — в результате все эти наборы станут плохими. Уберём карточки и останется карточек и набора, среди которых опять должен найтись хороший.

Действуя аналогично, получим, что какие-то две карточки встретятся вместе хотя бы в наборах, напишем на них число и выкинем, останется карточек и наборов. Тогда, поскольку какая-то пара карточек встретится в одном наборе хотя бы раз. Написав на этих карточках число и выкинув, мы получим карточек и наборов. Какая-то очередная пара карточек встретится в одном наборе хотя бы раз, напишем на них число 4 и выкинем, в результате получим карточек и набора. Далее какая-то пара карточек встретится в одном наборе хотя бы раз, записываем на них число и выкидываем, останется карточки и набор. Напишем на двух карточках из этого набора число а на двух других — число тогда и этот набор также окажется плохим. Мы доказали, что всегда можно так занумеровать карточки, что все наборов окажутся плохими.

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

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

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

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

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

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

Оценка.

Покажем, что ходов обязательно придётся сделать.

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

Второй способ. Предположим, что мы сделали менее ходов. Тогда найдётся строка, которую мы не задействовали. Но в этой строке в результате появилось чёрных клеток, значит, было сделано как минимум “вертикальных” ходов. Аналогично показывается, что было сделано как минимум “горизонтальных” ходов, т.е. всего не менее ходов.

Пример.

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

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

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

Пронумеруем олигархов и их города числами от до соответственно.

Пример.

Пусть дорога между городами и принадлежит олигарху под номером тогда и только тогда, когда Тогда количество дорог равно

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

Оценка 1.

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

Рассмотрим произвольную тройку олигархов и Докажем, что эта тройка сопоставлена не более чем одной дороге.

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

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

Оценка 2.

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

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

База очевидна.

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

ребер.

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

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

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

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

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

Итак, не умаляя общности будем считать, что все вершины различны, причем и Рассмотрим три случая.

(а) Тогда проведем перестройку в графе (это возможно, так как ) и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

(b) . Тогда — чередующийся цикл, меньший чем противоречие.

(c) Тогда проведем перестройку в графе (это возможно, так как и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

Назовем кусок шоколадки если его можно разрезать, и если нельзя. Изначально есть только один большой кусок, а в конце игры их Карлсон может играть так, чтобы четность количества больших кусков после его хода обязательно менялась: один большой кусок уничтожается ходом Малыша, после чего появляется от до новых больших кусков. Если количество новых больших кусков нечетно, то один точно есть и Карлсон его съест. Если же количество больших кусков четно, то есть хотя бы один малый и Карлсон съест именно малый кусок. Итак, число больших кусков после каждой пары полуходов меняет четность, а по окончании игры чётность чисел больших кусков должна измениться, значит, будет сделано нечётное количество ходов, т.е. Карлсон выиграет.

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

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

Такую же конструкцию провернём в другую сторону: возьмём ромб, примыкающий к отрезку с другой стороны, и отметим в нём параллельную сторону и т.д.

Мы получили “полосу ширины ”, которая рассекает наш шестиугольник. При этом цикл заведомо пересекает эту полосу, но всё время в направлении слева направо. Это невозможно.

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

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

Предположим, что это не так, и рассмотрим в качестве наименьший по числу вершин контрпример. Ясно, что граф содержит больше одной вершины и связен (иначе одна из компонент связности была бы меньшим контрпримером). Удалим из графа произвольную вершину пусть новый граф распался на компоненты Пусть , — подграфы в соответственно на соседях вершины Несложно видеть, что

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

Мы проверили, что при всех Тогда по формуле т. е. граф оказался неконтрпримером.

Выберем учеников из первого кружка, рассадим их в разные кабинеты. Выберем других человек из второго кружка и рассадим их, и так далее.

Рассмотрим комнат, где число определим позже. Посадим каждого школьника в одну из этих комнат, выбирая ее случайно (все комнаты равновероятны). Назовем комнату подозрительной, если в ней оказались представители не всех кружков. Предположим, что случилась УДАЧА: оказалось не более чем подозрительных комнат. Тогда имеется неподозрительных комнат, мы можем назвать их кабинетами, и искомая рассадка найдена. УДАЧА заведомо иногда случается, если математическое ожидание числа подозрительных комнат меньше Заметим, что равно количеству комнат умноженному на вероятность того, что конкретная комната подозрительна. Эта вероятность, в свою очередь, не превосходит Итак, если

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

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

Допустим, что среди туристов имеется (или более) «богачей». Нарисуем граф: вершины — это города, из каждого города проведем самый дорогой выходящий путь. Тогда этот граф представляет собой лес, в каждом дереве которого все ребра направлены к корню, за исключением единственного ребра, выходящего из корня, — это ребро в дереве как бы двустороннее. Возьмем богача, который расположен ближе всего к корню своего дерева. Этот богач будет в течение ходов самым близким к корню. Значит, он проедет по городам, в которых еще не было других богачей. Это может быть только если граф — это путь из вершин, богачи занимают первые вершин этого пути (т. е. половину) и гуськом движутся по этому пути в сторону второй половины. Отсюда следует, что богачей не может быть больше а также что количество переездов тоже не превосходит

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

Обозначим города Допустим, что путь

составлен из самых дорогих авиалиний, для определенности пусть цена перелета равна рублей. А «бедный путь» пусть сначала проходит по городам с большими четными номерами, потом — по городам с большими нечетными, а далее — с малыми: сначала с четными, потом с нечетными:

Цены этих авиалинии пусть убывают от до рубля при движении вдоль этого пути. Цены остальных авиалиний назначим произвольно в диапазоне от до рублей.

Оценка
Назовем ободком множество клеток, находящихся в одном ряду, а также на продолжении этого ряда за одно или несколько ребер. Каждая ладья держит под боем клетки двух ободков. Всего на поверхности куба имеется ободков (есть три возможных направления, по ободков в каждом). На каждом ободке может стоять не более одной ладьи, и любая ладья стоит на двух ободках. Поэтому ладей не может быть больше

Пример
Рассмотрим три соседние грани и поделим каждую на квадрата . Далее в трех квадратах, указанных на рисунке, поставим ладьи на одной из главных диагоналей.

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

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

Пусть имеется способов выбрать граммов без использования гири в г и способов набрать граммов с использованием гири в г.

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

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

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

Сложив полученные два неравенства, имеем требуемое.