Fog Creek Software
Discussion Board




Switches Puzzle

Hi all,

I couldnt find any solution or discussion on the "Switches Puzzle" (#1 on the list), so I decided to use this space :-)
Kindly ignore if this has been discussed.

Here's my solution:

Strategy: The prisioners decide to flip the right (could as well be left) side switch only if they are flipping or the first time and the left side one for any subsequent flips.

Working: Each time a prisioner is taken to flip a switch, he just flips the right one (except the first time) but observes the change in position of the left one from the last time. If the position is same as it was, the last time he visited the switch room, he knows that an even number of people have visited the room for the first time, he assumes the worst case (zero). If, one the other hand, the position is changed from the last time, he knows that an odd number have visited and assumes the worst case again (one). Once a prisioner has his counter = 23, he knows atleast 23 have visited the switch room.

Thanks!

EE/ CS Guy
Friday, July 23, 2004

The problem here is that the worst case assumption can lead to everyone being stuck at a count of 2 forever.

Assume everyone gets brought in for the first time without any repeats, then gets brougt back in in the same order.  Boom, everyone sees an odd number of people since their first visit, assumes 1 other person has come through since then, and that only 2 people have ever entered the room.

Not that i don't have kinks in my solution fo this.. but  this one probaly leaves prisoners stuck forever more often than not.

Notadragon
Tuesday, July 27, 2004

The solution:

The prisoners decide on one of them ( the_chosen_one ) keeping count and turning off right switch whenever it's on.  Other prisoners will turn right switch only ones, when they find it off, otherwise they would just change the position of left switch. the_chosen_one will switch off right switch whenever he sees it on and keep count of times he switch off right switch, if anytime the right switch is off when he enters the room he will just change the position of left switch. When his count reaches 23 he knows that atleast once everyone has entered the room.

Sam Bhai
Tuesday, August 03, 2004

Doesn't work if the switch that the "chosen one" flips was initially on.  No one else will flip it off before the chosen one goes to the room.  And the chosen one will think that someone flipped it on, so he'll count 1. 

If you make everyone flip it on twice, only when they see it off, when the chosen person counts to 44, he'll know that everyone was in the room at least once. 

Sean
Wednesday, August 04, 2004

Didn't you mean 46 (23+23) Sean ?
Because if you start with 1, "Neo" will count one, so when it gets to count 46, everyone has visited twice, except one of the guys (which has visited only once), but since we only need to know if everyone visited (at least once), we only need 46.
It will also work, when it starts from 0.
You could say 44, if "Neo" doesn't count himself though.

Rui Martins
Wednesday, August 04, 2004

Sean you are right that my solution won't work always, because if the switch was initially ON, the count would reach 23 and he'll figure out that everyone has visited the room, but when the switch was initially OFF the count would never reach 23 (It'll remain at 22).

Making everyone else switch ON twice and "the_chosen_one" counting till 44 will resolve this problem.

Sam Bhai
Thursday, August 05, 2004

Neo could count till 23, because he could exclude himself and "initial ON" case.

Sergei Shishkin
Sunday, August 08, 2004

I think Sam got it right the first time with a small change. Assuming that the prisoners can tell the passing of days then the first prisoner in the room knows that he is first. If the first is the choosen one, he will make sure the right switch is in OFF position (switch it, if it is currently in a ON position, or switch the left switch if the right is already in OFF position). If the first person is not the choosen, he will make sure the right switch is in the ON position. The rest is like Sam described.

Yair Sarig
Thursday, August 26, 2004

The answer was inspired by everyone else's comments, especially Sam's.

Strategy:
1) Only Neo is allowed to turn switch B from on to off
2) Everyone else shall turn switch B on from off twice, if it is off

Instructions for 'common prisoners':
1) If B is off, turn it on. But ONLY do this twice
2) If it's your third time here, OR if someone else has already switched B to on, toggle A to pass your turn.


Instructions for Neo:
1) If B is on, turn it off.
2) If B is off, ignore it and toggle switch A (to pass time)
3) Keep count of how many times you repeat action 1 of turning B back off.
4) when you have counted to 43, call the guards, and you will be set free.

How it works:
Assume Neo was not the first guy let into the room. Someone else will have turned on B if it was originally off, or left it on if it was originally on.
Assume Neo was the first one in. He'll turn B off if it was on. He'll leave it off if it was off.
(by the way, Neo will know that he is the first one in if B is off)
Neo will count how many times he turns B back off after someone has turned it on to signal having been there once or twice.

Why they have to do it twice:
Because if Neo wasn't the first one in and some guy turns it on, Neo won't know that his first time into the room, and the guy's "vote" won't be counted and they'll be forever stuck at count 21 (Neo doesn't get to "vote"; one guy's "vote" is wasted).

If everyone does it twice:
even if one guy gets repeatedly missed, he'll eventually get a valid turn because "given enough time, everyone will eventually visit the switch room as many times as everyone else". So everyone gets a turn, just a matter of when. So when Neo counts to 43, he knows that everyone can only ever "vote" twice, making a maximum of 44 counts. However, if one did turn it on before Neo's first turn, it won't ever get to 44.
*But* seeing that even if one guy is consistently missed, that means 21 cellmates can and will have "voted", making a total of 42. Which means that 43 will signal that everyone has gone twice and one guy has either gone twice or just now, once.

There. Really long rambling answer. But what I read from you guys were too complicated for me. I hope this helps dummer people like me.

ChocoBean
Sunday, August 29, 2004

The flaw in the above logic.

To count 43, Neo has to be inside the switch room 43 times and toggle the switch 43 times. That means the rest of the prisoners have gone to the switchroom 2 times each where as Neo has been 43 times.

Arent we violating the equal visit constraint?

Aks
Monday, August 30, 2004

Nope. See, of course everyone will also have to visit the room as many times, they just won't be able to insert useful input most of the time. (only two of the 43+ times actually. sucks to be them)
We don't want to get out quickly, we just want to make sure we get out alive. Eventually.
The question asks for 100% certainty, not a reasonable gamble.

ChocoBean
Monday, August 30, 2004

how about this?

repeat:
01->11
11->10
00->10
10->11

nonrepeat or neo:
00->01
01->00
10->00
11->01


neo when he first enters adds himself to his prisoner count and switches according to nonrepeat rules, but on subsequent visits he continues to use nonrepeat rules without counting himself. now every time neo enters if the
switches are in a repeat state or in a nonrepeat state that isn't the one he left them in, he adds one to his count. when the count reaches the number of prisoners, neo knows everyone has been in the switch room at least once.

Lee
Wednesday, September 01, 2004

um, guess i should've noticed something amiss while typing " if the
switches are in a repeat state...he adds one to his count". :/

Lee
Thursday, September 02, 2004

Uhm, this sounds awfully compllicated...

I'd solve this, by just hitting any switch at random every time you enter the room BUT if you go there the first time you leave your left shoe there.

If you enter the room and see 23 shoes, well, game. :)

(I tried to find something in the rules that forbid this, but couldn't, so I guess this counts as a solution. But of course, yours are way more in what I'd think the questioner wanted to hear)

:) Martin

Martin Häcker
Tuesday, September 07, 2004

Can you imagine the chance of regaining your freedom after committing a crime?  Is it possible for these prisoners to come up with a solution in a constructive manner?  Well, if you ask me, no.  However, that is not the question being asked here.  The many solutions attempted to solve this problem in this forum have failed to recognize one thing, how will they know the number count if they are all isolated from each other? There are only two switches, whether on or off, how will they know how many times it has been flipped and by whom?  In addition, they don’t even know the starting positions of the switches.  They will only know how many times they have been there.  Really, there is no solution; there is no freedom for these prisoners until they have served their time.  Of course, if there were a genius in the bunch, than maybe it would be possible to find a solution; then again, if there were a genius, than he/she would not have been caught in the first place.

This brainteaser is just to see if you can pinpoint the obvious.  The obvious being the words prisoners and freedom, which don’t go together so there is no solution.  That is my opinion; of course, I could be way off.

Angela Filippi
Tuesday, September 07, 2004

There is a solution 'cause I got it. what I think every one is skirting around but not getting is the fact that they can plan for each day they are there. It's a binary state problem and as well as the switches you can use the concept of 'odd' and 'even' days served. Using a  "strategy" based on this allows every "chosen" prisioner to determine whether the person who last entered the room was a first-timer or a repeater. Basically, when the prisoners get together they decide on either LEFT or RIGHT switch and 'OFF' or 'ON' state for 'ODD' and 'EVEN' days served.
When a prisoner is a 1st-timer, he will set the chosen switch to the chosen state for the day he is in the room. So when another prisoner enters he will know if the most recent previous visit has been by a 1st-timer or not. Repeaters make sure the chosen switch is in the inverse state when they leave so that any future visiting prisoners know that a repeater was the last to visit. When a prisoner has 22(since everyone has a mark for day 1)counts marked for correct position of the chosen switch then they can all get out!
There may be an even quicker (for the prisoners) solution, but I cannot think of one off the top of my head.

I have to say, it was my wife that figured it out, as I was fumbling around with similar solutions to the above, and realising they wouldn't work.

Ratso
Saturday, September 11, 2004

I may be missing something, but if i am not i believe Chocobeans solution on 29th Aug seems to be correct. and ofcourse his argument posted on 30th proves the point..I dot see anything wrong with that one....is there something wrong??

AJ
Tuesday, September 14, 2004

I have spent a lot of time thinking about the problem and I have found another solution. I'm belive it is a slightly "better" solution than the one offered by ChocoBean in the sense the the prisioners get out faster. However it might be a "worse" solution in the sense that the algorithm is slightly more complicated.

Strategy:
NEO counts the times switch B has been switched from on to off, i.e. it was on when he left the room and it is on when he enters. Neo always toggles switch B. (This is the way to convince them that he has been in the switchroom)

Commoners switch B once and only once from on to off once they are convinced that NEO has been in the switch room. They are convinced that NEO has been in the switchroom once they have seen switch B change.

I have written a Perl program to verify my solution and the solution provided by ChocoBean and it seems to work. On  averge ChocoBean's solution requires around 1100 visists while my solution requires around 725 visits.

I would be happy to post the Perl implementations if anyone is interrested.

Henrik Sandell
Wednesday, September 22, 2004

Ok, here is the solution: one person makes some type of stabbing implement from the springs in his bed and when he has enough for everyone, he makes a guess (probably wrong) and we kill those stinkin' gators.

Stan Owens
Monday, September 27, 2004

I don't see how any (?) of these solutions would work, because its based on the following false assumptions:

- That the warden will select the prisioners evenly.  Based on the question, its conceivable that he could send the same guy to the room 50 times and then the next guy 50 times and so on.

- That the warden will choose only one per day.  It says 'from time to time'.

the solutions probably break some other assumptions too... but never mind, heres my partial solution:

this solution may have already been proposed, i didn't read all the responses...

a leader is nominated. he starts his count at '0'.
switch A is the dummy switch, B is the key switch.

when the leader enters the room, if B is off he flips it and adds 1 to his count, else he flips A.

when a prisioner comes in and sees B on, he flips it off.  he does this twice during his life.  otherwise he will flip A.

so in the case the switches start off, the leader will eventually flip B on, and another prisioner will flip it off.  each prisioner does this twice, so the switch will be flipped off 44 times, and the leader will flip it on 23 times. 

If both switches are on, then the first time B is flipped is by a prisioner.  at this point the leader would come along and flip it on.  so in this case, each prisioner flips it off 44 times, and the leader flips it on 44 times.

so when the leader has flipped B on 44 times, its time to declare that all have moved through the room.

that sounds right to me?

Paul
Sunday, October 24, 2004

Well, it seems to me that there is a major point to this puzzle that everyone is ignoring.  The warden hasn't described the room at all.  Perhaps the prisoners would be allowed to ask the warden to describe the switch room to the prisoners, but since we cannot assume that that is so, there is only one definitive answer.  The only way the prisoners could be assured to not be fed to the gators is this: serve their full prison sentences.  Why?

Well, everyone is assuming that the two switches are next to each other and are basing their plans on this belief.  What if the two switches are one above the other?  What if ther're on opposite walls, and prisoners may be escorted into the room through any number of different doors?  The fact is...there is just not enough information supplied to justify making any plan except "Nobody ever tell the warden  that we've all been to the switch room, and we'll just stay here until our time is up."

Michael Kraack
Monday, October 25, 2004

*  Recent Topics

*  Fog Creek Home