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

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

В спортивный лагерь приехали на отдых 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

Решение

Построим граф: вершины — школьники, ребро — «знают друг друга». Школьники приятели тогда и только тогда, когда они лежат в одной компоненте связности. Значит, команда из попарных приятелей — это школьники из одной компоненты.

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

Пусть в самой большой компоненте человек. Тогда

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

Больше гарантировать нельзя. Пример: компонент, в каждой все знают друг друга, размеры :

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

💡 Почему так

Приятельство — это принадлежность к одной компоненте связности. Условие про любые школьников означает, что компонент не больше . По принципу Дирихле в одной из них не меньше человек.

Ответ

✓ dzmen.ru

, ,

Помогло?

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