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

Вероятность и статистика9 классРешено по тексту 15 октября 2026 в 05:54

Приятели и компоненты связности

В спортивный лагерь приехали на отдых 127 школьников. Школьники A и B считаются приятелями, если они лично знают друг друга либо если найдутся такие школьники C₁, C₂, …, Cₖ, что A знает C₁, C₁ знает C₂, …, Cₖ знает B. Известно, что в лагере среди любых 8 школьников имеется пара приятелей. Требуется сформировать команду из N школьников так, чтобы любые двое в ней оказались приятелями. Для каких N это гарантированно можно сделать? Выберите все подходящие варианты: 17, 18, 19, 21, 22, 23, 24

Решение

Представим школьников вершинами графа, знакомства — рёбрами. Два школьника приятели, если они лежат в одной компоненте связности. Значит, команда, в которой все приятели, — это набор школьников из одной компоненты.

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

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

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

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

Итак, гарантированно можно при .

💡 Почему так

Отношение «быть приятелями» делит школьников на компоненты связности; команда должна целиком лежать в одной компоненте. Из условия компонент не больше , поэтому самая большая содержит не менее человек.

Ответ

✓ dzmen.ru

, ,

Помогло?

Есть ещё задание?Сфоткай, и ДЗмэн решит за пару секунд.

Решить по фото

Решить своё по фото