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

№ Знакомые и приятели, компоненты связности

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

Решение

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

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

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

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

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

Значит, гарантированно можно при : подходят , , . Числа и не подходят.

💡 Почему так

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

Ответ

✓ dzmen.ru

, ,

Помогло?

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