Using your Head is Permitted

March 2011 riddle

The following riddled was related to me by Omer Angel, who heard it from Avi Berman. It continues the tale of MegaCorp, the company introduced in last month's riddle.

Each employee of MegaCorp has a separate office in the MegaCorp office building. Each office is equipped with one overhead light and one toggle switch to turn the light on and off.

Every day, the employees turn on all lights when they come to work. Each evening they turn off all lights when they go home.

One day, the employees arrive to discover that someone has played a rather elaborate hoax on them. Though all looks fine when they come in (all lights are off), every time an employee flicks the switch in her office, this not only toggles the light in her office, but also the lights in the offices of all of her friends.

The question: does there necessarily exist an arrangement of the switches that will turn all lights simultaneously on (so that work can begin)? Prove your answer.

List of solvers:

Daniel Bitin (1 March 10:20)
Yongxing Deng (2 March 01:50)
Joseph DeVincentis (2 March 03:17)
Sumit Sanghai and Dharmadeep Muppalla (2 March 03:39)
Lin Jin (2 March 14:39)
Christian Blatter (3 March 20:07)
Wolfgang Kais (4 March 00:50)
Oded Margalit (4 March 07:48)
Gaoyuan Chen (5 March 02:44)
Jan Fricke (5 March 04:45)
Liu Bobby (19 March 05:33)
Hongcheng Zhu (30 March 04:44)
Bojan Bašić (31 March 15:03)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page