Author |
Topic: Prisoners again- with 2 switches (Read 17573 times) |
|
mad
Junior Member
Posts: 118
|
 |
Prisoners again- with 2 switches
« on: Feb 25th, 2008, 10:24am » |
 Quote  Modify
|
The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.
"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. I am not telling you their present positions. The switches are not connected to anything.
"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.
"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure.
"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."
What is the strategy they come up with so that they can be free?
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
|
Re: Prisoners again- with 2 switches
« Reply #1 on: Feb 25th, 2008, 11:01am » |
Quote Modify
|
Of course if you don't optimize the number of visits, you can reduce the problem to 2 state switch without timing (the other switch does not carry information in this strategy).
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Prisoners again- with 2 switches
« Reply #2 on: Feb 25th, 2008, 3:37pm » |
Quote Modify
|
This is the 100 Prisoners & 2 Lightbulbs riddle. There is a thread for it here.
It doesn't look like that thread ever came to a full consensus on the solution, however.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Prisoners again- with 2 switches
« Reply #3 on: Feb 25th, 2008, 4:00pm » |
Quote Modify
|
on Feb 25th, 2008, 3:37pm, Icarus wrote:This is the 100 Prisoners & 2 Lightbulbs riddle. There is a thread for it here.
It doesn't look like that thread ever came to a full consensus on the solution, however. |
|
Not exactly as they must switch exactly one switch during each visit.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Prisoners again- with 2 switches
« Reply #4 on: Feb 26th, 2008, 12:51am » |
Quote Modify
|
There is a difference.
In "100 prisoners and a light bulb" there is a version with 1 visit a day, which allows the meaning of the switch to change from day to day, and there is a version without a time line that requires that every visit to is handled in the same way.
In this riddle, the prisoners can distinguish 2 cases. The switch can have a different meaning depending on whether both switches are in the same position or not. I am not sure how (and whether) that distinction can be put to use efficiently.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Prisoners again- with 2 switches
« Reply #5 on: Feb 26th, 2008, 2:16am » |
Quote Modify
|
This seems to be the same as the original one, that had been discussed among Hungarian mathematicians' and was the basis of the 100 prisoners riddle. The original is still available on IBM's page.
There are two main differences between the 100 prisoners and 1 light ball and this one:
There are two switches. BUT a prisoner must switch one. This means it is the same in terms of information as one switch that you might or might not change.
There is no fixed period of visits, i.e. all periodicity related solutions are out of question. As a second consequence of it, the switch can never be known as reset to "off". In the fixed period game we can say that the first visitor sets it to "off" and the game starts on the second day, knowing that the switch's original position is off. In the game without fixed periods, we can never know whether the game has started at all. This is why the best solution known waits until everybody was there twice.
The two prisoners and 2 (or n) light balls is totally different, if you can decide whether change the status of one or two or none of the switches.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: Prisoners again- with 2 switches
« Reply #6 on: Feb 26th, 2008, 11:32am » |
Quote Modify
|
As Grimbal pointed out, you can reliably distinguish between the two parities of visit-events, however it's not obvious how to take advantage of that - particularly with the unknown initial state potentially adding more spurious counts.
The best I can come up with would be to start each prisoner with 3 tokens (a single and a double) and pass single tokens on the A visits, and doubles on the B visits, with prisoners merging pairs of single tokens into doubles where possible, and the designated counter never passing a token.
I suspect this will run slower than ignoring the parity information and just running the standard 2-tokens per prisoner, single phase solution.
I also suspect that any gains from passing larger bundles of tokens on the B visits will be swamped by the cost of having more tokens per prisoner to start with - essentially, you're looking at starting each prisoner with an A-token and a B-token and having a rule whereby A-tokens can be converted into B-tokens (but not vice versa) at the cost of making both types of token harder to collect - under standard conditions, a token gets collected every time the counter visits and at least one token-bearer has visited since the counter's last visit. With the alternating A/B, a token only gets collected when the counter visits and the previous visitor was a token-bearer - obviously far worse...
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Prisoners again- with 2 switches
« Reply #7 on: Feb 26th, 2008, 4:27pm » |
Quote Modify
|
Because the prisoners are forced to flip a switch, the relative positions of the switches (= or not =) will switch with every visit. I think the fact that the visitors must always flip a switch pretty much destroys the utility of the second switch for sending messages.
Here is one solution:
The left switch will be considered meaningless. Visitors who do not wish to send a message will flip it. This reduces the problem to 100 prisoners and 1 light bulb with uneven visits and uncertain initial state. To solve that problem:
Pick a leader. On the leader's first visit he will flip the (right) switch, and remember the position he left it in. No one else is to ever flip the switch unless:
(1) the switch is currently on, and
(2) they have seen the switch off before, and
(3) they haven't flipped the switch before.
Any time that the leader visits and sees the switch off when he did not leave it off, he will increment his count and turn the light back on. If the switch is in the same position he left it in before, he will flip the switch, but not increment his count.
When his count reaches 99, he declares everyone has visited.
-------------------------------
Regular prisoners only get one chance to be counted. But they have to wait until they are sure that their message will be heard. That is, until they are sure that the leader has visited the room. So we have the rule that no one else can touch the switch until they have seen the switch in both positions. This can only occur after the leader's initial visit. Unfortunately, it is quite possible that someone's first visit may not come until everyone else has already been counted. If the leader did not switch the light off himself, this person would never have the opportunity to see the light in both positions, and so would never be sure that it was safe to send his message. Therefore, the leader has to switch the light on and off himself, even though when he switches it off, it means that no messages can be sent until he visits again.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Prisoners again- with 2 switches
« Reply #8 on: Feb 27th, 2008, 12:21am » |
Quote Modify
|
As I also pointed out before and agreeing with Icarus there is no difference between 1 switch optional to be switched and 2 switches where one and only one must be switched. As Icarus says, you only look at switch A, while switch B is only used to switch something if you do not want to switch A. So in this context there is no difference between this variation and the 100 prisoners and 1 switch.
The uncertainty of the initial position is causing the problem. Because of the non predictable periodicity, there is no chance to re-set the switch if the initial state is not known.
This is why the standard solution (single pre-appointed leader) counts until 197, allowing every prisoner to show his presence twice. Because of the uncertainty of the initial state, one count of the first prisoner might be lost. In this case 197 is reached when all prisoners were there twice. If the first count is not lost, then 197 is reached when 98 prisoners were there 2 times and 1 only once.
This approach is safe and probably also much faster than Icarus's one, where the counting only starts when every priosoner already had seen the switch in both positions.
Edit note: A xor B reference removed.
|
| « Last Edit: Feb 28th, 2008, 2:45am by jollytall » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Prisoners again- with 2 switches
« Reply #9 on: Feb 27th, 2008, 3:50pm » |
Quote Modify
|
A xor B switches with every visit, so its state can't be used for passing information. This is why I went with one switch and ignored the other.
While the two-token method certainly works better than mine, I think the problem is not missing the first visitor's count, but rather falsely counting a visit that didn't actually occur. If the switch is initially in the message position, no one realizes that it wasn't set that way by an earlier visitor, so the false count is picked up by the Leader. I would say that leader needs to count to 198 to be sure he has counted everyone.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Prisoners again- with 2 switches
« Reply #10 on: Feb 27th, 2008, 11:52pm » |
Quote Modify
|
on Feb 27th, 2008, 3:50pm, Icarus wrote:| If the switch is initially in the message position, no one realizes that it wasn't set that way by an earlier visitor, so the false count is picked up by the Leader. I would say that leader needs to count to 198 to be sure he has counted everyone. |
|
Well, the leader knows he hadn't been there to reset the switch; he can only be sure that something is a message after his first visit.
If he counts what he encounters on his first visit as possibly being a real message, then he'd have to count to 198; if he disregards it, he'd have to count to 197 (and the first prisoner's first message may have gone wasted).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Prisoners again- with 2 switches
« Reply #11 on: Feb 28th, 2008, 2:44am » |
Quote Modify
|
Forget my comment re A xor B. Original post edited.
As towr say, the difference is in the starting position. If the leader starts counting once he reset the switch, the counting should go up to 197 (and so, 1 visit of 1 prisoner might be lost). If the leader already counts the first time he goes in (if the switch tells him to count), then he might count the initial state as a false visit, so he has to count up to 198.
|
| « Last Edit: Feb 28th, 2008, 2:46am by jollytall » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Prisoners again- with 2 switches
« Reply #12 on: Feb 28th, 2008, 4:47am » |
Quote Modify
|
So, for 23 prisoners, how many does he count?
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Prisoners again- with 2 switches
« Reply #13 on: Feb 28th, 2008, 6:24am » |
Quote Modify
|
2*(n-2)+1, i.e. 43 with the most comonly accepted logic.
To further clarify the two logics:
If the leader starts to count once he reset the switch during his first visit, he must count till 43 (23 prisoners).
If the leader is already allowed to count 'one' when he enters (and finds the switch switched on) then he needs to count till 44. But if he finds the switch off at his first visit, that means that the switch was off at the beginning AND noone has visited it yet, he doesn't need to count 44 (although that is not a problem either), but 43 is sufficient.
With other words the two logics are the same most of the cases, but the "start counting after your first visit and count till 43" is shorter in that case when the leader visits the room first and the original status of the switch is off. This has 1/46 probability, when the 44 counting is results in a longer escape time.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Prisoners again- with 2 switches
« Reply #14 on: Feb 28th, 2008, 3:45pm » |
Quote Modify
|
It seems to me now we agree that it is 23C2 problem refered by n prisoners and a k-state switch as the parity of number of visits does not carry any usefull information.
|
| « Last Edit: Feb 28th, 2008, 3:49pm by Hippo » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Prisoners again- with 2 switches
« Reply #15 on: Feb 28th, 2008, 4:03pm » |
Quote Modify
|
on Feb 27th, 2008, 11:52pm, towr wrote:
Well, the leader knows he hadn't been there to reset the switch; he can only be sure that something is a message after his first visit.
If he counts what he encounters on his first visit as possibly being a real message, then he'd have to count to 198; if he disregards it, he'd have to count to 197 (and the first prisoner's first message may have gone wasted). |
|
I see. Thanks.
I know I've read these threads before, but I failed to remember the logic.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
mattian
Senior Riddler
 
Gender:
Posts: 404
|
|
Re: Prisoners again- with 2 switches
« Reply #16 on: May 11th, 2010, 2:09pm » |
Quote Modify
|
THIS IS MY SOLUTION
Please let me know if there are any holes in this approach.
Step 1
Use switch A as the primary switch which may be toggled or left alone as necessary. Use switch B as a dummy switch that allows a prisoner to leave switch A alone. Thus switch A becomes a single optional switch, while switch B absorbs "noise" and carries no information.
Step 2
Elect a leader. The leader is responsible for managing the state of switch A (hereafter referred to as "the switch").
Step 3
Assign a count of 1 (a token) to each prisoner before commencing.
Strategy:
Any non-leader who enters the room will abide by the following rules:
1. If only one state (either 1 or 0) has EVER been seen on the switch, do nothing, retain token and skip the remaining steps.
2. If both states (both 1 and 0) have been seen on the switch then NOTE that the leader has visited at least once and continue with step 3.
3. If the current state is 0 and current prisoner has a token, then set switch to 1 and relinquish token.
4. If the current state is 1 then do nothing, but remember for next time that leader the has visited at least once.
5. If the current state is 0 and the current prisoner has no tokens, do nothing.
The leader when he enters will do the following:
a. If the initial value of the switch was 0, then set it to 1. This will not allow any prisoners to submit their tokens because the switch will remain at 1 until A returns. But this is fine because it allows some prisoners to witness a state change (see Step 2.) thus informing them that the leader has visited at least once and allowing them to submit their tokens at their next opportunity.
b. If the initial value of the switch was 1, then set it to 0. This allows some prisoners to see a state change thus informing them that the leader has visited at least once and allowing them to submit their tokens at the next opportunity.
c. At any point the leader may opt to leave the switch at 1 instead of resetting it to 0, if he is missing prisoners who may potentially have missed a state change. It is safe to do so because in the 1 position, no one can misleadingly submit a token. The prisoner can use his discretion to determine how long to leave the switch in a chosen state, but he will collect counts only when he witnesses a change from 0 to 1 (ie. when he leaves the switch at 0 and returns to find it at 1). But he cannot forget that every prisoner has to get the signal that he has started counting - and that signal comes in the form of a state change that they have witnessed.
d. When the leader's count reaches 23, declare that all prisoners have visited.
Note: If the leader sets the switch to 0 and a subsequent prisoner sets it to one by "submitting" his token, a third prisoner might see the state change before the leader sees it. This is not a problem because ANY state change is indicative of the fact that the leader has visited and counting has started. But that third prisoner won't submit a token at that visit because the switch will be at 1, so he will retain his token until a later visit.
----------------------------------
UPDATE:
I just reread the thread. Turns out icarus already posted this solution. My apologies.
|
| « Last Edit: May 12th, 2010, 7:11am by mattian » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Prisoners again- with 2 switches
« Reply #17 on: May 12th, 2010, 2:36pm » |
Quote Modify
|
My intuition (as in it's been 5-6 years since I worked seriously on this family of problems, and I'm not about to try working out solid figures) is that it's best for the leader to flip the signal switch on every visit, but that 23 prisoners is more than enough for "count twice and possibly miss one" to be more efficient than waiting for every prisoner to have seen the signal switch change state and then been able to pass a signal...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
The "count twice and possibly miss one" approach takes 1128.05 visits, from what my program tells me. Icarus' and Mattian's approach takes 718.43 visits. (Well, assuming Mattian makes the same choice in case c) as Icarus.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Prisoners again- with 2 switches
« Reply #19 on: May 13th, 2010, 8:44am » |
Quote Modify
|
Shows what intutition is worth! 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Prisoners again- with 2 switches
« Reply #20 on: May 13th, 2010, 9:49am » |
Quote Modify
|
There is room for optimization as well. When the leader returns to the room and find the light is on, if he only flips the switch with 50% chance, the process only takes 676.22 visits on average; at 10%, it's 649.86. Making that probability depend in some way on how often he visited before should improve things further.
Most people will have seem the light off in the first 200 visits, so there's little point to switching the light off for the leader after that point. (But of course he only knows how often he has visited himself, plus how many he has counted. But after 10 visits he can estimate there have likely been over 200 visits.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Prisoners again- with 2 switches
« Reply #22 on: Aug 3rd, 2010, 8:10am » |
Quote Modify
|
I'm still working on the details, but the leader should, in fact, be able to estimate, based on the number of uncounted prisoners and the number of times he has visited since the last count, whether leaving the light on or off is more likely to result in a successful count. His estimate would be based on an estimate of the chances of the light remaining off because no one countable had visited the room versus their not having seen a state change.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Prisoners again- with 2 switches
« Reply #23 on: Aug 5th, 2010, 2:22am » |
Quote Modify
|
on May 13th, 2010, 9:49am, towr wrote:There is room for optimization as well. When the leader returns to the room and find the light is on, if he only flips the switch with 50% chance, the process only takes 676.22 visits on average; at 10%, it's 649.86. Making that probability depend in some way on how often he visited before should improve things further.
Most people will have seem the light off in the first 200 visits, so there's little point to switching the light off for the leader after that point. (But of course he only knows how often he has visited himself, plus how many he has counted. But after 10 visits he can estimate there have likely been over 200 visits.) |
|
What about to switch on only when probability drones will switch on is less than 1/2? How to compute this probability is described in the other thread.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Prisoners again- with 2 switches
« Reply #24 on: Aug 5th, 2010, 3:17am » |
Quote Modify
|
It sounds like something that might work, but I'm not quite sure how the leader can best estimate that probability, which depends on the number of times he's visited, his current count, and his previous decisions.
The last factor especially would explode a simulation to find out (too many possible histories).
|
| « Last Edit: Aug 5th, 2010, 3:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print