There are lamps and switches in a room. Each lamp is connected to exactly switches. When a switch is pressed, the state of each connected lamp changes from "ON" to "OFF" or vice versa. It is known that by pressing some of the switches, all lamps can be turned on. Prove that this can be achieved by pressing the switches no more than times.
Solution
Obviously, each switch should not be pressed more than once. Let us divide all switches into two groups: Group I - those switches that must be pressed to turn all lamps on, and Group II - all other switches. Since each lamp is connected to an even number of switches, if all switches in Group II are pressed, then all lamps will also turn on. Indeed, we choose lamp "A". If the number of switches connected to "A" is even in Group I, then their number is also even in Group II, and pressing them in either group will not change the state of lamp "A". Similarly, for an odd number.
In total, there are switches in Groups I and II. Therefore, there are no more than switches in at least one of them, which proves the desired answer.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.