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