Соответствия, сравнения, количества
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
На доске написаны числа 
Вася выписал некоторые множества из четырёх чисел. Оказалось, что любые две четвёрки либо
вообще не пересекаются, либо пересекаются ровно по 
элементам. Какое наибольшее количество четвёрок мог выписать
Вася?
Подсказка 1
Попробуем сначала привести пример. Разобьем числа на 50 пар произвольным образом. Как из этих пар легко получить нужные четверки чисел?
Подсказка 2
Верно! Возьмем всевозможные пары пар, и все получится. Можно заметить, что каждое число входит не более, чем в 49 четверок чисел. А можно ли это доказать в общем случае?
Подсказка 3
Предположим, что есть число, которое принадлежит 50 множествам. Без ограничения общности можно считать, что это 1 и содержится оно в четверки {1,2,3,4}. Тогда есть еще 49 множеств, содержащих 1. А сколько множеств содержат 2, 3 и 4?
Подсказка 4
Верно! Каждое из 49 множеств, содержащих 1, отличных от {1,2,3,4}, содержит одно из чисел 2, 3, 4. По принципу Дирихле есть не менее 17 множеств, которые содержат какое-то из чисел 2, 3, 4. Пусть это число 2. Тогда выходит, что есть достаточно много четверок, содержащих и 1, и 2. Можно ли из этого сделать какой-то вывод?
Подсказка 5
Правильно, 1 и 2 входят всегда вместе! Тогда у нас есть 50 множеств, содержащих и 1, и 2. Может ли такое случиться?
Подсказка 6
Верно, не может, поскольку в ином случае какие-то четверки пересекаются по трем элементам. Остается сделать оценку, учитывая, что каждый элемент содержится не более, чем в 49 множествах! Можно ли это сделать, построив какое-нибудь соответствие между числами и множествами, в которых они содержатся?
Пример. Разобьём все числа на 
пар. Сделаем наши четвёрки всеми возможными парами этих пар. Этот пример подходит, и четвёрок
ровно 
Оценка. Докажем, что каждое число входит не более, чем в 
множеств. Предположим противное, что какое-то число (можем
считать, что 
) принадлежит хотя бы 
множествам. Возьмём одно из них: 
Есть 
других множеств с 
Каждое из них содержит ровно одно из чисел 
По принципу Дирихле, какое-то содержится хотя бы 
раз. Можем
считать, что 
Рассмотрим некоторые четыре множества с 
и 
Друг с другом они больше не пересекаются. Обозначим
эти множества 
Тогда любое другое множество, содержащее 
содержит и
Действительно, иначе оно должно содержать по каждому элементу из пар 
Итак, любое
множество, содержащее 
содержит и 
Но 
таких множеств взять нельзя, так как оставшиеся пары в них не могут
пересекаться.
Итак, каждый элемент присутствует не более, чем в 
множествах. Предположим, множеств всего 
Тогда рассмотрим
всевозможные пары вида “множество — его элемент”. С одной стороны, таких пар 
(у каждого множества 
числа), а с другой — не
более, чем 
(если считать по числам). Таким образом, 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
