Высшая проба 2023, 10 класс, задача 4
( баллов) Однажды друзей, живущих в разных уголках земного шара, захотели
обменяться друг с другом новостями. Для этого они собираются устроить k видеовстреч, на каждой из которых каждый человек расскажет всем свои новости, а также все новости других людей,
которые он узнал ранее.
Для видеовстреч было предложено дней, но оказалось, что каждый из друзей может присутствовать только в какие-то из них. При каком наименьшем натуральном k можно гарантированно
выбрать k дней для видеовстреч из предложенных так, чтобы каждый узнал новости каждого?
(Между предложенными днями у людей новых новостей не возникает, и никак иначе они друг
с другом не общаются. В каждый из предложенных дней проходит одна видеовстреча, на которой
собираются все, кто может в этот день присутствовать.)
Ответ: дней.
Решение. Приведём пример ситуации, в которой дней не хватит. Пусть у каждого из людей будет своя, не совпадающая с другими людьми, пара дней, в которые он не может участвовать во встрече. Так как количество способов выбрать пару дней из предложенных равно , то для любой пары дней найдётся человек, который не может присутствовать ровно в эту пару дней. Предположим, что мы смогли выбрать какие-то дня так, чтобы каждый узнал все новости. Но тогда существует человек , который не может присутствовать в первые два дня из этих четырёх, а также человек , который не может присутствовать в последние два из этих четырёх дней. Заметим, что тогда не сможет узнать новостей . Противоречие. Теперь поймём, что дней всегда точно хватит. Выберем дней произвольным образом. Докажем, что любые два человека будут вместе присутствовать на какой-то встрече. Действительно, среди этих дней есть не более дней, в которые не может присутствовать первый, а также не более дней, в которые не может присутствовать второй. Значит, найдётся день, в который могут присутствовать оба человека. Таким образом, каждая пара людей сможет обменяться новостями, т. е. каждый узнает новость каждого.
Баллы за оценку и пример суммируются.
+9 б. Оценка — доказано, что 4 дней может не хватить.
В отсутствие этого доказательства оценивается следующее продвижение: # hse-vp-2023-final-g10 / solutions / page 5 ## Best Text.
+1 б. Упомянуто, что всем людям могут соответствовать разные пары пропущенных дней.
+6 б. Пример — доказано, что 5 дней гарантированно хватит. Следующее продвижение не оценивается.
0 б. Приведён только верный ответ.