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

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

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

Следовательно, ни один из предложенных размеров команды не гарантирован.

Ответ: ни один из вариантов.