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

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

Задача 1#75129

Однажды 45  друзей, живущих в разных уголках земного шара, захотели обменяться друг с другом новостями. Для этого они собираются устроить k  видеовстреч, на каждой из которых каждый человек расскажет всем свои новости, а также все новости других людей, которые он узнал ранее.

Для видеовстреч было предложено 10  дней, но оказалось, что каждый из друзей может присутствовать только в какие-то 8  из них. При каком наименьшем натуральном k  можно гарантированно выбрать k  дней для видеовстреч из предложенных 10  так, чтобы каждый узнал новости каждого?

(Между предложенными днями у людей новых новостей не возникает, и никак иначе они друг с другом не общаются. В каждый из предложенных дней проходит одна видеовстреча, на которой собираются все, кто может в этот день присутствовать.)

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

Оценка. Приведём пример ситуации, в которой 4 дней не хватит. Пусть у каждого из 45 людей будет своя, не совпадающая с другими людьми, пара дней, в которые он не может участвовать во встрече. Так как количество способов выбрать пару дней из 10 предложенных равно  2
C10 =45  , то для любой пары дней найдётся человек, который не может присутствовать ровно в эту пару дней. Предположим, что мы смогли выбрать какие-то 4 дня так, чтобы каждый узнал все новости. Но тогда существует человек A  , который не может присутствовать в первые два дня из этих четырёх, а также человек B  , который не может присутствовать в последние два из этих четырёх дней. Заметим, что тогда B  не сможет узнать новостей A  . Противоречие.

Пример. Теперь поймём, что 5 дней всегда точно хватит. Выберем 5 дней произвольным образом. Докажем, что любые два человека будут вместе присутствовать на какой-то встрече. Действительно, среди этих 5 дней есть не более 2 дней, в которые не может присутствовать первый, а также не более 2 дней, в которые не может присутствовать второй. Значит, найдётся день, в который могут присутствовать оба человека. Таким образом, каждая пара людей сможет обменяться новостями, то есть каждый узнает новость каждого.

Ответ:

При k= 5

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

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

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

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

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

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

Бесплатное обучение
в Школково

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

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

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

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

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

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

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

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