in Uncategorized

Prisoner Problems

Professor Char gave us an interesting problem in our Concurrent Programming class, that is more of a riddle that a programming problem. I am going to look up the answer in a few days, until then, help me figure it out.

There are 12 students taking an exam. Each has his own examination room. Each student is individually led to a common room, so that while 1 student is out of his room and in the common room, each of the other 11 students is still in his own examination room.

The common room contains 2 switches, that can be set to an on or off position.

The only way for the students to pass is by going into the room and stating that all other students have been in the room. If the statement is true, then all students will pass. If the statement is false, all the students will fail.

The only way for students to communicate state information is using the switches. Meaning, students can only use their own memory and the switches to decide if all of the other students have been in the room.

Students can be taken to the room infinitely many times, and in no particular order.

The important thing to note, is that the students know abotu the exam ahead of time, and can coordinate some sort of plan to pass.

What kind of plan do they use to pass