Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела множества
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#101754

Даны пятиэлементные подмножества A ,
 1  A ,...,A
 2     k  множества {1,2,...,23} такие, что пересечение любых двух из них содержит не более трёх элементов. Докажите, что k≤ 2018.

Подсказки к задаче

Подсказка 1

Пятиэлементное подмножество содержит 10 групп из трех элементов, а всего подмножеств k. Значит, вместе они содержат 10k групп! А сколько всего трехэлементных подмножеств есть у 23-х элементного множества?

Подсказка 2

Верно, 1771! Значит, какая-то трехэлементная группа содержится хотя бы в 10k/1771 всех подмножеств. Предположим, что k > 2018, откуда получим, что подмножеств хотя бы 12. Но эти подмножества не могут пересекаться ни по каким другим элементам! Какой вывод можно сделать?

Показать доказательство

Рассмотрим все возможные группы из трех элементов. Таких групп C3 =1771.
 23  Каждое пятиэлементное подмножество содержит C3= 10
 5  таких групп. Так как подмножеств k,  то всего они содержат 10k  групп с учетом кратности. Тогда какая-то группа содержится хотя бы в -10k
1771  всех подмножеств. Рассмотрим эти подмножества. Если k> 2018,  то таких подмножеств хотя бы 12.  С другой стороны, данные подмножества не могут пересекаться ни по каким другим элементам. Помимо трех элементов общей группы осталось 20  элементов, и в каждом подмножестве содержится 2  из этих 20  элементов. Но если подмножеств хотя бы 12,  то какие-то два из этих подмножеств будут пересекаться хотя бы по одному элементу из этих 20.  Тогда соответствующие подмножества будут пересекаться хотя бы по четырем элементам, что противоречит условию. Значит, k ≤2018.

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!