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

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

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

Решение

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

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

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

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

💡 Почему так

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

Ответ

✓ dzmen.ru

, ,

Помогло?

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