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

№ Графы: компоненты связности, принцип Дирихле

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

Решение

На фото видны варианты , , , . Возможно, список продолжается ниже и не виден; решаем по видимым.

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

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

Какая-то группа достаточно большая. Если групп не больше , то в самой большой группе не меньше

школьников, потому что .

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

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

Подходят .

💡 Почему так

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

Ответ

✓ dzmen.ru

, ,

Помогло?

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