Задача на принцип Дирихле

[2old]

Даны $21$ девятиэлементных подмножеств 30-элементного множества. Тогда какой-то элемент 30-элементного множества содержится по крайней мере в $7$ данных подмножествах. (доказать)

Ясно, что задача на принцип Дирихле, но не могу сообразить что к чему. Если взять $4$ девятиэлементых подмножеств, то какой-то элемент 30-элементного множества содержится по крайней мере в двух из них.

[NSKuber]

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

[azmt]

Пусть имеется множество натуральных чисел от $1$ до $30$. Выделим в этом множестве первые $9$ чисел. Получим первое 9-ти элементное подмножество данного множества. Теперь вместо цифры $9$ будем подставлять оставшиеся числа из данного множества. Получим тогда оставшиеся $20$ подмножеств из 9-ти элементов (например подмножества {1-8,10},{1-8,11}). Видим, что например число $2$ войдёт по крайней мере в $7$ подмножеств данного множества.

[NSKuber]

azmt
И как ваш конкретный пример помогает в решении поставленной задачи?

[Nemiroff]

2old в сообщении #1060395 писал(а):

Если взять $4$ девятиэлементых подмножеств, то какой-то элемент 30-элементного множества содержится по крайней мере в двух из них.

Почему?

[azmt]

Из 30-ти элементного множества можно составить три 9-ти элементных подмножества, в которых 27 элементов из данного множества встречаются только один раз. Чтобы составить четвёртое подмножество, нам придётся выбрать хотя бы один элемент из предыдущих подмножеств, который уже хоть раз встречался.

[Nemiroff]

azmt, я не вас спрашивал.

[provincialka]

2old, может, удобнее представить данные в виде таблички $21\times 30$, строки которой соответствуют множествам, а столбцы -- элементам. Тогда в каждой строке будет проставлено ровно по 9 галочек (понятно, как?). А сколько всего? А сколько может быть в столбцах?

[gris]

мне всегда нравилось представлять, что за участие в подмножестве дают конфетку

[2old]

Nemiroff
Ну потому что полностью различных девяток можно взять только $3$, для четвертой придется снова использовать элементы, которые уже брали.

NSKuber
Не могу сообразить

-- 08.10.2015, 17:02 --

provincialka
О, спасибо! Стало понятнее, чего вообще считать.

Если считать по строкам, то получаем, что использовалось всего $21\cdot 9=189$ элементов. Теперь будем считать по столбцам.
Как советовал NSKuber, предположим, каждый элемент содержится не более, чем в $6$ множествах. Но тогда число использованных элементов не превосходит $6\cdot 30 = 180<189$, значит найдется элемент, который сидит как минимум в $7$ множествах.

[provincialka]

2old
Правильно. Только лучше сказать "использовано всего 189 галочек (значков)". Чтобы не путать с 30 элементами.