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

Компоненты связности, принцип Дирихле

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

Решение

Варианты ответа на фото не видны, поэтому найдём все подходящие .

Разобьём школьников на группы: в одной группе все приятели друг другу, а школьники из разных групп приятелями не являются (это цепочки знакомств). Команда, в которой все попарно приятели, — это часть одной группы.

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

Если групп не больше , а школьников , то в самой большой группе не менее человек:

Значит, команду из школьников (и любого меньшего числа) сформировать можно всегда.

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

💡 Почему так

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

Ответ

✓ dzmen.ru

Гарантированно можно для всех (то есть ); для — нельзя.

Помогло?

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