Light switch problem
November 30th, 2015 at 7:00:07 AM
permalink
The king selects 16 prisoners from death row. He explains to them collectively that he has placed a switch in an empty cell that can be set to either an up or down position. The switch is not connected to anything. The initial state could be either way. He then explains that he will separate the prisoners into separate cells. At least once a day the king will select a prisoner at random and lead him to the switch cell. At any time if any prisoner declares "We have all visited the switch room at least once" and he is right, then all 16 prisoners will be set free. If he is in error (and the king keeps records of who has been there) then all will be immediately executed in a painful way.
After explaining the rules, the king says he will give the prisoners some time to discuss a strategy before separating them.
What strategy should the prisoners employ to guarantee eventual freedom?
The first satisfactory answer will be rewarded with a mystery prize. However, the winner must be present at a WoV event to collect and give proper notice that he will be there. Declining or re-gifting the prize is allowed.
After explaining the rules, the king says he will give the prisoners some time to discuss a strategy before separating them.
What strategy should the prisoners employ to guarantee eventual freedom?
The first satisfactory answer will be rewarded with a mystery prize. However, the winner must be present at a WoV event to collect and give proper notice that he will be there. Declining or re-gifting the prize is allowed.
I think somebody's perceived IQ goes up by ten points if he declares that he is a Monty Python fan.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 30th, 2015 at 7:42:44 AM
permalink
Assuming 1/16 prisoners are selected per day, and each prisoner has a fair "random" 1/16 chance of being chosen, the odds EACH prisoner has of being drawn EACH day is N*(1/16), where N is the number of days. Thus, after 16 days each prisoner should have 16*(1/16) chance of being selected to go to the switch room. To encompass repeats I'm thinking of giving each prisoner their own 16 day spread from which to be selected. Thus 16 days each * 16 prisoners = 256 days.
On the 257th day, the prisoner should declare they've all been to the switch room.
Rambling Thoughts: N*[(1/16)^16] where N is the number of days. This would lead me to believe they could never be 100% certain they've all been selected as this number rather small... 5.421*e^-20.
On the 257th day, the prisoner should declare they've all been to the switch room.
Rambling Thoughts: N*[(1/16)^16] where N is the number of days. This would lead me to believe they could never be 100% certain they've all been selected as this number rather small... 5.421*e^-20.
Playing it correctly means you've already won.
November 30th, 2015 at 7:51:58 AM
permalink
First, declare one of the prisoners to be a "Counter." Then, on first day, any prisoner who visits the room makes sure the switch is DOWN to insure a known state for Day 2. Beginning with Day 2, each prisoner (who is not the Counter) visiting the room flips the switch UP if it is currently DOWN, but only if he has not previously flipped the switch UP. Otherwise, he does nothing. When the Counter is led to the room, if the switch is UP, he flips it DOWN and increments his count (which starts at 1 for himself) by 1. Otherwise, he does nothing. When the Counter's count reaches 16, he can declare that all prisoners have visited the room.
Based on the last few puzzles, I am beginning to be concerned that we are helping to set free so many criminals who have committed capital offenses. ;)
"Dealer has 'rock'... Pay 'paper!'"
November 30th, 2015 at 8:28:54 AM
permalink
Quote: RomesAssuming 1/16 prisoners are selected per day, and each prisoner has a fair "random" 1/16 chance of being chosen, the odds EACH prisoner has of being drawn EACH day is N*(1/16), where N is the number of days. Thus, after 16 days each prisoner should have 16*(1/16) chance of being selected to go to the switch room. To encompass repeats I'm thinking of giving each prisoner their own 16 day spread from which to be selected. Thus 16 days each * 16 prisoners = 256 days.
On the 257th day, the prisoner should declare they've all been to the switch room.
Rambling Thoughts: N*[(1/16)^16] where N is the number of days. This would lead me to believe they could never be 100% certain they've all been selected as this number rather small... 5.421*e^-20.
I think you disproved your own solution. While the confidence can be high that after a long period of time everybody will have been in the Switch Room at least once, for any finite number of visits there will always be some chance that at least one person was never there. I'm looking for a strategy where when somebody says "We've all been in the Switch Room." He can be certain of being correct.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 30th, 2015 at 8:34:45 AM
permalink
Quote: JoemanFirst, declare one of the prisoners to be a "Counter." Then, on first day, any prisoner who visits the room makes sure the switch is DOWN to insure a known state for Day 2. Beginning with Day 2, each prisoner (who is not the Counter) visiting the room flips the switch UP if it is currently DOWN, but only if he has not previously flipped the switch UP. Otherwise, he does nothing. When the Counter is led to the room, if the switch is UP, he flips it DOWN and increments his count (which starts at 1 for himself) by 1. Otherwise, he does nothing. When the Counter's count reaches 16, he can declare that all prisoners have visited the room.
Correct! Mr. Joe has claimed the prize. Please declare if you accept, decline, or re-gift it (and how).
How would your solution change if there were no one visit per day guarantee? For example, the king lets prisoners into the Switch Room whenever he feels like it. He could lead 50 visits there in a day or go days with no visits.
Quote:Based on the last few puzzles, I am beginning to be concerned that we are helping to set free so many criminals who have committed capital offenses. ;)
The ACLU would be proud of us!
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 30th, 2015 at 8:41:43 AM
permalink
Each prisoner agrees that the first time he visits the switch cell, he will carve a notch into the wall using the shank hidden in his boot. (It's death row, of course he has a shank hidden in his boot.) The first prisoner to see 16 different marks on the wall tells the king they have all visited the switch room.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
November 30th, 2015 at 9:03:28 AM
permalink
Thank you for the prize, but unfortunately, I do not foresee myself in Vegas in the near future to collect. May I add the prize to the kitty for whoever solves your next puzzle?Quote: WizardCorrect! Mr. Joe has claimed the prize. Please declare if you accept, decline, or re-gift it (and how).
"Dealer has 'rock'... Pay 'paper!'"
November 30th, 2015 at 10:05:53 AM
permalink
Quote: MathExtremistEach prisoner agrees that the first time he visits the switch cell, he will carve a notch into the wall using the shank hidden in his boot. (It's death row, of course he has a shank hidden in his boot.) The first prisoner to see 16 different marks on the wall tells the king they have all visited the switch room.
The king will kill all of you in a painful manner for cheating.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 30th, 2015 at 10:08:53 AM
permalink
Quote: JoemanThank you for the prize, but unfortunately, I do not foresee myself in Vegas in the near future to collect. May I add the prize to the kitty for whoever solves your next puzzle?
You may!
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 30th, 2015 at 1:34:16 PM
permalink
Quote: WizardHow would your solution change if there were no one visit per day guarantee? For example, the king lets prisoners into the Switch Room whenever he feels like it. He could lead 50 visits there in a day or go days with no visits.
As with the previous solution, select a counter. However, in this case, every prisoner except the counter will flip the switch up if it is down and that prisoner has not flipped it up twice already. When the counter enters the room, he flips the switch down if it is up. When the count gets to 29 (starting the count at zero),, the counter knows that everybody has been in the room once.
The reason everybody but the counter has to do it twice is, if it starts down and a non-counter enters first, that prisoner flips it up, but when the counter enters, he has no way of knowing if it started up or if someone flipped it up. The first prisoner has to flip it up again, so everybody has to be told to flip it up twice; it is possible for 14 of the 15 non-counters to enter twice and flip it up (if it started down), but on the 29th flip, we know that all 15 non-counters have flipped it up at least once.
The reason everybody but the counter has to do it twice is, if it starts down and a non-counter enters first, that prisoner flips it up, but when the counter enters, he has no way of knowing if it started up or if someone flipped it up. The first prisoner has to flip it up again, so everybody has to be told to flip it up twice; it is possible for 14 of the 15 non-counters to enter twice and flip it up (if it started down), but on the 29th flip, we know that all 15 non-counters have flipped it up at least once.
November 30th, 2015 at 2:44:28 PM
permalink
As with the previous solution, select a counter. However, in this case, every prisoner except the counter will flip the switch up if it is down and that prisoner has not flipped it up twice already. When the counter enters the room, he flips the switch down if it is up. When the count gets to 29 (starting the count at zero),, the counter knows that everybody has been in the room once.
The reason everybody but the counter has to do it twice is, if it starts down and a non-counter enters first, that prisoner flips it up, but when the counter enters, he has no way of knowing if it started up or if someone flipped it up. The first prisoner has to flip it up again, so everybody has to be told to flip it up twice; it is possible for 14 of the 15 non-counters to enter twice and flip it up (if it started down), but on the 29th flip, we know that all 15 non-counters have flipped it up at least once.
The reason everybody but the counter has to do it twice is, if it starts down and a non-counter enters first, that prisoner flips it up, but when the counter enters, he has no way of knowing if it started up or if someone flipped it up. The first prisoner has to flip it up again, so everybody has to be told to flip it up twice; it is possible for 14 of the 15 non-counters to enter twice and flip it up (if it started down), but on the 29th flip, we know that all 15 non-counters have flipped it up at least once.
I agree!
For those who correctly answered, the way I first heard this puzzle there were two switches and 23 prisoners. I think the second switch was thrown in there as a red herring. Do you like the telling better the simple way with one switch or would you prefer to torture your victims a bit by confusing them with a second switch they don't need?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 30th, 2015 at 3:23:18 PM
permalink
Quote: WizardAs with the previous solution, select a counter. However, in this case, every prisoner except the counter will flip the switch up if it is down and that prisoner has not flipped it up twice already. When the counter enters the room, he flips the switch down if it is up. When the count gets to 29 (starting the count at zero),, the counter knows that everybody has been in the room once.
The reason everybody but the counter has to do it twice is, if it starts down and a non-counter enters first, that prisoner flips it up, but when the counter enters, he has no way of knowing if it started up or if someone flipped it up. The first prisoner has to flip it up again, so everybody has to be told to flip it up twice; it is possible for 14 of the 15 non-counters to enter twice and flip it up (if it started down), but on the 29th flip, we know that all 15 non-counters have flipped it up at least once.
I agree!
For those who correctly answered, the way I first heard this puzzle there were two switches and 23 prisoners. I think the second switch was thrown in there as a red herring. Do you like the telling better the simple way with one switch or would you prefer to torture your victims a bit by confusing them with a second switch they don't need?
I liked it straightforward; I was able to follow both solutions from beginning to end without the red herrings. Good job, Joeman and TDG!
If the House lost every hand, they wouldn't deal the game.
November 30th, 2015 at 4:47:46 PM
permalink
Quote: Wizard
I agree!
For those who correctly answered, the way I first heard this puzzle there were two switches and 23 prisoners. I think the second switch was thrown in there as a red herring. Do you like the telling better the simple way with one switch or would you prefer to torture your victims a bit by confusing them with a second switch they don't need?
It doesn't really change the answer to have two switches, but it would allow the prisoners to escape significantly sooner. The non counters can flip up either switch if one is down and the counter can (potentially) count two others at a time. I think the puzzle is better with one switch, though.
December 1st, 2015 at 6:32:31 AM
permalink
Quote: WizardFor those who correctly answered, the way I first heard this puzzle there were two switches and 23 prisoners. I think the second switch was thrown in there as a red herring. Do you like the telling better the simple way with one switch or would you prefer to torture your victims a bit by confusing them with a second switch they don't need?
I have heard two versions as well; the "follow-up question" was the second version
and in the first, everybody was shown at the start of Day 1 that the switch was in the down position, but again, there was no "exactly one prisoner in the room per day" requirement.
December 1st, 2015 at 7:01:45 AM
permalink
From a problem-solving standpoint, I would prefer the simpler way. But a part of me doesn't want to shy away from a tougher challenge.Quote: WizardDo you like the telling better the simple way with one switch or would you prefer to torture your victims a bit by confusing them with a second switch they don't need?
I think having a second switch in the problem may have thrown me off. However, 23 prisoners instead of 16 may have helped me because with 2^4 prisoners and a binary switch, I initially thought the solution might involve some manipulation of the powers of 2.
"Dealer has 'rock'... Pay 'paper!'"
December 1st, 2015 at 12:44:18 PM
permalink
Follow up question:
1. How long, on average, would it take the prisoners to get free?
2. How many days for a 90% (95%) chance to be free by then?
In both cases we assume the selection of the king is completely random each day.
1. How long, on average, would it take the prisoners to get free?
2. How many days for a 90% (95%) chance to be free by then?
In both cases we assume the selection of the king is completely random each day.
