Open Contests

Question

There is a finite number of lamps in an electrical scheme. Some pairs of lamps are directly connected by a wire. Every lamp is lit either red or blue. With one switch all lamps that have a direct connection with a lamp of the other colour change their colour (from red to blue or vice versa). Prove that after some number of switches all lamps have the same colour as two switches before that.

Accepted Answer

If some connected lamps are lit in different colours they both change colour upon switching, hence they are also lit differently after the switch. The same holds on each following switch. Hence no pair of connected lamps lit in different colours can disappear but more of such pairs can appear. As there are only finitely many lamps, the number of connected pairs of differently lit lamps can not grow infinitely. Hence this number stops changing after some number of switches. This means at that point a lamp either changes colour on each switch or never changes colour. Hence the colours of all lamps are the same after two consecutive switches.