| Home | Student Seminar Series | Math Club Officers | Undergraduate Math Dinners | Mathematics | Past Events |
One hundred prisoners are on a ship heading toward a prison. The following morning, and each morning after, one prisoner will be selected at random and taken to a room with a lamp. They may turn the lamp on or off, or leave it as they found it. If at any point a prisoner says "All 100 of us have been in this room" and is correct, all prisoners will be set free. If they are wrong, then the prisoners are doomed forever. The prisoners cannot communicate once they arrive at the prison, but can come up with a strategy while on the ship. What should their strategy be?
Note that the lamp could be either on or off on the first day
For a harder problem: Is there a winning strategy if the first prisoner is taken in at some indeterminate time - that is, if no one knows if they are the first to be taken to the room?
Answer The person who goes in on the first day (whoever it ends up being) will be called the lightman. On the first day, the lightman makes sure the lamp is in the off state. Then if any prisoner goes into the room with the lamp off, he will turn it on is he hasn't before. If the lamp is already on, he will do nothing. Then the next time the lightman is in the room he will turn the light off and wait until he arrives in the room again with a lit lamp. Once he turns the lamp off 99-100 times, (meaning everyone else has turned the lamp on once) he can claim his freedom. We'll leave the harder problem for you!
Week of September 24
A scientist has created a type of egg which can withstand being dropped from extreme heights. There are two problems: First he only has two eggs, and second he doesn't know the height they can withstand. He does however, know that the height is some number of stories between 1 and 100. For example he knows that there is some floor of his 100 story laboratory from which he can safely drop the eggs, but doing so from any higher floor would cause them to break. What is the "best" maximum number of floors that he must test so that he can be sure of the eggs' strength? Assume both eggs have the same strength. HINT: Notice that once the first egg breaks you have to go back to the last known "safe spot" and then go up one floor at a time to have any hope of getting the right floor.