Задача
COM-B2-M04-P012 Игроки, знакомые со всеми
В компании из \(n\ge 3\) человек знакомство взаимно. Известно, что хотя бы один человек знаком не со всеми. Какое наибольшее число людей всё же может быть знакомо со всеми остальными? Докажите ответ.
Если бы таких людей было \(n-1\), что происходило бы с оставшимся человеком?
Ответ: \(n-2\). Сначала покажем, что \(n-1\) невозможно. Если \(n-1\) человек знакомы со всеми, то оставшийся человек знаком с каждым из этих \(n-1\) людей. Значит, он тоже знаком со всеми, что противоречит условию.
Покажем достижимость. Пусть два человека \(A\) и \(B\) не знакомы друг с другом, а все остальные знакомы со всеми. Тогда ровно \(n-2\) человек знакомы со всеми остальными, а \(A\) и \(B\) не знакомы со всеми. Условие выполнено.
Идея вдохновлена типовым олимпиадным вопросом о максимальном числе универсальных вершин, но формулировка и решение подготовлены как оригинальная тренировочная задача.