Комбинаторика на Питергоре

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

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

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

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

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

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

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

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

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

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

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