ВсОШ 2023, региональный этап, 9 класс, задача 10
( баллов) Куб разбит на миллион единичных кубиков; в каждом кубике расположена лампочка. Три грани большого куба, имеющие общую вершину, окрашены: одна красным, другая синим, а третья зелёным. Назовём столбцом набор из кубиков, образующих блок . У каждого из столбцов есть одна окрашенная торцевая клетка; в этой клетке стоит переключатель — нажатие на этот переключатель меняет состояние всех лампочек в столбце (выключенная лампочка включается, а включенная выключается). Изначально все лампочки были выключены. Петя нажал на несколько переключателей, получив ситуацию, в которой ровно лампочек горят. Докажите, что после этого Вася может нажать на несколько переключателей так, чтобы ни одна лампочка не горела, использовав не более переключателей с красной грани.
(С. Кудря, И. Богданов)
Ответ
Решение. Ясно, что результат нажатия нескольких переключателей не зависит от того, в каком порядке эти нажатия были произведены — количество переключений каждой лампочки не зависит от этого порядка. В частности, можно считать, что Петя использовал каждый переключатель не более одного раза.
Весь куб разбивается на слоёв, параллельных красной грани. Каждый переключатель на некрасной грани переключает лампочки в одном слое, а каждый переключатель на красной грани — по лампочке во всех слоях.
После действий Пети найдётся слой, в котором включено лампочек — назовём один такой слой главным. Пусть — набор из переключателей на красной грани, связанных со включёнными лампочками в главном слое. Мы докажем, что Вася может погасить все лампочки, использовав с красной грани ровно эти переключатели.
Запустим несколько другой процесс, начиная с того же исходного положения. Пусть — набор переключателей с красной грани, использованных Петей, а — набор использованных им переключателей с некрасных граней, связанных с главным слоем. Пусть Петя применит и , а затем Вася применит . После действий Пети в главном слое будут гореть те же лампочек, что и раньше, а значит, после действий Васи все лампочки в главном слое будут погашены. Если теперь Вася применит в каждом из остальных слоёв наборы переключателей с некрасных граней, аналогичные , то все лампочки будут погашены.
Пусть теперь Петя применит все остальные переключатели (с некрасных граней!), которые он применял исходно, а Вася применит их ещё по разу. Все лампочки по-прежнему будут погашены. При этом в новом процессе Петя применил ровно те же переключатели, что и в исходном, а Вася использовал лишь переключатели набора с красной грани (и какие-то — с остальных граней). Значит, если в исходном процессе Вася совершит те же действия, которые он сделал в новом, он добьётся требуемого.