Fog Creek Software
Discussion Board




switches puzzle

I have a question about the switches puzzle.  Are the men allowed to use dust on the switches, or leave objects like hair/nails in the switch room to communicate to each other, or are they only allowed to communicate through the switches?

Thank you! :)

eliza s
Thursday, June 10, 2004

I don't know the answer to this one, but I would guess that the answer is no.

I think the key is in the following sentence:
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else."

So the trick is to figure out when everyone has been to the room the same number of times, not necessarily the moment when the last prisoner takes his first trip to the room.

Brad corbin
Thursday, June 10, 2004

Thank you for your response. :)  I also doubted that the prisoners could communicate in a way other than through the switches... but this puzzle has been bothering me for days already! and I figured it wouldn't hurt to ask.

I think you're right about where the key of the puzzle lies... but how?  well, that's the question, isn't it? :)

eliza s
Friday, June 11, 2004

Okay.  I'd had it with the puzzle and went to look for the solution.  And I must say, it made me very frustrated! :D  I think that there should have been an additional sentence saying something like:
Assume that the warden will take the prisoners to the switch room as many times as is necessary for your solution.

I would post the solution, but since I didn't figure it out on my own, I won't... so I hope that additional sentence helps whomever is as frustrated as I was with this riddle. :o)

eliza s
Monday, June 14, 2004

Well I think this can be the answer:
I dont know i may be wrong but this is what i feel may work please any one reply if i am wrong.

They keep the code of "00" or "01" for a newperson visiting the switch room, and "10" or "11" for a person who is visiting a second time/ higher. When their leader examines that there are 23 new comings recorded he informs the warden that everyone have visited.

Chaitanya vahni
Thursday, June 17, 2004

Hi Chaitanya,

Nice try, but it is of course not the right answer.  Just think it out yourself, how could you create numercial representation like 00, 01, 10, 11 and so on with just 2 simple switches? Furthermore, each time you could (and must) only flick one switch. 

Lawrence Tan
Thursday, June 17, 2004

Given the assumptions that:-

A) There no restriction on the amount of time the prisoners could take before sending the notice to the warden that everyone has been to the switch room at least once.

B) There is no restriction the number of time each prisoner can visit the switch room

* Actually the 2 assumptions are very fair - if there is a time restriction or number of visit restriction, the warden could have just bring some prisoners there multiple times but never for certain prisoners and when the deadline is reached, all will be put to death.  Then this would a no-win situation for the prisoners from the start.

Solution:-

1. Appoint a score keeper.  The rest of the other 22 become simple "transmitters".

2.  When any transmitter enter the switch room, if he see the switch B is off, he flicks it on.  If he see switch B is already on, he flicks switch A once, regardless of which position switch A is at. 

3. Any transmistter should only switch B once (and only when he sees it in off position).  Once he has flicked it once, the rest of the time he will continue flicking switch A, regardless of its position.


3. The score keeper will be in charge of flicking switch B to the off position.  Each time he flicks switch B to off position he count off 1 to his total score.  But if he see switch B is already in off position, he flicks switch A too and do not add to his score. 

4.  This is repeated until the score keeper's score reaches 22.  At this point he informs the warden that everyone has been to the switch room at least once. 

Solved.

Lawrence Tan
Friday, June 18, 2004

I thought about this one all weekend and also thought of the strategy above but what about the initial state if the switches? Does the first prisoner to enter the switch room know that he is the first? What if the nominated score keeper enter's the room and switch B is already on? He will incorrectly count this as one prisoner having been in the switch room.

What other strategies are possible? Does the number 23 have any relevance?

Damian Kennedy
Sunday, June 20, 2004

I agree with Damian's assessment: the initial state of the switches is a problem.

The problem occurs if the "counter" is the VERY first one in the room. If switch B is already on, he will count it as 1, and as he counts up and reaches 22, only 21 of those are "real" tallies. He will announce prematurely, one person will still not have entered the room, and all prisoners will be executed.

Same problem occurs if another prisoner is first, and switch B is on. He will assume another prisoner set it, and will still switch it on during a later visit, resulting in an early announcement.

Just upping the count limit to 23 doesn't work either. If the switch starts in the OFF position, then the count will stay forever at 22, and an announcement will never be made.

Ugh.

Brad Corbin
Wednesday, June 23, 2004

Think this will work:
Have 1 leader and the rest are followers.

A follower must see B in both states before he can touch it. That is, he has to see it on once then encounter it off before he can touch it. After seeing it on and then finding it off, he can turn it on once  and only once.  If its already on, he flicks A and considers himself uncounted. After he has been counted, he only ever flicks A.

The leader is the only one who can ever turn B off.  The first time he comes in, if B is off, he must turn it on.  If he comes in for the first time (or the second), he must turn it off.

From them on, if he comes in and its on, he counts 1 and turns it off. If its not set we can do some sort of pattern where we assure the follower will get to see an on before the off where the leader will flick it but not count on the next 1.

We he gets to 22 he's done.

Mike McCracken
Wednesday, June 23, 2004

But what if a particular prisoner always follows the "leader" ? He will only ever see the switch in the "off" state (because the leader turns it off), and he never turns it on, and is never counted.

Brad Corbin
Thursday, June 24, 2004

That is what I meant by this comment:

From them on, if he comes in and its on, he counts 1 and turns it off. If its not set we can do some sort of pattern where we assure the follower will get to see an on before the off where the leader will flick it but not count on the next 1.

If point is not not just the gun and get killed while at some point being able to say without a doubt that everyone has been in.

Its not the most efficient algorithm but it will work.  It allows you to get to a know state and them allows the leader to drive from there and tally in a safe way.

Mike McCracken
Thursday, June 24, 2004

There are two solutions, but the simplest one is presented here.  It is the expansion of the "turn B on once" approach.  One prisoner is the counter, and every time they enter the room, they turn of the counting switch if it is on, and increase their internal counter by 1.  Every other prisoner can flip that switch *twice*.  When the count is at 2n, everyone has seen the switch at least once, and at least all but one have seen it twice.

Andy
Friday, June 25, 2004

This is a flaw in all the answers above - you all assume the "Leader" will visit the switch roon at least 23 times.  But there is no such garantee cause the guard choose the prisoners randomly, the chance of one of them is chosen 23 times can be very slim. Suppose one is chosen every day, before the "leader" is chosen 23 times, all of them would be dead of aging.  :-)

Steve Li
Tuesday, July 06, 2004

I don't think there is any other way around this, Steve. Practically speaking, you may be right. It could take years.

With 23 prisoners, and if the warden takes 1 per day, each prisoner will likely visit (even pessimistically) about once per month.

The first few times the "leader" visits, he will almost certainly have something to tally. He will only NOT have something to tally if the only people who visited the room since his last visit had already been tallied, which won't happen statistically often until we get down to only a few prisoners untallied.

I'd have to write a program to estimate it, but I would think this tallying would be complete inside 2 years average.

Brad Corbin
Friday, July 09, 2004

Note that the original question makes no mention of the frequency of how often these selections take place. I assumed once per day for convenience sake.

If we wanted to do some calculations of how long we might expect it to take, we'd have to measure it by "visits", whether they happened once per day or once per hour.

Brad Corbin
Friday, July 09, 2004

Well, here's the result of some programming 'speriments:

We already knew that a single leader counting to 22 or 23 would have problems based on the initial state of the switches.

The technique that works is having each prisoner turn switch A on TWICE when they see it off.

The leader should count up to 44, and then announce that everyone has visited the room.

This either amounts to 2 true visits by each prisoner (if switch A started in the off state) or 2 visits by 21 prisoners, 1 visit by 1 prisoner, and an extraneous tally if switch A started on.

Obviously, the leader knows he has visited the switch room.

In a little vb.net app, I've calculated the average number of visits each prisoner needs to make to reach this total.

The program saw numbers as low as 35 per prisoner (800 total visits) and as high as 65 per prisoner (over 1500 total visits).

So let's hope the warden chooses prisoners more often than once a day.

Brad Corbin
Friday, July 09, 2004

Nice one corbin, your one is the only solution ive seen so far that covers all assumptions correctly. Hopefully someone could find an even more efficient answer. 

Mohammed Saiyad
Wednesday, July 14, 2004

What if the leader is take to the Switch room 35 times before any other prisioner visits it and he is never taken in again?

least_random_number
Wednesday, July 21, 2004

Solutions is simple...

No need of tracking anything....Let the warden continue to take the prisoners to the room until one day one prisoner is called for the 4th time...and since the prisoner knows that he has already visited 3 times and since he is being called again means all other prisoners have also visited the room atleast 3 times.

Asha
Saturday, July 24, 2004

Asha-
If the warden chooses prisoners at random, it is possible, even LIKELY, that one prisoner could go to the room 4 times before another prisoner even goes once.

Brad Corbin
Wednesday, August 18, 2004

Just a small analysis on the numbers.
No. of switches = 2 i.e. total of 4 states 00, 01, 10, 11
fact(4) = 24 which is one less than the total number of prisoners.

Will this help in some way!!!

Abhinav

Abhinav Agarwal
Thursday, August 19, 2004

I think Asha is right....
The reason is hidden in this sentence..
"But, given enough time, everyone will eventually visit the switch room as many times as everyone else"
So, whosoever visits the switch room 622nd time and comes back should declare that all have visited the room.
(23)3.......

prasad
Thursday, August 26, 2004

I thought to try something different with this puzzle.
No speical char, or 'neo'  instead the prisioner remembers which pattren the switches are when he goes in.
OX  -> XX  -> XO -> OO
XO  -> OO -> OX -> XX
when someone goes in for the first time they move forward in the pattren.  When they go in a multiple time, they move back. The idea is that if at the end of the 'test' they all balance out equal due to randomness, then the prision just has to count times that he sees his orginal pattren.  This would be the 24th time someone has gone in.  I understand there could be problems, but with the times hopefuly it would balance out =)  or if not.... well im not a prisioner

Sour

Rem Boo
Sunday, August 29, 2004

er sry bout that, looks like i missed the important number which would be the 7th time, a person sees his pattren

Rem Boo
Sunday, August 29, 2004

I would like to extend this question:

- Only the prisoner(s) who can tell for SURE that ALL have visited the room is/are released.
- No prisoner can communicate with each other (released or not).

How can all 23 be freed? They need not all be freed at the same time.

Laval.
Monday, September 27, 2004

Each prisoner runs the next algorithm then:

counter = 1;
First time: 01->00
                00->01
                10->00
                11->01

Repeat:  10->11
                11->10
                01->11 counter ++
                00->10 counter ++

if  counter == 23
              tell 'We have all visited the switch room.'

katja
Monday, October 04, 2004

*  Recent Topics

*  Fog Creek Home