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

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

Задача 1#96504

В школе учится 10001  школьник. Они входят в банды, при этом один школьник может входить в несколько банд. Банды входят в сообщества, при этом одна банда может входить в несколько сообществ. Пусть всего k  сообществ, при этом выполнены следующие условия.

∙

Каждая пара школьников входит ровно в одну банду.

∙

Для каждого школьника P  и каждого сообщества S  существует ровно одна банда этого сообщества S,  в которую входит школьник P.

∙

В каждой банде нечетное количество участников. Более того, если в банде 2n+ 1  человек, то эта банда входит ровно в n  сообществ.

Найдите все возможные значения k.

Показать ответ и решение

Обозначим за P  одного из наших школьников. Заметим, что любое сообщество S  должно содержать всех школьников по второму условию. Поэтому банды из которых состоит сообщество S  не пересекаются, но в объедении дают всех школьников. Рассмотрим все банды, которые содержат школьника P.  Обозначим эти банды за B1,B2...Bk.  Заметим, что по первому условию эти банды попарно не могут пересекаться по какому-то школьнику, кроме P.  Следовательно, если обозначить за T1,T2,...Tk  количество школьников в бандах B1,B2,...Bk  соответственно, то верно следующее равенство: T1+ T2+ ...Tk = 10000+ k  . Так как в объединении банд B1,B2,...Bk  встречается каждый школьник, кроме P,  по одному разу, а школьник p1  встречается k  раз. Теперь воспользуемся третьим условием и заменим каждое Ti  на     ′
2 ⋅Ti + 1.  Следовательно, верно равенство:  ′   ′      ′
T1+ T2+...+Tk = 5000.  Заметим, что каждая из банд Bi  по третьему условию должна содержаться ровно в   ′
Ti  сообществах, но при этом банды Bi  и Bj  при i⁄= j  не могут лежать в одном сообществе, и в каждом сообществе должна быть хоть одна банда Bi.  Поэтому сообществ должно быть ровно 5000.  Для построения примера достаточно взять одну банду, которая содержит всех школьников и сделать 5000  сообществ, которые состоят только из этой банды.

Ответ:

 5000

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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