Олимпиада начальной школы 2x2, 6 класс, 2011 год, 2 тур
дата проведения: 22 мая 2011
Задача 8.
В школе работает несколько секций, всего больше 15 секций, в каждой не более 15 мест. Известно, что для любых 16 секций найдётся ученик, который записался во все эти секции. Докажите, что тогда есть ученик, который записался во все секции.
Ответ на Задачу 8.
Решение:
Рассмотрим некоторую секцию 𝐴. Если утверждение задачи неверно, то для любого ученика из этой секции найдётся секция, в которой он не занимается. Тогда, все эти секции вместе с 𝐴 образуют набор из не более, чем 16 секций, не имеющих общих учеников. Дополнив их любыми секциями до 16, получим набор из 16 секций, противоречащий условию задачи.