Solution to swithches puzzle Note that the bulbs are labelled so consier this ... take 0 for 'off' and 1 for 'on' and then form a table which looks like a binary table for all possible values for 'two bits'..           A    B    Value         ----------------------             0    0      0             0    1      1             1    0      2             1    1      3 The following conditions were decided by the three prisoners : 1)They labeled themselves as 1,2 and 3 .... corresponding     to the above possible combinations of the bulbs. 2)The declaration that all have visited the switch room will     made by Number 3 3)All have taken note their "signatures" as per the above      table.The prisoner 1 for example will leave  "0 1" as his   signature (on the condition that the available situation of   the switches is "0 0" or "1  1"). 4)Number 2 will leave his signature only when he is sure     that Number 1 has visited...ie Number 2 sees the      signature of Number 1 and remembers...     Now suppose that Number1 has made his signature     "0 1" and Number 2 then sees it......so he cannot write     his signature now..as he is allowed to only switch one     bulb at a time..so he makes a mental note of the fact     that number1 had visited and then Number2 puts the     bulbs in  "0 0" situation.After that when ever Number2     gets a chance(when "0 0" or "1 1" is available)     to write his signature he will do it promptly. 5)Everybody will write his own signature or "0 0"( if he    cannot write his signature) 6)Nubmer 2 will write his signature only when he is sure   that Number 1 had written his signature(irrespective of   the fact that Number 1 had visited immediately before   or sometime before) and also when he gets an   opportunity to do so ( ie the situation is "0 0" or "1 1")   otherwise he will revert to "0 0"... the default one! for   everybody. 7)Number 3 will write his signature only when he is sure   that Number 2 had written his signature....   and Number 2 took care of Number 1's signature   so Number 3 needs to be only on the look out for   Number 2's signature.This ensures everybody made it   into the switching room.Then Number 3 declares.... Take any combination for a start and use the following rules: 1)Prisoner will try to write his signature 2)If he cannot he will try to put "0 0" One case the combination "1 1" is given and Number 3 walks in for the first time.. he cannot put "0 0" but he wont even put "0 1" as that would give an impression of Number 1 having walked in .. so he will put "1 0" Each prisoner knows whether they have put their own sign or not so if the encounter thier own sign which they have not put.....Number1 and Number2 will leave "0 0" as the switches position and Number3 when encounters "1 1" will leave "1 0" One needs to recognize the others sign only: ie Number 2 will only need to recognize "0 1" in order to put his own "1 0" signature (then or in the near future thats it!!) and Number 3 will only need to recognize "1 0" in order to put his own "1 1" sign(he doesnt need to observe for "0 1" at all!! Number 1 is free to put his sign whenver he gets a chance.... he need not observe anything....... Hope i m right :) sorabh sorabh saxena Sunday, June 08, 2003 Hi ! I like your approach . However I think it's wrong. In your algorithm, suppose number 3 eventually finds out that number 2 has put his signature, but how number 3 can know that this is  number 2 from his group, or at least that all number 2's already visited the room. And how number 3, who is going to declare that everybody has visited the room, can know that all other number 3's visited the room? Gans Sunday, June 08, 2003 Is there a misprint in the puzzle statement? It says "23" prisoners -- should it actually have said "3"? If 3,  my proposed solution is: Prisoner 1 takes the switch on the left. Prisoner 2 and 3 take the switch on the right. Both 2 and 3 remember the position of the switches. If, when either of them visits the room, both switches are in different positions from their last visit, they declare. Of course, if the warden knows the algorithm, he can keep them there indefinitely... William Wednesday, June 11, 2003 there is no mistake, i think the number 23 is there to confuse us. any solution should work for 50 or even 100 prisoners as well. i'm not going to give any hints, but if you want a solution, google should be able to find one for you. i solved it (almost right) after a while, and it required no thinking outside of the box (aha!). good luck! rx4ever Saturday, June 14, 2003 The puzzle does not state *how* the switch must be mounted on the wall. It mentions moving the switch. Switch A will indicate whether the first 12 prisoners have come through or not. Switch B acts as an hour hand abd tally. Since there are 23 positions. Use one switch for AM/PM. The first 12 prisoners use the AM switch as ON. Now as each prisoner comes into the room and move the switch "one hour". He flips the B switch only to statisy the warden. When the 12th prisoner comes into the room, he switches the first switch OFF to indicate that 12 prisoners have already been though and move the B switch to the "noon position".  Then the rest of the prisoners come in until the last. If he's been in the room before,  he simply swiches B on or off to statisfy the warden. Prisoner will know he's last when Switch A is OFF and Switch B is tipped to the 11o'clock position. -V vrkelley Monday, June 16, 2003 um, except they are normal lightswitches so you can only flip them 'on' and 'off', not to 11 o'clock. Michael H. Pryor Wednesday, June 18, 2003 This was a toughie. Took me a day.  The solution is to have a leader among the prisoners who will declare when everybody has visited the switch-room. At the allowed meeting between prisoners, they decide on the leader and also decide on a "special switch", which will be used to communicate between the leader and the rest of the prisoners. Lets take it to be A. To denote switch positions, I will use 0 and 1 to denote any one of "on" or "off" positions. Lets assume that A is 0 initially. I will deal with the problem arising out of this assumption later. If the leader comes in and sees A as 0 he does nothing, he simply flips B. When a prisoner comes in and if the value of A is 0 and if he has never flipped A before, he flips A to a 1 and afterwards everytime he comes in he flips B. The value of B is irrelevant. When a leader comes in and notices that A became 1, he realizes that someone new has come into the room, so increments the count of prisoners who visited the room by one and flips it back to 0. Thus, if we can guarantee that A is initially 0, when the leader notices A becoming 1, 22 times, he can guarantee that everybody has visited the switch-room. But since we cannot guarantee this,so we would need to change the strategy little.  Instead of having the prisoner flip A only if he has not flipped it before, we will let him flip A to a 1, two times i.e if a prisoner has already flipped A to a 1 on a previous visit, we will let him flip it once more on a subsequent visit. If the leader observes A as 1, 43 times, he cannot yet say if everyone has visited because A could be initially 1 and 21 prisoners could have visited twice. But  if there are 44 flips, we can guarantee that everybody has visited the cell atleast once. Alex Czarian Thursday, June 19, 2003   A similar solution to the one given above by Alex, is: Let there be a secret code "0 0" for example. Now, Every prisoner will make the position of the switches as "0 0" only once!....so the moment any prisoner sees the  secret code "0 0", 22 times , he would be 100% sure that all the others have visited the room. The number of prisoners does not matter, it can be 2000 also and the key value would be 1999. Rahul Sachdev Friday, June 20, 2003 Based on the solution given, I feel the wording of the puzzle was confusing. The warden only guaranteed that each prisoner would eventually visit the switch room the same amount of times, it did not say he would continue choosing prisoners indefinately untiil one declared they had all visited. The solution implies that each prisoner would have to visit the room 22 times.  However, from the wording I thought that each may visit the room 1 time or 6 times or whatever the warden chose not thinking there was no upper limit. Jeffrey Smith Tuesday, June 24, 2003 Has anyone actually heard of this puzzle being used in a real interview?  Seems a bit tough for a simple hour-long interview if they're also going to hit you with coding questions. TwinPapa Monday, July 07, 2003 The solution to the Switches Puzzle i think is Initially all the prisoners decide if they visit the "Swiches room" for the first time they will alternate between 00 and 01 If they visit swiches room for the second or more times they will alternate between 10 and 11 So if the prisoner visits the room 3rd time(or more) and sees some one has put the combination as (10 or 11) he will declare that everyone has visited the room once. becuase of the clause " But, given enough time, everyone will eventually visit the switch room as many times as everyone else. " I think this solution is rite.IF some one thinks its not lemme know THE RIDDLER Monday, July 14, 2003 Riddler, you are wrong: remember that in the problem it says: "I may choose the same guy three times in a row" According to you, the first time he will flip to 01 or 00, second time to 10 or 11, and the third time he'll see 10 or 11 and go declare to warden.  While it may have only been 1st, second and third visits. I think the solution is posted above - each guy will leave the code (say 00) exactly once, and whoever counts 22 of the code declares. Jeff P Friday, July 18, 2003 Actually, I think that Alex's second answer is correct;  Leader waits to see A at 1 44 times. Rahul's secret code won't work, because no one prisoner is likely to see all of the other secret codes. Prisoner 1: leaves code Prisoner 2: sees code, but has no choice but to change it Prisoner 3: leaves code, but will never know about the first one, so he'll never see 22 codes... Allan Schon Tuesday, July 22, 2003 On entering the switch room each prisoner will do the following: Note the current position of the switches A & B, on or off. They then move one switch to denote either their first or second visit using the folowing table: o - denotes switch position  off 1 - denotes switch position  on 0, 0 - New 0, 1 - New 1, 0 - Second visit 1, 1 - Second Visit Note you can set the switches to either new or second entrant using the above table no matter what the current state. Each prisoner will then simply tally the number of new entrants as and when they make a visit to the switch room. When a total of 22 or n-1 is reached, the prisoner will know that all have visited the switchroom. n being total number of prisoners. Since all prisoners keep their own tally there is no need for a single leader (he might escape in the meantime). Just hope they can all count or else its crocodile time! Stuart Stuart Saturday, July 26, 2003 I think my solution above is incorrect (how sad is that, I'm still thinking about it!). However I believe the following adaption will work. A single prisoner will be required to count the number of new entrants using the code below: Right switch. 0- indicates new to visit 1- already visited Left switch position not important. Each time a prisoner visits for the first time and the right switch is in position 1, they must move it to 0 to indicate a new visit. The counter on their next visit will add this to the tally and then move the right switch to position 1. If already in position 1 they will alternate the position of left switch. If a prisoner enters on their first visit and right switch is already in position 0, they must alternate the position of the left switch. Every prisoner must continue to enter the switchroom as if it were their first visit following the rules above until such time that they able to move the right switch from position 1 to 0 indicating their first countable visit. When the prisoner counting reaches a value of n-1 (n being total number of prisoners) they will know that all prisoners have visited the switch room. Stuart Thursday, July 31, 2003 This was a good one with pretty interesting solutions. But Alex's solution posted on June 19th is the right one. If I was forced to select between the alligators and Alex's solution it wouldnt be tough for me to select would it? :) Hadi Mohammed Thursday, August 07, 2003 Alex's solution posted on June 19th is a good attempt but if the number of prisoners = 23 and say the prisoners each vist the switchroom only 4 times then this solution will not work. Some one else has already posted this issue. I propose that each prisoner leave their left shoe.  When there are 23 left shoes any prisoner may make the declaration. John Tuesday, August 26, 2003 What if they don't wear shoes? After all they are being threatenend with being fed to alligators. What's to stop the Warden from commiting other Human Rights Violations? Brian Wednesday, August 27, 2003 I think Alex's solution is correct. I came up with the solution where the leader counts 22 new ones, but I realized after reading his solution that I was wrong, since the first count could be due to the initial position of the switch. Therefore, to count twice would eliminate that possibility. Good job Alex ! Anurag Jain Wednesday, August 27, 2003   Fog Creek Home