2005 IMO Shortlist Problems/C1
Problem
(Australia) A house has an even number of lamps distributed among its rooms in such a way that there are at least three lamps in every room. Each lamp shares a switch with exactly one other lamp, not necessarily from the same room. Each change in the switch shared by two lamps changes their states simultaneously. Prove that for each initial state of the lamps there exists a sequence of changes in some of the switches at the end of which each room contains lamps which are on as well as lamps which are off.
This problem was not used on the contest, as it appeared in the 1990 Australian Mathematical Olympiad.
The problem was submitted to the Problem Selection Committee in the following form:
A school has an even number of students, each of whom attends exactly one of its (finitely many) classes. Each class has at least three students, and each student has exactly one "best friend" in the same school such that, whenever 
is 
's "best friend", then is 's "best friend". Furthermore, each student prefers apple juice over orange juice or orange juice over apple juice, but students change their preferences from time to time. "Best friends", however, will change their preferences (whic may or may not be the same) always together, at the same moment.
Whatever preference each student may initially have, prove that there is always a sequence of changes of preferences which will lead to a situation in which no class will have students all of whom have the same preference.
Solution
It is sufficient to prove that we can always reduce the number of monochromatic rooms by one after finitely many steps.
Suppose there is a monochromatic room. We start in that room, and perform a sequence of moves according to the following rules:
- If we are in a monochromatic room, we toggle a switch connected to a light in our room which we have not toggled before. We then move to the room containing the other light which the switch changed.
- If we are in a dichromatic room or a room in which we have been before, we stop.
Eventually, we must either reach a dichromatic room, in which case we have reduced the number of monochromatic rooms by one, or we reach a room that we had been in before. But when we entered it for the first time, it was monochromatic. Since it was monochromatic, we have toggled two distinct lights in that room (one leaving and one coming back), and since there is at least one additional light in the room that has not been toggled since we were in it last, the room is now dichromatic. Thus we eventually encounter a dichromatic room, decreasing the number of monochromatic rooms by one, so we can eventually make all rooms dichromatic. Q.E.D.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
