» MAKE: NOISE — Discuss this article

Showing messages 1 through 13 of 13.

• Simple improvement to the Tower solution
  You must be logged in to reply.
  
  
  Since each of the agents in the tower switch problem knows how much time has passed, you can adjust the rules of switch use to adjust for initial state issues.
  
  The initial conditions of A in the up position changes the first visitors behavior in the following ways:
  
  1. Counter - Ignores initial up value, switches A to down position
  2. Non-counter - Switches dummy switch (B) but counts initial up value as personal count increment. (i.e. will never switch A during sequence)
  
  The initial value can be cleared in the first visit with these modifications, and they don't have to be remembered beyond the first day. So the counter only has to see 22 increments, not 44.
  
  Another attempt to make this sequence shorter would defer the assignment of counter maiden to the witch, so the first maiden would assume the role of counter, by the selection at time=0, assuming the evil which was using a normal distribution, as others have mentioned. With the role selection deferred, the first maiden will know that the initial conditions are junk, as she was selected on the first trip, so she can adjust switch A's value if needed.
  
  If the witch can ever decide to send no maiden up, then this optimization wouldn't work, because no one would be selected as the counter maiden and the sequence would get to infinity (or maiden death) first.

  Posted by SkiesAbove on July 08, 2007 at 08:10:12 Pacific Time

• Seat Shuffle with algebra
  You must be logged in to reply.
  
  
  While I think induction is the rigorous proof, I originally attempted to use algebra with some interesting results. In each of the below cases, from left to right, each term between pluses represents the expected value if the crazy person chose seat "n".
  Case of 2:
  "Crazy chooses seat one 50% of the time causing a win, and seat two 50% of the time causing a loss" =
  (1/2) * 1 + (1/2)*0 = 1/2
  Case of 3:
  "Crazy chooses seat one 33% of the time causing a win, and seat two 33% of the time causing a subcase the same as the 'Case of 2', and seat three 33% of the time causing a loss.
  (1/3) * 1 + (1/3)((1/2) * 1 + (1/2) * 0) + (1/3) * 0 =
  1/3 + 1/6 = 1/2
  Case of 4:
  (1/4)*1 + (1/4)(Case of 3) + (1/4)(Case of 3) + (1/4) * 0 =
  1/4 + 1/8 + 1/8 + 0 = 1/2
  The pattern seemed to be
  Case of n:
  1/n + 1/(2n) + ... + 1/(2n) + 0 =
  There are (n-2) terms in the middle, thus:
  1/n + (n-2)*(1/(2n)) + 0 =
  1/n + (1/2 - 1/n) + 0 = 1/2
  
  Again, it doesn't feel as rigorous, but I always find it interesting how different approaches that are correct "just work" when it's math...
  

  Posted by oberman77 on June 20, 2007 at 05:22:21 Pacific Time

• Seat shuffle
  You must be logged in to reply.
  
  
  It took my brain a while to accept that 50% was the correct answer but it finally sunk in. However, I think the official answer could be put a little better and some of the people who just reverse engineered or monte carlo'ed to get the answer are missing the correct reasoning.
  
  Basically, there are two sets of probabilities to be concerned with. The probability that passenger 100 ultimately gets the correct seat, and the probability that a definitive decision is made in any iteration. The second has nothing to do with getting the right answer, but has to do with what seems intuitively correct.
  
  At every iteration (or, in other words, for every passenger who makes a decision) the chances of passenger 100 being forced into or out of his seat is 50% either way. The individual can choose the "correct" seat to get things back in sequential order thereby ensuring passenger 100 will get the correct seat, or they can choose passenger 100's seat, thereby ensuring passenger 100 will not get the correct seat. Anything else just sends the decision on to the next round.
  
  Prior to realizing that those are the only two relevant options per round it intuitively it seems like the probability of passenger 100 getting the correct seat should change based on some sort of combined probabilities. As you can see though, it doesn't. What does change is the likelihood that a definitive decision will be made that round.
  
  For example, during the first round the initial crazy man can sit in seat 1 (ensuring passenger 100 gets the correct seat) or in seat 100 (ensuring passenger 100 doesn't) and a definitive decision will be made. The chances of this happening are given as (number of determinant options)/(number of seats) or 2/100 or 2%.
  
  However when only 2 people remain there are 2 determinant options and 2 seats so the chances of a definitive decision being made at this point are 100%.
  
  Realizing this cleared things up for me, hopefully it does for others too.

  Posted by bryan_s on June 16, 2007 at 00:27:26 Pacific Time

• Switch or Miss
  You must be logged in to reply.
  
  
  Ok, I'm going to be "that guy" who complains about an error in the puzzle. It clearly says "You may choose which switch to toggle;...and I'm not telling you which position they are in to start with". Given this restriction the solution as proposed doesn't work since the maidens don't know before hand whether to flip the dummy switch (Switch B) or not.
  
  Please correct me if I'm wrong.

  Posted by bryan_s on June 15, 2007 at 20:56:56 Pacific Time

• Switch or Miss in depth
  You must be logged in to reply.
  
  
  This reminded me of a very similar puzzle I worked on awhile ago called 100 PRISONERS AND A LIGHT BULB:
  
  (differences: 100 people, one switch/light initially off, not forced to do anything)
  
  The forum board on that site lists many different approaches to solving it (including the "counter" solution given for this puzzle).

  Posted by oberman77 on June 13, 2007 at 08:03:21 Pacific Time

• Switch or miss
  You must be logged in to reply.
  
  
  Here's a solution which solves the problem. 100% accuracy and minimal visits to the tower.
  
  Maiden one: If the right lever is in the up position, lower it. Otherwise let it stay and move the left lever. Next time, if the left lever is in the same position, move the left lever. Repeat until left lever is in a different position from the last time. Once the left lever has shifted, maiden one knows someone else has been to the chamber. Maiden one now moves the right lever to the up position. Next time, if the right lever is in the up position, no maiden who has seen the right switch down has been to the chamber for the first time. Move the right lever down. If the right lever is down, at least one other maiden has been to the chamber for the first time. Move the left lever and repeat the previous steps of checking for a change in the left lever's position. Once the left lever has shifted, at least one other maiden has been to the chamber. (Herein would lie a bug, if the first maiden didn't lower the right lever whenever she sees it. If the same two maidens repeatedly visit the chamber in the beginning, we have a stalemate. The other maidens would never see the right lever in the down position.) Shift the right lever to the up position. Wait for it to come down. Once it's come down, a second maiden has been to the chamber. Repeat. Once the right lever has been shifted down 22 times, all maidens have been to the chamber.
  
  Maidens 2-23: If the right lever is up, move the left lever. If the right lever is down, next time we come to the chamber, and the right lever is up, shift the right lever down. If one comes to the chamber after having shifted the right lever down previously, keep shifting the left lever. The rule is that maidens 2 though 23 all shift the right lever only once, and only after they have seen the right lever down. Only the first maiden shifts the right lever up, so once this has occurred, they can be sure that the first maiden has been to the chamber after their last visit.
  
  The problem we have is that the other maidens must be assured that maiden one has been to the chamber. This is done by seeing the right lever in the lower position, and then in the up position. Since only maiden one shifts the right lever up, if it's been down and is now up, maiden one has been to the chamber.
  
  The problem arises when two maidens, one of whom is maiden one, visit the chamber repeatedly. Maiden one shifts the right lever down, waits for maiden two to visit, and then shifts the right lever up. Maiden two has seen the right lever down, and shifts it down from the up position. Maiden one now waits for the left lever to be in a different position from the last time. This happens the next time maiden two visits the chamber. Maiden one now thinks someone else has been to the chamber and shifts the right lever up. Next, maiden three comes in and seeing that the lever is up, shifts the left lever (only maiden two has seen the right lever down). No matter how many times anyone comes to the chamber, none of the maidens shifts the right lever down, since they never see the lever down.
  
  The solution is to have maiden one shift the right lever down if she sees it still in the up position. Now the next maiden will see it is down. If the right lever is still in the up position when maiden one comes in, she knows she was herself the one to shift it up, and that there has been no maiden who has both seen the right lever down and has visited the chamber for the first time.
  
  I wrote a java program which demostrates the actions of the maidens in java. It is probably easier to understand than the above explanation. At least I wrote it with more care.
  
  It's available at http://www.plug.fi/23maidens/Witch.java.txt

  Posted by troyzki on June 06, 2007 at 07:17:53 Pacific Time

• Switch or Miss
  You must be logged in to reply.
  
  
  It seems to me that in the proposed solution the counter maiden is really only counting the number of times a maiden other than herself has visited the tower (not the number of maidens that have visited the tower), and so in some cases can incorrectly believe that everyone has visited the tower when some maidens haven't.
  
  To see the issue, give each maiden a unique number, from 0 to 23, and make maiden number 23 the counter. Then choose the following 'random' sequence of maidens: number 0, number 23, 0, 23, 0, 23, and so on, repeating forever. The counter maiden, number 23, will eventually incorrectly say that all maidens have visited, when in reality only she and maiden zero have visited. This sequence 0, 23, 0, 23... is possible because the choice of maiden at any time is random - that is, any sequence is possible.
  
  In formal terms, the suggested solution will incorrectly accept some sequences not in the language of 'the sequence contains every maiden at least once'. In particular, it incorrectly accepts '0, 23, 0, 23, ....'
  

  Posted by Needhamia on June 03, 2007 at 16:57:31 Pacific Time

• Seat simplicity
  You must be logged in to reply.
  
  
  I think kds_ats has it exactly right.
  
  You can analyze and parse this until your math turns red, but there's no getting around the fact that when #100 gets on the plane, either his seat is taken, or it isn't. Does it really make a difference how that situation arose?

  Posted by j_mack on May 30, 2007 at 09:06:12 Pacific Time

• seat shuffle induction
  You must be logged in to reply.
  
  
  Here's how I would explain the induction.
  
  Start by thinking of it as a game that is over as soon as someone sits in the 100th seat. Call that loosing. The probability of winning is 1 - P(loosing). Where winning means the 100th passenger sits in their seat.
  
  The probability of loosing a 2 person game is 1/2.
  
  The probability of loosing a 3 person game on the first turn is 1/3. The chances of having a second turn are 1/3 and you are now playing a 2 person game with a probability of loosing of 1/2. So, probability of loosing a 3 person game is 1/3 + 1/3 * 1/2 = 1/2.
  
  For a 4 person game it's:
  1st turn = 1/4
  2nd turn = 1/4 * P(3 person game)
  3rd turn = 1/4 * P(2 person game)
  
  Now you can see the induction. For a 100 person game you have a chance to loose on the 1st turn and then 98 more times.
  So, it's 1/100 + 98 * 1/100 * 1/2.
  
  It's 98 and not 99, because you never loose a 1 person game, i.e. if you haven't lost up until the very last turn, you win.
  
  

  Posted by KenKnowles on May 26, 2007 at 05:23:46 Pacific Time

• clarification- switch or miss
  You must be logged in to reply.
  
  
  I'm puzzled by the explanation... if the witch selects maidens at random (from their cells) how can a maiden act as the counter... if she may only be selected to visit the tower once, or any number of times? It is probably obvious, but I'm lost.

  Posted by zwild1 on May 23, 2007 at 22:19:25 Pacific Time

• seat shuffle summation?
  You must be logged in to reply.
  
  
  I'm sorry, my applied math is a little rusty, but this is the summation I was able to reduce the problem to, and I'm not certain that it sums to 1/2.
  
  (1/100)(1+(1/2))+(1/100)sum_n=3to99[(1/n)Y_sub_n]
  
  where,
  Y_sub_n = (1/(n-1))(Y_sub_n-1 + Y_sub_n-2 + ... + Y_sub_3)
  and
  Y_sub_3 = 1+(1/2)
  Y_sub_4 = (1/3)Y_sub_3
  
  
  Am I the only one who came up with this? Am I smoking crack? The published solution looks elegant, but it doesn't feel very convincing to me.

  Posted by milesvp on May 21, 2007 at 11:23:30 Pacific Time

• Seat Shuffle:Easier Solution?
  You must be logged in to reply.
  
  
  Since the aha question asked what the probability is that the 100th passenger could sit in seat 100(their assigned seat), either there is a person there or not, so the probability is 50%. No induction needed, I think...

  Posted by kds_ats on May 18, 2007 at 18:08:29 Pacific Time

• switch orr miss: alternate solution?
  You must be logged in to reply.
  
  
  Couldn't one of the maidens other than the counter be instructed to flip switch A twice and the counter only count to 23?
  
  Just trying to save time.

  Posted by neilium on May 18, 2007 at 06:35:28 Pacific Time