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

№ Наибольшая клика в графе знакомств (цепи и антицепи)

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

Решение

Если один школьник по цепочке знакомств «достаёт» другого, они приятели. Это отношение транзитивно: если достаёт , а достаёт , то достаёт .

Команда, в которой все попарно приятели, — это «цепь». Группа из школьников, среди которых нет ни одной пары приятелей, — это «антицепь» из элементов.

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

Тогда в одной из цепей не менее

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

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

💡 Почему так

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

Ответ

✓ dzmen.ru

, ,

Помогло?

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