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

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

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