Dartblog

With hope to reprise the great popularity of Dartblog’s first mathematical puzzle, (my long-winded solution here), I am retroactively introducing the semi-regular column Math@Dartblog. I am calling the first puzzle and its solution Installments 1 and 2, respectively, and I’ll call this great article on magnitude estimation Installment 2.5. Welcome to Installment 3, and another puzzle.

You are one of 100 prisoners each held in solitary confinement by a sadistically curious and curiously sadistic jailer. Today, the jailer escorts all 100 of you to the prison conference room (do prisons have conference rooms?) and explains his sadistic game. (“I offer a route to freedom!” he begins, “… or death.”) At noon each day starting tomorrow, the jailer will choose one prisoner uniformly at random to escort to his lamp chamber. This chamber is a small, silent, emotionless room containing nothing but an old, rickety lamp in the center. The prisoner so escorted may take one of two actions in the lamp chamber.

1. He may turn on the lamp if it is off or turn off the lamp if it is on, or

2. He may make the Declaration of Freedom or Death, announcing “All 100 prisoners have visited the lamp chamber.”

Alternatively, he may chose to do neither, and return to his cell. If a prisoner toggles the state of the lamp, he returns to his cell immediately thereafter, and the game continues. If he makes the Declaration of Freedom or Death, all the prisoners immediately receive, you guessed it, freedom or death. The rule is simple: They receive freedom if the declaration is correct—if all 100 prisoners have indeed visited the lamp chamber. They receive death otherwise.

On any given day, no prisoner knows which prisoner has been escorted to the lamp chamber except that prisoner himself. No communication of any kind is allowed between the prisoners once the game has begun—except, of course, what can be accomplished through the lamp. The jailer informs you that on the morning of the first day, the lamp will be off.

“You have one hour to discuss your strategy,” intones the jailer. “Will you find freedom… or death?”

Now the math.

Assuming the game continues for eternity, no prisoner nor the jailer dies of natural causes, and the rickety lamp never burns out, it is trivial to see that the prisoners can save themselves with probability arbitrarily close to 1. To do this, they could agree to completely ignore the lamp and simply wait a huge number of days, say one million days, before making the declaration. The prisoner chosen on the one millionth day would make the declaration. The probability that not all 100 prisoners have been chosen after one million days is infinitesimal.

Is it possible for the prisoners to save themselves with certainty? (Hint: yes, otherwise there wouldn’t be much to this problem.) How?

I have found one strategy that saves the prisoners with certainty. I am sure there are others, and I am sure they vary widely in their efficiency. I am reasonably happy with mine; if the prisoners are young at the start of the game, they should be out in their lifetimes.

That being said, it is clear that due to the randomness of the game, there exists no strategy for which we can put an absolute upper bound on the number of days it will take to free the prisoners. For it is possible, despite being “impossible,” that a single prisoner could be chosen one million times in a row at the very beginning of the game, say. We must therefore compare the efficiency of different strategies based on their expected runtimes.

Is it possible to save the prisoners with certainty if the initial state of the lamp is unknown to the prisoners?

Answers soon.