solovay is currently certified at Master level.

Name: Robert Solovay
Member since: 2002-08-08 09:07:19

Homepage: http://math.berkeley.edu/~solovay/

Notes:

My one widely used public domain program is a program that computes the checksum of a TeX file. For a description see Checksum

I am a retired Professor of Mathematics whose specialty used to be Mathematical Logic. Lately I have been getting into computer proof assistants especially Mizar.

### Recent blog entries by solovay

31 Dec 2002 (updated 4 Feb 2003 at 23:38 UTC) »

An amusing puzzle

The following is taken from the puzzles column of the Fall, 2002 issue of the magazine Emissary.

A warden meets with 23 prisoners as they arrive. He explains the prison rules, and then allows them to meet with each other, talk, and have a strategy session. The prisoners are then taken to their solitary cells, and no further communication between the prisoners is possible.

In the prison there is a "switch room" containing two electrical switches (not connected to anything), each with two positions. From time to time the warden chooses a prisoner and takes him to the switch room; after observing the switches the prisoner is required to choose one switch and reverse its state. (The prisoners know nothing about the initial state of the switches.) The prisoner is then returned to solitary confinement. The only constraint on the warden's behavior is that each prisoner must be taken to the switch room infinitely often, i.e., any individual prisoner knows that he will sooner or later be taken to the switch room, and after that sooner or later be taken to the switch room again, etc.

At any time, a prisoner can announce to the warden that "By now, all of us have visited the switch room." If this is a true statement, the prisoners are all freed. If it is false, the prisoners are all executed. Clearly, no prisoner will make this statement unless they are absolutely sure that it is true.

Devise a strategy for the prisoners which will guarantee their release.

Source: This problem has apparently been circulating for a while, and appeared on IBM's puzzle web site "Ponder This" at www.research.com/ponder/. Each month, a puzzle is posted on that site, and a solution (together with a list of people who solved it) is posted at the end of the month. The prisoners problem was the July, 2002 challenge.

solovay certified others as follows:

• solovay certified solovay as Journeyer
• solovay certified rlevin as Journeyer
• solovay certified phr as Journeyer

Others have certified solovay as follows:

• solovay certified solovay as Journeyer
• helcio certified solovay as Journeyer
• fxn certified solovay as Journeyer
• Bram certified solovay as Apprentice
• chalst certified solovay as Master
• ploppy certified solovay as Master

[ Certification disabled because you're not logged in. ]