В спортивный лагерь приехали на… (вероятность и статистика)

Приятели как компоненты связности

В спортивный лагерь приехали на отдых 134 школьника. Школьники $A$ и $B$ считаются приятелями, если они лично знают друг друга либо если найдутся такие школьники $C_{1}, C_{2}, \dots, C_{k}$ , что $A$ знает $C_{1}$ , $C_{1}$ знает $C_{2}$ , $\dots$ , $C_{k}$ знает $B$ . Известно, что в лагере среди любых 8 школьников имеется пара приятелей. Требуется сформировать команду из $N$ школьников так, чтобы любые двое в ней оказались приятелями. Для каких $N$ это гарантированно можно сделать? Выберите все подходящие варианты: 16; 19; 20; 23; 25; 26; 27

Решение

Считаем знакомство взаимным. Тогда школьников можно разбить на группы: в одной группе все приятели друг другу, а школьники из разных групп приятелями не являются (в графе знакомств это компоненты связности).

Число групп. Если бы групп было хотя бы , то, взяв по одному школьнику из восьми разных групп, мы получили бы школьников без пары приятелей. Это противоречит условию. Значит, групп не больше .

Самая большая группа. Если в каждой группе не больше человек, то всего школьников не больше

Значит, есть группа не меньше чем из школьников. Все они приятели друг другу, поэтому команду из человек составить можно. Команды из и человек получаются из неё выбором части школьников.

Почему больше нельзя гарантировать. Пример: групп размерами , , , , , , (сумма ), внутри группы все знакомы, между группами никто не знаком. Среди любых школьников двое окажутся в одной группе, то есть условие выполнено. Но самая большая группа состоит из человек, поэтому команду из , , или человек составить нельзя.

Гарантированно можно при .

💡 Почему так

Отношение «приятели» разбивает школьников на группы (компоненты связности). По условию их не больше , поэтому по принципу Дирихле в одной из групп не меньше человек.

Ответ

✓ dzmen.ru

, ,

Помогло?

В спортивный лагерь приехали на отдых 134 школьника. Школьники A и B…