7-я олимпиада им. Шалтая Смагулова, 6 класс, 3 тур

В классе 30 учеников, один из них — Вася. Каждый из Васиных одноклассников имеет ровно 5 общих друзей с Васей. Докажите, что в классе есть ученик с нечетным числом друзей.

Комментарий/решение

Всего учеников 30 - значит учеников которые не Вася -29. И каждый имеет 5 друзей с Васей: 29*5-30=115. 115 можно получить из суммы чисел тогда и только тогда, когда хотя бы одно слогаемое нечетное.Докажем: Пусть не так, тогда все слагаемы четные но тогда и сумма четная, а 115- число нечетное => противоречие. Доказано

Разобьем класс на 3 группы, друзья Васи, Вася, не друзья Васи.

Предположим противное и скажем что у всех четное количество друзей, значит группа друзей Васи состоит из четного количества людей, а не друзей Васи нечетное. Рассмотрим количество дружб между друзьями и не друзьями Васи.

Друзья -> не друзья. Заметим что каждый друг Васи дружит с четным количеством не друзей Васи, отсюда следует что количество дружб четное

Не друзья -> друзья. Каждый недруг дружит с 5 друзьями, отсюда тк их общее количество нечетное, значит и количество дружб тоже. Противоречие нечетное ≠ четное