Задача 5.
В аудитории А сидит 20 участников олимпиады, причём среди любых 10 из них есть 3 одноклассника. Верно ли, что в аудитории А обязательно есть 5 человек из одного класса?
Ответ на Задачу 5.
Ответ: да, верно.
Решение:
Предположим противное. Пусть в этой аудитории нет пяти человек из одного класса. Тогда максимальное количество одноклассников – 4. Разобьём 20 участников олимпиады на группы одноклассников. Если в группе одноклассников ровно один человек, назовём эту группу малой. Если в группе больше одного человека, назовём её большой.
Теперь разделим 20 участников олимпиады на 2 команды. В первую команду возьмём по одному человеку из каждой малой группы и по два человека из каждой большой. После этого в каждой большой группе останется не более двух человек. Объединим их всех во вторую команду. Заметим, что в каждой команде нет трёх одноклассников, однако мы разбили 20 человек на 2 команды и следовательно в одной из команд не менее 10 человек. Возьмём эту команду и, если там больше 10 человек, то выберем любых 10, и среди этих десяти не будет трёх одноклассников. Противоречие.
