Олимпиада имени Леонарда Эйлера 2018-2019 учебный год, II тур регионального этапа

Имеется 70 переключателей и 15 ламп. Каждая лампа соединена с 35 переключателями. Никакие два переключателя не соединены с одним и тем же набором ламп. Нажатие на переключатель меняет состояние всех ламп, с которыми он соединён (включённые выключает и наоборот). Изначально все лампы выключены. Докажите, что можно нажать на какие-то 19 переключателей таким образом, чтобы включилось не менее восьми ламп. ( С. Берлов )

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

Комментарии от администратора Комментарии от администратора №1.     Рассмотрим всевозможные наборы из 19 переключателей. Рассмотрим также любую лампочку. Разобьём все переключатели на 35 пар таким образом, чтобы в каждой паре ровно один переключатель был соединён с выбранной лампочкой. Заметим, что тогда все наборы по 19 переключателей тоже разбились на пары, получающиеся заменой всех переключателей на парные. Так как число 19 нечетно, в каждой паре наборов ровно один включает выбранную лампочку.
   Составим таблицу, в которой строки соответствуют лампочкам, а столбцы — наборам из 19 переключателей, и отметим в каждой строке единицами наборы, включающие соответствующую лампочку. Из доказанного выше следует, что единицы в таблице занимают ровно половину клеточек. Значит, найдется столбец, в котором единицы занимают не меньше половины клеточек, то есть найдётся набор, который включает не менее половины всех лампочек. Следовательно, какой-то набор из 19 переключателей зажжёт не менее 8 лампочек.