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

Графы: компоненты связности

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

Решение

Школьники — вершины графа, знакомство — рёбра. Приятели — это вершины, связанные путём, то есть лежащие в одной компоненте связности. Команда, в которой все попарно приятели, — это набор людей из одной компоненты.

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

поэтому если бы в каждой компоненте было не больше человек, всего было бы не больше . Значит, есть компонента не менее чем из человек. Из неё можно выбрать команду из любого числа N от до человек.
N = гарантировать нельзя. Пример: компонент по человек и одна компонента из человек (). В каждой компоненте все знакомы (или связаны цепочкой), среди любых человек двое попадут в одну компоненту (принцип Дирихле, компонент ), то есть будут приятелями. А команды из человека не получится: больше человек в одной компоненте нет.

💡 Почему так

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

Ответ

✓ dzmen.ru

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

Помогло?

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