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

Бөлмеде $n$ шам және $k$ сөндіргіш бар. Басында әр шам немесе жанып, немесе сөндіріліп тұр. Әр шам сым арқылы дәл 2020 сөндіргішпен қосылған. Сөндіргішті басқан кезде, сол сөндіргішпен қосылған шам өз қалпын қарама-қарсы қалыпқа өзгертеді. Сөндіргіштерді қандай-да бір ретпен баса отырып, барлық шамдарды жанған қалыпқа келтіруге болатыны белгілі. Осы нәтижеге сөндіргіштерді $[k/2]$ санынан аспайтын басу арқылы жетуге болатынын дәлелдеңіз. Бұл жерде $[x]$ саны — нақты $x$ санының бүтін бөлігі, яғни $x$-тен аспайтын ең үлкен бүтін сан. ( Зиманов Т. )

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

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