Теория графовСтепени вершинСвязность

Знакомства

Стартовый архив Mathforces · задача R

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

Докажите, что среди любых шести человек найдутся двое с одинаковым числом знакомых внутри этой шестёрки. Знакомство взаимно.

Официальное решениеОткрыть

Степени вершин лежат среди 0,1,2,3,4,5. Однако степени 0 и 5 не могут встретиться одновременно: человек без знакомых не знаком с человеком, знакомым со всеми. Значит реально возможны не более пяти значений степеней для шести людей. По принципу Дирихле две степени совпадают.

Отправить решение

Наберите не меньше 90 баллов, чтобы задача попала в решённые. Попытки сохраняются.

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

Обсуждение

Войдите, чтобы оставить комментарий.

Пока нет комментариев. Начните обсуждение.