» MAKE: NOISE — Discuss this article

Showing messages 1 through 40 of 40.

• 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.
  
  
  Simple, Tell all the maidens to make a tally mark next to a switch. and only on the first time they visited. As soon as a maiden counts 22 marks they can all go. Sure this is cheating (i prefer hack) but she is an evil witch.
  
  On second thought there are 23 of them and only one of her. they ought to blitz her, end of witch.

  Posted by ActionJackson on June 07, 2007 at 01:03:16 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

• Switch or Miss
  You must be logged in to reply.
  
  
  The solution assumes that the counter maiden, after 23 trips herself, that the random selection of the other maidens has insured they have had at least one trip to the tower each. Why is this a valid assumption ? Likely yes. High probability - yes. But not certain. This seems a cheat to get to the "100% certainty" the puzzle asked for.
  
  Said another way, the Witch is evil, obviously, so she selects at random, but does not select one maiden ever. You never get all maidens to visit the tower, and they are forced to stay in the dungeon, because, well, she is evil.
  
  That was her plan all along - false hope.
  

  Posted by AddisonGrimes on June 04, 2007 at 06:25:08 Pacific Time

• Switch or Miss
  You must be logged in to reply.
  
  
  The solution assumes that the counter maiden, after 23 trips herself, that the random selection of the other maidens has insured they have had at least one trip to the tower each. Why is this a valid assumption ? Likely yes. High probability - yes. But not certain. This seems a cheat to get to the "100% certainty" the puzzle asked for.
  
  Said another way, the Witch is evil, obviously, so she selects at random, but does not select one maiden ever. You never get all maidens to visit the tower, and they are forced to stay in the dungeon, because, well, she is evil.
  
  That was her plan all along - false hope.
  

  Posted by AddisonGrimes on June 04, 2007 at 06:25:30 Pacific Time

• Switch or Miss
  You must be logged in to reply.
  
  
  The solution assumes that the counter maiden, after 23 trips herself, that the random selection of the other maidens has insured they have had at least one trip to the tower each. Why is this a valid assumption ? Likely yes. High probability - yes. But not certain. This seems a cheat to get to the "100% certainty" the puzzle asked for.
  
  Said another way, the Witch is evil, obviously, so she selects at random, but does not select one maiden ever. You never get all maidens to visit the tower, and they are forced to stay in the dungeon, because, well, she is evil.
  
  That was her plan all along - false hope.
  

  Posted by AddisonGrimes on June 04, 2007 at 06:24:47 Pacific Time

• Switch or Miss
  You must be logged in to reply.
  
  
  From the solution:
  "On any subsequent trips they can just toggle the B switch so they are not counted twice."
  
  The 0 maiden would only signal her presence when she hadn't been counted yet, so she wouldn't get double counted by the counter.

  Posted by MichaelPryor on June 03, 2007 at 20:05:13 Pacific Time

• Switch or Miss
  You must be logged in to reply.
  
  
  If each maiden only toggles the switch if she hasn't been in the tower before, it seems to me the counter maiden has the problem of distinguishing the following 3 sub-sequences of visits with only 2 states of the switches:
  
  1) ..., counter, maiden-who-hasn't-visited-before, counter
  
  2) ..., counter, maiden-who-has-visited-before, counter
  
  3) ...counter, counter (that is, the counter maiden was chosen twice in a row)
  
  For example, if a maiden throws the A switch only if she hasn't been in the tower before, the cases fall out this way:
  
  1) counter puts A Down, maiden who hasn't visited before puts it Up, counter sees the A switch Up.
  
  2) counter puts A Down, maiden who has visited before leaves the switch alone, counter sees the A switch Down.
  
  3) (the failure) counter puts A Down, counter immediately visits the tower again and sees the A switch is Down - is she to conclude that she is in case number 2, or instead that she's in case number 3?
  

  Posted by Needhamia on June 04, 2007 at 08:33:54 Pacific Time

• Switch or Miss
  You must be logged in to reply.
  
  
  Now that I've thought about it a bit longer, I see how the described solution does fit the problem description.
  
  Putting the problem description in a formal form: Given all possible sequences, of any length, of maidens chosen at random, there is at least one sequence which will end with the last-chosen maiden correctly saying 'we've all been here at least once', and there is no sequence which will end with the last-chosen maiden incorrectly saying 'we've all been here at least once'.
  
  In other words, there needs to be only one sequence where the counter-maiden correctly says 'we've all been here'. It doesn't matter that there may be sequences that contain all the maidens, yet don't cause the counter-maiden to say they've all been there - that's just bad luck for the maidens.
  

  Posted by Needhamia on June 04, 2007 at 09:11:59 Pacific Time

• Switch or Miss
  You must be logged in to reply.
  
  
  The counter only puts A down if when she visits, it happens to be up. And then she counts that as +1 maiden.
  
  If it's already down then she doesn't do anything... she just flips the b switch and doesn't count it as anything.

  Posted by MichaelPryor on June 04, 2007 at 08:39:05 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 simplicity
  You must be logged in to reply.
  
  
  The flaw in this logic is that it does matter how you get to that last choice.
  
  Consider a slightly different game where passengers board in order 1 to 100, but everybody always picks a random seat. You can apply the same logic to this totally different game. When the last passenger boards, either there's someone in seat 100 or not. But the answer 1/2 is wrong in this case. The probability is actually 1/100.
  
  In order for the last person to get seat 100 everybody before them has to not choose that seat. So, the answer is 99/100 * 98/99 * 97/98 * 96/97 * ... * 3/4 * 2/3 * 1/2. You can easily see that everything cancels out except 1/100.
  

  Posted by KenKnowles on May 31, 2007 at 10:17:23 Pacific Time

• Seat simplicity
  You must be logged in to reply.
  
  
  Ken,
  Your change to the game does, in fact, make the probability completely different. In this puzzle, the passengers don't automatically make a random choice (and that makes all the difference)
  The flaw in your argument is that the game isn't just the probability that someone will sit in seat 100, it's the probability that someone will sit in seat 100 *before* someone sits in seat 1. Once someone has sat in seat 1, all of the remaining passengers will be able to sit in their assigned seats. The probability calculation needs to include the probability of someone sitting in seat one.
  The exact calculation isn't:<br/>
  (99/100)*(98/99)*(97/98)...(1/2) = 1/100<br/>
  it's:<br/>
  (1/100+98/100*(1/99+97/99*(...(1/4+2/4*(1/3+1/3*(1/2)))...)))<br/>
  which simplifies the sum of<br/>
  99/9900 + 98/9900 + ... + 1/9900 = 1/2<br/>
  Cheers, Gregory
  
  
  

  Posted by gtf13 on July 26, 2007 at 23:32:38 Pacific Time

• Seat simplicity
  You must be logged in to reply.
  
  
  So far that's two scenarios that change the original conditions, and use the changed conditions to make an argument about the original puzzle.
  
  I clarified elsewhere that my thesis ('doesn't make a difference how the situation arose') applies only to the puzzle as stated. If you want to refute it, give a counter-example that uses the original conditions, not some variation. Under the rules as given, what could happen that would NOT make this a 50:50 proposition?
  
  In another reply, a poster shows more rigorously that, given those conditions, this always reduces to the situation where there are two passengers and two seats... that's why the answer is what it is. Given that, I don't see a lot of wiggle room (and these are airline seats, after all) (-:

  Posted by j_mack on May 31, 2007 at 17:37:16 Pacific Time

• Seat simplicity
  You must be logged in to reply.
  
  
  Yeah, what Ken said :)

  Posted by MichaelPryor on May 31, 2007 at 10:53:05 Pacific Time

• Seat simplicity
  You must be logged in to reply.
  
  
  The problem with this line of thinking is you could very well say the same thing about the chances of rolling a 1 on a six sided die. "You either roll a 1 or you don't, so the chances are 50/50", but we know that's not the case. Your chances are 1/6.
  
  Since 50/50 is the actual correct answer in this case, it's hard to show how this logic is flawed in this particular case, but imagine that I was a flight attendant on the plane and I was working to corrupt the chances and so immediately before the last guy got on the plane I would always make sure his seat was empty (by moving someone from somewhere if I had to). Does that help to show why that argument isn't strong enough to come to the correct answer (even though it happens to)?

  Posted by MichaelPryor on May 30, 2007 at 09:17:59 Pacific Time

• Seat simplicity
  You must be logged in to reply.
  
  
  Your dice objection would be valid if we were talking about any given passenger, at any point in the boarding sequence.
  
  Instead, all the previous is just prologue. The circumstance at hand is that there is one empty seat, and one passenger. How that came to be is irrelevant.
  
  That the answer is the same for 2, 3, 100 and 1000 passengers does seem to imply that the logic isn't faulty at all.
  
  Or maybe I'm just lucky (-:

  Posted by j_mack on May 30, 2007 at 12:41:05 Pacific Time

• Seat simplicity
  You must be logged in to reply.
  
  
  You wrote: "How that came to be is irrelevant."
  
  This is where it breaks down because that statement is not true. How it came to be is incredibly relevant. For example, as I laid out above, I could have the flight attendant always make sure the empty seat is your seat by rearranging passengers. Then at the end there is one seat, one passenger, but the chances of his seat being empty are 100%.

  Posted by MichaelPryor on May 30, 2007 at 12:43:45 Pacific Time

• Seat simplicity
  You must be logged in to reply.
  
  
  You wrote: "How that came to be is irrelevant."
  
  Yes, and I should have qualified that. There were conditions given that set this up. Within those constraints, it makes no difference how the seat came to be empty, i.e. how many random choices went into creating the condition that exists when #100 gets on the plane.
  
  What you're postulating is another case altogether, which doesn't follow the original premise. And in fact, the other (correct) analyses given here would also fail to get your answer, because your new problem isn't the same one that they were analysing.
  
  So yes, you clearly can construct a different problem that my response doesn't apply to.
  
  

  Posted by j_mack on May 30, 2007 at 14:20:58 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

• seat shuffle induction
  You must be logged in to reply.
  
  
  "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."
  
  This is not correct. There is a 2/3 chance of moving on from the first round not a 1/3 chance.

  Posted by cameronzilla on June 01, 2007 at 22:46:43 Pacific Time

• seat shuffle induction
  You must be logged in to reply.
  
  
  "This is not correct. There is a 2/3 chance of moving on from the first round not a 1/3 chance."
  
  In my solution, I'm adding up the chances of loosing. There's a 1/3 chance of winning on the first round; person 1 picks seat 1. Only if person 1 picks seat 2 will there be another round with a chance of loosing.
  

  Posted by KenKnowles on June 03, 2007 at 15:14:06 Pacific Time

• seat shuffle induction
  You must be logged in to reply.
  
  
  Ok, I'm finally convinced the answer is 1/2, and that the induction argument can be made to work (somehow).
  
  My combinatorics maths aren't what I'd like them to be, but I can see a definite pattern, and I can almost see how to make the pattern inductive.
  
  I tried out all the possible combinations of outcomes up to 5 players and came up with half wins and half loses. I post 3&4 players here, for anyone else needing convincing.
  
  ######Here's 3 players
  1 = picks seat 3
  2 = picks seat 2 #lose
  
  1 = picks seat 2
  2 = picks seat 3 #lose
  
  1 = picks seat 2
  2 = picks seat 1 #win
  
  1 = picks seat 1
  2 = picks seat 2 #win
  
  As you can see, there are 4 possible combinations with 2 winning combinations. So there is a 2/4 chance of winning(assuming a flat distribution).
  
  ######Here's 4 players
  1 = seat 4
  2 = seat 2
  3 = seat 3 # lose
  
  1 = seat 3
  2 = seat 2
  3 = seat 4 # lose
  
  1 = seat 3
  2 = seat 2
  3 = seat 1 # win
  
  1 = seat 2
  2 = seat 4
  3 = seat 3 # lose
  
  1 = seat 2
  2 = seat 1
  3 = seat 3 # win
  
  1 = seat 2
  2 = seat 3
  3 = seat 1 # win
  
  1 = seat 2
  2 = seat 3
  3 = seat 4 # lose
  
  1 = seat 1
  2 = seat 2
  3 = seat 3 # win
  

  Posted by milesvp on June 03, 2007 at 06:21:35 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

• clarification- switch or miss
  You must be logged in to reply.
  
  
  The question implies, that each time the witch goes to pick a girl, that each of the 23 girls will be picked with some probability P, where P > 0. That is to say, each girl has a chance to be picked each and every time the witch picks.
  
  This means, that eventually, given the life of the universe, each girl will visit the tower at least once, and that the counter girl will visit the tower enough times to see the switch in the up position 22 times.

  Posted by milesvp on May 24, 2007 at 15:17:07 Pacific Time

• clarification- switch or miss
  You must be logged in to reply.
  
  
  I think it's clear that this problem was ill-conceived. The puzzle as written certainly has no solution, even if we adopt a simplistic notion of what "random" means.
  
  Suppose the problem specified that each day's choice of maiden were independent, and that each maiden was equally likely to be chosen (probably what the author meant). Then one still could not say that the maidens could have "100% certainty," because there would be no upper bound on how long they would have to wait to get their result.

  Posted by Akrmac on May 25, 2007 at 21:28:47 Pacific Time

• clarification- switch or miss
  You must be logged in to reply.
  
  
  Nope!
  
  The question is well "conceived". The program I wrote that implements the solution terminates always. It takes between 650 to 900 (!) visits.

  Posted by arouse on May 26, 2007 at 18:25:09 Pacific Time

• clarification- switch or miss
  You must be logged in to reply.
  
  
  Great, I seem to be getting the same results with my little simulation of the problem, (avarage number of iterations is about 900)
  
  I actually would have thought the number would have been larger. In any case I will try to get around to running the simulation over a larger number of trials to see what I get for an actual avarage number required for the madens to get out of the tower.

  Posted by monte_carlo on May 30, 2007 at 21:29:09 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

• Seat Shuffle:Easier Solution?
  You must be logged in to reply.
  
  
  No, because even if there are only two possible outcomes, the odds for either outcome are not necessarily 50%. Consider, for example, a six-sided die with one face bearing "1" and the other five faces bearing "2". The odds that you'll roll a "2" are not 50%.
  
  For what it's worth, I went and calculated the first three cases and got the 50%. Since I guessed that that was a likely outcome (tricky questions like this often have simple answers once all the cases are worked out) I was satisfied that if I got the same answers for 2, 3, and 4 seats that the rest would be the same.

  Posted by CyberSmythe on May 19, 2007 at 21:59:37 Pacific Time

• Seat Shuffle:Easier Solution?
  You must be logged in to reply.
  
  
  No, because even if there are only two possible outcomes, the odds for either outcome are not necessarily 50%. Consider, for example, a six-sided die with one face bearing "1" and the other five faces bearing "2". The odds that you'll roll a "2" are not 50%.
  
  For what it's worth, I went and calculated the first three cases and got the 50%. Since I guessed that that was a likely outcome (tricky questions like this often have simple answers once all the cases are worked out) I was satisfied that if I got the same answers for 2, 3, and 4 seats that the rest would be the same.

  Posted by CyberSmythe on May 19, 2007 at 21:59:24 Pacific Time

• Seat Shuffle:Easier Solution?
  You must be logged in to reply.
  
  
  Yes, I too worked through a few cases where N=2, 3,4.. and sort of saw how the probablility remains the same for all N.
  
  Then I wrote a simple simulation that used this process:
  ---------------------------------------
  NB. Make a 1D array with 100 elements = 1 (for free seats)
  seats =: total_number_seats # 1
  
  NB. the crazy passenger takes a seat, sets the randomly chosen seat to 0
  seats =: randomly_find_free_seat_in seats
  
  NB. Iterate over the remainging 99 passengers
  passenger =. 1
  
  while. (passenger less_than total_number_seats - 1) do.
  if. (passenger has_a_seat_in seats) do.
  seats =: passenger sit_in seats
  else.
  seats =: randomly_find_free_seat_in seats
  
  end.
  passenger =. next passenger
  end.
  
  check_last_in seats
  -------------------------------------
  running 10,000 trials, I found that passenger 100 got the seat 48.95% of the time.

  Posted by monte_carlo on May 27, 2007 at 15:04:27 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

• switch orr miss: alternate solution?
  You must be logged in to reply.
  
  
  Unfortunately, I think the author's solution is the fastest. In the case you proposed (one maiden is instructed to flip the switch twice and the counter only count to 23) there is a problem.
  
  Here is the problem scenario: the switch is initially in the up position (so the couter counts +1 erroneously). Next, 21 of the maidens visit (leaving one that hasn't gone).. however, one of the 21 was the maiden who switches twice. That would add 22 to her count of 1, giving 23. She would be wrong to say everyone had visited at this point.

  Posted by Derekagreene on June 08, 2007 at 08:38:44 Pacific Time