Докажите что к каждому подмножеству из 100 элементов {1,} можно добавить по одному элементу так т что все получившиеся 101-элементные подмножества будут разными

113

306

Посмотреть ответы 2

Ответы на вопрос:

ulyanablem

Математика

4,6(81 оценок)

Лемма (холл). пусть есть k мальчиков и некоторое количество девочек, при этом любая группа из m мальчиков знает не менее, чем m девочек (считаем, что группа знает девочку, если это девочку знает хотя бы один мальчик из группы). тогда каждому мальчику можно найти невесту среди знакомых ему девочек так, чтобы любая девочка была невестой не более, чем одного мальчика. доказательство. пусть еще не все мальчики - женихи, на первом шаге выберем любого мальчика без невесты, а он пригласит всех девочек, с которыми он знаком. на каждом последующем шаге будем добавлять в рассмотрение женихов всех выбранных девочек, а они тоже пригласят всех девочек, с которыми они знакомы. тогда: 1. на каком-то шаге мы выберем девочку без жениха (всякий раз, если в группе есть m мальчиков, будет не менее m девочек. если всё время у всех девочек будут женихи, то равно или поздно в группе будут все k мальчиков и, соответственно, не менее k девочек. ну а поскольку невест не больше k - 1, то хотя бы у одной не будет жениха). 2. найдя девочку без жениха, поженим её с тем, кто её пригласил. оставшуюся без пары девочку поженим с тем, кто пригласил её, и так далее. в конце концов мальчик, изначально не умевший пары, получит невесту, а все мальчики - женихи, останутся женихами. повторяя подобные операции можно найти всем мальчикам пару. а теперь к ; ) пусть 100-элементные подмножества - мальчики, 101-элементные подмножества - девочки. будем говорить, что мальчик знает девочку, если они отличаются на один элемент (например, {1, 2, 100} знает {1, 2, 101}). заметим, что любые m мальчиков суммарно знают не менее m девочек: каждый знает 1916 девочек, а общих знакомых девочек, посчитанных дважды, на каждого не больше 101. тогда по лемме каждому мальчику можно найти пару, т.е. 101-элементное подмножество, которое и требуется по условию.

2001maks44

Математика

4,4(7 оценок)

Х=28•35=980 вот это верно 100%

Реши свою проблему, спроси otvet5GPT

Быстро
Мгновенный ответ на твой вопрос
Точно
Бот обладает знаниями во всех сферах
Бесплатно
Задай вопрос и получи ответ бесплатно

Задай свой вопрос

Популярно: Математика

Есть вопросы?

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.