A $100 \times 100 \times 100$ cube is divided into a million unit cubes and in each small cube there is a light bulb. Three faces $100 \times 100$ of the large cube having a common vertex are painted: one in red, one in blue and the other in green. Call a $\textit{column}$ a set of $100$ cubes forming a block $1 \times 1 \times 100$. Each of the $30 000$ columns have one painted end cell, on which there is a switch. After pressing a switch, the states of all light bulbs of this column are changed. Petya pressed several switches, getting a situation with exactly $k$ lamps on. Prove that Vasya can press several switches so that all lamps are off, but by using no more than $\frac {k} {100}$ switches on the red face.
Problem
Source: ARO Regional stage 2023 9.10
Tags: 3D geometry, combinatorics, Russia
chronondecay
02.12.2023 08:23
We suppose that the switches are on/off switches, which are all off initially. We will show the equivalent claim that any attainable configuration of lights with $k$ lights on can be achieved with at most $k/100$ red switches on. Note that for any $100\times100\times1$ slice of the cube parallel to the blue face, if we toggle each of the 10 red and 10 green switches on that slice then all of the lights in that slice remain in the same state. The same is true if we swap "blue" and "green" in the previous sentence. Consider the (finite) set of all configurations achievable by performing some sequence of such toggles along slices; these must have all lights in the same state, but the switches could be in different states. Take the configuration in this set which has the minimum number $n$ of red switches on; it now suffices to show that $n\leq k/100$. Now consider the $100\times100$ grid of red switches. The minimality condition says that if we toggle all the switches in any subset of rows, then toggle all the switches in any subset of columns, the resulting configuration has at least $n$ red switches on. But this exactly implies that in any slice of the cube parallel to the red face, the number of lights that are on is at least $n$. Since there are 100 slices, the total number of lights that are on (namely $k$) must be at least $100n$, and we are done.