Республиканская олимпиада по математике, 2020 год, 9 класс

В комнате есть $n$ ламп и $k$ выключателей. В начале каждая лампа может быть либо включенной, либо выключенной. Каждая лампа соединена проводом ровно с 2020 выключателями. Нажатие на выключатель изменяет на противоположное состояние каждой лампы, к которой он подключен проводом. Известно, что можно так понажимать на выключатели, что все лампы станут включенными. Докажите, что можно добиться того же результата не более, чем за $\left \lfloor \dfrac{k}{2} \right \rfloor$ нажатий на выключатели. $\left \lfloor x \right \rfloor$ обозначает наибольшее целое число, не превосходящее $x$. ( Зиманов Т. )

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

Комментарии от администратора Комментарии от администратора №1.     Заметим, что бессмысленно нажимать на один и тот же выключатель более одного раза. Пусть $A$ — какое-нибудь множество выключателей, нажав на которые по одному разу можно сделать все лампы включенными, а $B$ — множество всех остальных выключателей. Так как каждая лампа соединена проводом с четным количеством выключателей, то если вместо выключателей из $A$ мы нажмем на выключатели из $B$, все равно все лампы окажутся включены. Так как $|A| + |B| = k$, то в хотя бы одном из этих множеств не больше $\left \lfloor \dfrac{k}{2} \right \rfloor$ выключателей. Следовательно, мы можем нажать на не более $\left \lfloor \dfrac{k}{2} \right \rfloor$ выключателей так, чтобы все лампы оказались включены, что и требовалось доказать.