After studying for a math exam some months ago, I fell in an uneasy sleep and had the oddest dream.
I dreamt I was part of a company of soldiers captured in enemy territory, imprisoned for weeks.
Finally, one day, we all were brought before the prison warden.
He offered us a chance to earn back our freedom – but at the price of having to pass a deadly test.
He placed a sheet of paper displaying the rules of the test on the table we sat around and gave us
six hours to come up with a solution to save our lives.
The rules of this test were given as follows:
Following this discussion, every prisoner will be led to his own seperate cell.
They will be unable to communicate with each other until the test has been passed.
From then on, every day one prisoner will be picked at random and led into a separate cell
containing nothing but a single, massive two-position switch labeled with ON and OFF whose
initial state is unknown to all the prisoners.
The prisoner may flip this switch to his liking.
Before leaving the room, a prison guard will ask this prisoner the question:
“Has every prisoner been inside the switch room yet?”
Should the prisoner truthfully answer the question with yes, then the test has been passed successfully
and all prisoners will be given freedom.
Should the prisoner truthfully answer the question with no, then they will be led back to their cell
and the test will continue.
Should the prisoner answer untruthfully, the prisoners will have failed the test and will face execution.
Naturally, the table errupted in a heated debate about which strategy could save our lives.
How could we possible brave this seemingly impossible challenge with just a single bit of information
at our hands? Surely we were doomed. Or were we?
Hours passed, but at very last our commander came up with an ingenious method that would guarantee our survival,
without a shadow of doubt the most brilliant idea I had ever heard in my entire life.
I suddenly awoke, dazed, scrambled to write down the seemingly impossible solution, but alas! – I had already forgotten
most of it. Today I find myself questioning whether this dream was a streak of genius or madness.
My question is: Does this puzzle really have a definitive solution that ensures the soldier’s survival?
Or is this merely the stuff of dreams?
I have provided my own attempts at an solution below for inspiration.
Another tip: This problem is basically a harder version of the problem known as ‘100 prisoners and a lightbulb’, the major
difference being that the question will need to be answered correctly every day and not only when a prisoner wishes to give an answer.
This reduces the timeframe of the problem signifcantly and the solution will need to be found much faster.
Both problems are related to the Coupon collector’s problem. Perhaps understanding these problems can provide some insight?
