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

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

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

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