July 2002
This puzzle has been making the rounds of Hungarian mathematicians'parties.
The warden meets with the 23 prisoners when they arrive. He tells them:
You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
There is in this prison a "switch room" which contains two light switches, labelled "A" and "B", each of which can be in the "on" or "off" position. I am not telling you their present positions. The switches are not connected to any appliance. After today, from time to time, whenever I feel so inclined, I will select one prisoner at random and escort him to the "switch room", and this prisoner will select one of the two switches and reverse its position (e.g. if it was "on", he will turn it "off"); the prisoner will then be led back to his cell. Nobody else will ever enter the "switch room".
Each prisoner will visit the switch room aribtrarily often. That is, for any N it is true that eventually each of you will visit the switch room at least N times.)
At any time, any of you may declare to me: "We have all visited the switch room." If it is true (each of the 23 prisoners has visited the switch room at least once), then you will all be set free. If it is false (someone has not yet visited the switch room), you will all remain here forever, with no chance of parole.
Devise for the prisoners a strategy which will guarantee their release.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
07/01/2002 @ 9:00 AM EST
Solution:
07/31/2002 @ 3:00 PM EST
List Updated:
07/31/2002 @11:45 AM EST
People who answered correctly:
Dominic Baker (7.02.2002 @ 3:00 PM EDT)
Bill Roscoe (7.02.2002 @ 3:00 PM EDT)
Vitaly Stakhovsky (7.02.2002 @ 3:00 PM EDT)
Vishaal Kapoor (7.02.2002 @ 3:00 PM EDT)
Brian Mac Namee (7.02.2002 @ 3:00 PM EDT)
Divyesh Dixit (7.02.2002 @ 3:00 PM EDT)
Steve Clymer (7.02.2002 @ 3:00 PM EDT)
Sameer Udeshi (7.02.2002 @ 3:00 PM EDT)
Bill True (7.02.2002 @ 3:00 PM EDT)
Daniel Clymer (7.02.2002 @ 3:00 PM EDT)
Stephen D. Martin (7.02.2002 @ 3:00 PM EDT)
Graham Clemow (7.02.2002 @ 3:00 PM EDT)
Hubert Pujol (7.02.2002 @ 3:00 PM EDT)
Cheradenine Zakalwe (7.08.2002@ 12:00 AM EDT)
John McGee (7.09.2002 @ 10:00 AM EDT)
Mike Earley (7.09.2002 @ 10:00 AM EDT)
Steve Horvath (7.09.2002 @ 10:00 AM EDT)
Narayanan Unny E (7.09.2002 @ 10:00 AM EDT)
Praveen Jain (7.09.2002 @ 10:00 AM EDT)
Mikel Negugogor (7.09.2002 @ 10:00 AM EDT)
Thomson Roger D (7.09.2002 @ 10:00 AM EDT)
Steven Olafson (7.09.2002 @ 10:00 AM EDT)
Jimmy Hu (7.09.2002 @ 10:00 AM EDT)
CJ Smith (7.09.2002 @ 10:00 AM EDT)
Andy Lowry (7.09.2002 @ 10:00 AM EDT)
Dan Florescu (7.09.2002 @ 10:00 AM EDT)
Alex Wagner (7.09.2002 @ 10:00 AM EDT)
Jayavel Sounderpandian (7.09.2002 @ 10:00 AM EDT)
David Havelin (7.09.2002 @ 10:00 AM EDT)
John V. Sichi (7.09.2002 @ 10:00 AM EDT)
Vivek Kumar Mehra (7.09.2002 @ 10:00 AM EDT)
Sorav Bansal (7.09.2002 @ 10:00 AM EDT)
Brian R. Murphy (7.09.2002 @ 10:00 AM EDT)
Dan Ungureanu (7.09.2002 @ 10:00 AM EDT)
Gunnar Kaestle (7.09.2002 @ 10:00 AM EDT)
Michael P. Moyer (7.09.2002 @ 10:00 AM EDT)
Brett Maune (7.09.2002 @ 10:00 AM EDT)
Nicholas Klezczewski (7.09.2002 @ 10:00 AM EDT)
Thomas Russo (7.09.2002 @ 10:00 AM EDT)
Arun Sivaramakrishnan (7.09.2002 @ 10:30 AM EDT)
David Zimmermann (7.09.2002 @ 10:30 AM EDT)
Peter Bennett (7.09.2002 @ 10:30 AM EDT)
Mitchell A. Kaplan (7.09.2002 @ 10:30 AM EDT)
Chris Wilson (7.09.2002 @ 10:30 AM EDT)
Hassan Masum (7.09.2002 @ 10:30 AM EDT)
Karl D' Souza (7.09.2002 @ 10:30 AM EDT)
Traian Dajma (7.09.2002 @ 10:30 AM EDT)
John G. Fletcher (7.09.2002 @ 10:30 AM EDT)
Gaurav Saxena (7.09.2002 @ 10:30 AM EDT)
Mustafa Yucel (7.09.2002 @ 11:00 AM EDT)
Muriel Lauvergne (7.09.2002 @ 11:00 AM EDT)
John Ritson (7.09.2002 @ 11:00 AM EDT)
Ken Webb (7.09.2002 @ 11:00 AM EDT)
Miroshnichenko Yaroslav (7.09.2002 @ 11:00 AM EDT)
Nikhil sahasrabudhe (7.09.2002 @ 11:00 AM EDT)
Kapil K. Jain (7.09.2002 @ 11:00 AM EDT)
Einat Hardy (7.10.2002 @ 9:15 AM EDT)
Yuvraj Singh Dhillon (7.10.2002 @ 9:15 AM EDT)
J. N. Carrapa (7.10.2002 @ 9:15 AM EDT)
Michael Peeters (7.10.2002 @ 9:15 AM EDT)
Vaibhav Kamthan (7.10.2002 @ 9:30 AM EDT)
Michael Brand (7.10.2002 @ 9:30 AM EDT)
Ivan Priecel (7.11.2002 @ 9:30 AM EDT)
Rok Jamnik (7.11.2002 @ 9:30 AM EDT)
Sriram Sankaranarayanan (7.11.2002 @ 9:30 AM EDT)
Andrew Bayly (7.11.2002 @ 9:30 AM EDT)
Soumitra Pal (7.11.2002 @ 9:30 AM EDT)
Mesha Tonu (7.11.2002 @ 9:30 AM EDT)
Ervan Darnell (7.11.2002 @ 9:30 AM EDT)
Maxim G. Smith (7.11.2002 @ 11:00 AM EDT)
Noha Yousri (7.12.2002 @ 10:00 AM EDT)
Florian Horn (7.12.2002 @ 10:00 AM EDT)
Ilan Algor (7.12.2002 @ 10:00 AM EDT)
Bednarik Jozef (7.12.2002 @ 10:00 AM EDT)
Nikhil Dhoble (7.12.2002 @ 10:00 AM EDT)
Sanjib Basu (7.12.2002 @ 10:00 AM EDT)
Andrew Rose (7.15.2002 @ 9:30 AM EDT)
Kapil Kumar Sharma (7.15.2002 @ 9:30 AM EDT)
Simon Sabik (7.15.2002 @ 9:30 AM EDT)
Graeme McRae (7.15.2002 @ 9:30 AM EDT)
Lakshmi Giridharan (7.15.2002 @ 9:30 AM EDT)
Ming Yu (7.15.2002 @ 9:30 AM EDT)
Tali Avnery (7.16.2002 @ 9:30 AM EDT)
Baruch Doron (7.16.2002 @ 9:30 AM EDT)
Faron Moller (7.16.2002 @ 9:30 AM EDT)
Pascal Brisset (7.16.2002 @ 9:30 AM EDT)
Jozef Drahovsky (7.16.2002 @ 9:30 AM EDT)
Tim Johnston (7.16.2002 @ 9:30 AM EDT)
Melvin Carvalho (7.16.2002 @ 10:45 AM EDT)
Amit Sinha (7.16.2002 @ 2:15 AM EDT)
Hagen Von Eitzen (7.16.2002 @ 10:45 AM EDT)
Rajeswaran M. (7.17.2002 @ 9:40 AM EDT)
George Frankland (7.17.2002 @ 9:40 AM EDT)
Aditya Sharad Utturwar (7.17.2002 @ 9:40 AM EDT)
Itai Yanai (7.31.2002 @ 10:30 AM EDT)
Dan Schwarz (7.31.2002 @ 10:30 AM EDT)
David Keller (7.31.2002 @ 10:30 AM EDT)
Steve Steinfield (7.31.2002 @ 10:30 AM EDT)
Kidd Andy (7.31.2002 @ 10:30 AM EDT)
Amites Sarkar (7.31.2002 @ 10:30 AM EDT)
David Howie (7.31.2002 @ 10:30 AM EDT)
Andy Freestone (7.31.2002 @ 10:30 AM EDT)
Lyle Ramshaw (7.31.2002 @ 10:30 AM EDT)
Jim Saxe (7.31.2002 @ 10:30 AM EDT)
Yunhong Zhou (7.31.2002 @ 10:30 AM EDT)
Philipp Rumpf (7.31.2002 @ 10:30 AM EDT)
Peter Moller (7.31.2002 @ 10:30 AM EDT)
Christian Karbacher (7.31.2002 @ 10:30 AM EDT)
Thorsten Boecker (7.31.2002 @ 10:30 AM EDT)
Kishore Gangwani (7.31.2002 @ 10:30 AM EDT)
Jim Allers (7.31.2002 @ 10:30 AM EDT)
Richard Bennett (7.31.2002 @ 10:30 AM EDT)
Dan Milstein (7.31.2002 @ 10:30 AM EDT)
Mark Pilloff (7.31.2002 @ 10:30 AM EDT)
Ariel Ish-Shalom (7.31.2002 @ 10:30 AM EDT)
Dave Hebden (7.31.2002 @ 10:30 AM EDT)
Michael Mendelsohn (7.31.2002 @ 10:30 AM EDT)
Eric Porter (7.31.2002 @ 10:30 AM EDT)
Matthew Russo (7.31.2002 @ 10:30 AM EDT)
Phil Carmody (7.31.2002 @ 10:30 AM EDT)
Andrew Reed (7.31.2002 @ 10:30 AM EDT)
Nicolas Landes (7.31.2002 @ 10:30 AM EDT)
Oleg Trott (7.31.2002 @ 10:30 AM EDT)
Nis Jorgensen (7.31.2002 @ 10:30 AM EDT)
Nagendra (7.31.2002 @ 10:30 AM EDT)
Michael Malak (7.31.2002 @ 10:30 AM EDT)
Avery Wang (7.31.2002 @ 10:30 AM EDT)
Brent Townshend (7.31.2002 @ 10:30 AM EDT)
Gyora Benedek (7.31.2002 @ 10:30 AM EDT)
Yoav Raz (7.31.2002 @ 10:30 AM EDT)
Tom (7.31.2002 @ 10:30 AM EDT)
David Lightning (7.31.2002 @ 10:30 AM EDT)
Peter Huggins (7.31.2002 @ 10:30 AM EDT)
Forest Deal (7.31.2002 @ 10:30 AM EDT)
Kris Van Bael (7.31.2002 @ 10:30 AM EDT)
Frank Vernaillen (7.31.2002 @ 10:30 AM EDT)
Sebastjan Plavec (7.31.2002 @ 11:45 AM EDT)
Lukasz Bolikowski (7.31.2002 @ 11:45 AM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.