Author |
Topic: switches (Read 1164 times) |
|
Sam
Newbie
Posts: 30
|
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 |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: switches
« Reply #1 on: Aug 21st, 2005, 2:31pm » |
 Quote  Modify
|
You can use the strategy for "100 prisoners and one lightbulb" by using one of the switches to signal, and the other to not-signal (i.e. leave the signal switch in the position it is in)
Of course that's quite probably not the best one can do.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sam
Newbie
Posts: 30
|
|
Re: switches
« Reply #2 on: Aug 21st, 2005, 9:15pm » |
Quote Modify
|
towr ,can u please explain a bit more about your saying and what exactly is this 100 prisoners problem  ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: switches
« Reply #3 on: Aug 22nd, 2005, 1:27am » |
Quote Modify
|
100 prisoners & a light bulb
It's a long thread, and there's no definite best solution. But the easiest solution works.
The prisoners pick a leader. His task is to count how many prisoners have definitely been in the switch room by observing when the left switch is 'up', and setting it to down if it is (otherwise toggling the right switch).
The other prisoners all set the left switch to up if 1) it is down and 2) they never switched it up before. Otherwise they toggle the right switch.
Once the leader has counted to 99 he knows that including himself everyone has been in the room, and thus can tell the warden and get everyone free.
Admittedly there is one small problem. But I'll let you figure that out 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: switches
« Reply #4 on: Aug 22nd, 2005, 5:47am » |
Quote Modify
|
You can make use of the 2 switches:
Define a code: (u=up, d=down)
dd = 0
du = 1
uu = 2
ud = 3
This way you can store up to 3 tokens. A prisonner can add a token by flipping one switch and the leader can collect 3 token at a time, also flipping one switch. When he has collected 33x3 token, he can ask for the release.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: switches
« Reply #5 on: Aug 22nd, 2005, 6:07am » |
Quote Modify
|
Grimbal, you always have to flip a switch. What if people who have already been there are called in?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: switches
« Reply #6 on: Aug 22nd, 2005, 6:23am » |
Quote Modify
|
OK, each of the 99 "other" prisonners have a token. They can transfer the token to the counter (i.e. the switches) if the counter is not 3 and they still have the token (i.e. they were never in or when they were, the counter was full already). They only add it once.
When all token have been added to the counter and all token have ben acknowledged by the leader (by clearing the counter), the wait is over.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: switches
« Reply #7 on: Aug 22nd, 2005, 7:07am » |
Quote Modify
|
I don't think you answered River's objection, Grimbal; what happens when someone who has already given up their token reenters the room? They have to flip a switch which will either advance or retreat the counter--they have no means to leave it unaffected.
Also, the initial conditions assumption from 100 Prisoners and a Lightbulb doesn't hold; this variant specifically states that the initial positions of the switches are unknown, and that prisoners are picked at random intervals. I don't see any way for the leader to know with 100% certainty that he's the leader (or, alternatively, if the leader is chosen beforehand, what the initial value of the counter is), as no one can know for sure whether or not they were the first ever person to enter the room.
I think a more subtle strategy is needed here, perhaps along the lines of the one for yegulalp's 100 anonymous prisoners & a light bulb, no?
--SMQ
|
| « Last Edit: Aug 22nd, 2005, 7:12am by SMQ » |
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: switches
« Reply #8 on: Aug 22nd, 2005, 7:56am » |
Quote Modify
|
Aaah. I see. As too often, I read the problem too fast and missad a crucial point.
"He can't move both but he can't move none either.".
Then It is equivalent to the situation where the is a single switch that you move freely. The only additional information you have is whether the number of visits is even or odd, but since the first person can be sent in twice in a row, it becomes useless).
(.. Grimbal is re-reading the problem ..)
Oh? They are 23? That makes 1 leader and 22 followers, then.
(.. reading ..)
Oh? And you don't know the starting position? This IS a problem. You might be off by one token. So you need to start with 2 token each, and only when the leader has collected 43 (2*22-1), he can tell everybody was there.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: switches
« Reply #9 on: Aug 22nd, 2005, 10:53am » |
Quote Modify
|
Odd that variations on 100 prisoners + Light bulb with more difficult conditions are easier to solve - well, not really because the time-consuming problem with the classic version isn't finding a solution, but identifying the "best" solution...
Anyway, for this one, as has been pointed out, the second switch cancels with the forced action, leaving a variant which has been discussed in at least one of the threads - on the hard forum - unknown frequency of visits, which rules out any multi-stage approach, and unknown start time and initial state of the bulb, which, collectively, requires doubling the number of tokens out there to compensate for the potential rogue token.
So: Each prisoner except a nominated leader starts with a count of two. The first two times they find switch A off, they turn it on and reduce their count by 1. Any other time, they toggle switch B. The nominated leader turns switch A off every time he finds it on, and counts how often he does so, toggling switch B the rest of the time. Once the leader's count reaches 44, he declares victory.
The maximum number of counts available to the leader is either 44 or 45 - 2 from each other prisoner and possibly one from the initial state. When the leader has counted 43, there are either 1 or 2 counts yet to be collected, and it's still possible that some poor prisoner is sittingin his cell with both of them, never having seen the switches.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: switches
« Reply #10 on: Aug 22nd, 2005, 10:57am » |
Quote Modify
|
And, also in the spirit of the original 100 prisoners thread:
Since no-one except the prisoners ever enters the switch room, it's going to get pretty grubby - each prisoner leaves a mark of some sort the first time they visit. Once all 23 prisoners have made their mark, they get released...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: switches
« Reply #11 on: Aug 22nd, 2005, 11:29am » |
Quote Modify
|
Hm... yes, the needed count is 45 of course.
But I have been thinking. (yes, sometimes...). There are actually 2 independent chanels. You know whether a switch has been set during an even or an odd visit. So it is possible to transfer a single token on even visits and multiple token on odd visits. I don't know if it can be made to work better. It is difficult to control what you send and what you get. Just an idea.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2874
|
|
Re: switches
« Reply #12 on: Aug 23rd, 2005, 6:47pm » |
Quote Modify
|
on Aug 22nd, 2005, 11:29am, Grimbal wrote:Hm... yes, the needed count is 45 of course.
But I have been thinking. (yes, sometimes...). There are actually 2 independent chanels. You know whether a switch has been set during an even or an odd visit. So it is possible to transfer a single token on even visits and multiple token on odd visits. I don't know if it can be made to work better. It is difficult to control what you send and what you get. Just an idea. |
|
You may be onto something - I thought it was trivial to prove that splitting into two channels would always be worse, but there're some interesting corner cases where the "obvious" conclusion I was looking for doesn't seem to hold. It's about 3am my time, so I'm not going to try and write up anything coherently, but there are a couple of possible systems that could work better.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print