Вася составил список из всех 12-элементных подмножеств 26-элементного множества, каждое записал по одному разу. Петя добавляет по одному элементу в каждое множество списка. Докажите, что Петя может так выполнить добавления, чтобы среди полученных 13-элементных множеств не было одинаковых.

Представим 12–элементные и 13–элементные множества в виде двудольного графа. Все 12–элементные множества поместим в долю L, все 13–элементные – в долю R. Будем проводить ребро между вершинами долей R и L в том случае, если из 12–элементного множества можно получить 13–элементное добавлением одного элемента.
Тогда из каждой вершины доли L выходит по 14 ребер, так как из 12–элементного множества можно получить 14 13–элементных множеств путем добавления одного из оставшихся 14 элементов. Из каждой вершины доли R выходит по 13 ребер, так как из 13–элементного множества можно получить 12–элементное путем удаления одного из 13 элементов.
Докажем, что ∀X ⊆ L : |G(X)| ≥ |X|, где G(X) ⊆ R – множество соседей X. Из каждой вершины множества X выходит ровно по 14 ребер, тогда всего из множества X выходит 14 · |X| ребер. С другой стороны, из каждой вершины множества G(X) выходит не более 13 ребер, тогда из множества G(X) выходит не более 13 · |G(X)| ребер. Так как все ребра соединяют вершины множеств X и G(X), то 14 · |X| ≤ 13 · |G(X)| ⇔
⇔ |G(X)| ≥ 14/13 · |X| ≥ |X|.
Получим, что ∀X ⊆ L : |G(X)| ≥ |X|