Talk:Puzzles

From XKCD Wiki

[edit] Good Books?

Would it be worth having a section in the article on what books are good for such puzzles? For example, I like "aha! Insight" (ISBN: 0-7167-1017-X) and "aha! Gotcha" (ISBN: 0-7167-1361-6) by Martin Gardner, which are both great books with cool cartoons that talk out these problems.

Another excellent book is "What is the title of this book?" by Smullyan.

69.140.141.187 16:12, 18 February 2009 (UTC)

[edit] Merging duplicates

Some puzzles are equivalent (like "Two Beagles" and "Two Dice" or "Ball and Balance" and "16 cubes". Maybe the should be merged. --Derari 18:56, 20 July 2009 (UTC)

[edit] One more probability puzzle

I think this is the solution of the problem. Assuming Card(S) the cardinality of a set named S, we can say that the probability that A is a subset of B is

[Card(B) / N] * [Card(B) - 1/ N - 1] * ... * [ Card(B) - Card(A) / N - Card(A) ]

Are we supposed to pick A and B randomly from the subsets of X? If so, it's (3/4)^N. For each element of X, there are equal numbers of subsets of X that contain it and that do not, so the chance of that element being in any given subset is 1/2. For each element, there's a 1/2 chance that it's not in B, and an independent 1/2 chance it's in A, so there's a 3/4 chance that the element does not make A not a subset of B. The elements are independent of each other, so the chance that all of them are okay is (3/4)^N.

I don't understand why an equal number of subsets would contain a given element as would not. For example, only two subsets of {1; 2; 3} contain {1; 2} (just {1; 2} and {1; 2; 3}), whereas six do not ({}, {1}, {2}, {3}, {1; 3}, and {2; 3}).

{1; 2} is not an element of {1; 2; 3}. Considering an element a, there obviously is a single identical subset except with a for every subset without a, and vice versa. --Nix

Yeah, I misread your proof. This makes a lot of sense. 76.190.157.141 01:08, 14 April 2009 (UTC)

Should this really be on this list?

Well let's see. In general, the number of subsets in a set is of course the cardinality of the powerset, which is 2ⁿ, and therefore the number of possibilities for A and B is 2²ⁿ. This is the sample size. A given one of those subsets which we label B has 2^b subsets, where b is the number of elements in B. Now, obviously 0 <= b <= n, and the number of subsets with b elements is n!/[b!(n-b)!], so we take the sum from b = 0 to n of n!/[b!(n-b)!], and this is the number of successful combinations of A and B. So the probability is:

 n
Sum  _____n!_____
b=0  22n b! (n-b)!

This looks pretty aweful, though. Is there a simplification I missed? 76.190.157.141 19:51, 14 March 2009 (UTC)

The sum is missing the 2^b, so you're just counting all possible subset Bs once (ignoring A), and the sum you gave always comes to 1/2ⁿ although I don't know how to prove that directly from the sum. Completed with the missing 2^b, I still don't know how to simplify it, other than from the other solution. So it should simplify to (3/4)ⁿ. --Nix

I know from looking at n = 1, 2, 3, 4, and 5 that it clearly should be (3/4)ⁿ, though I don't know how to prove that directly. Assuming you're right and my sum should include the 2^b, I get:

n!   n
--  Sum  ____2b____
4n  b=0   b! (n-b)!

But how to simplify this I still have no clue. But you're right, it should equal (3/4)ⁿ, which I feel like I could prove if it weren't 2:30 AM right now. 76.190.157.141 06:21, 16 March 2009 (UTC)

To simplify it, you use this--131.215.7.73 08:12, 20 March 2009 (UTC)

Thanks. That transforms it into:

 1   n
--  Sum  2b(nb)
4n  b=0

Now we know that:

 n
Sum  xbyn-b(nb) = (x + y)n
b=0

So, setting x = 2 and y = 1, we get:

 1   n
--  Sum  2b(nb) = (1/4)n(2 + 1)n = (3/4)n
4n  b=0

as we expected. Therefore the answer indeed is that the probability is (3/4)ⁿ. 76.190.157.141 20:01, 21 March 2009 (UTC)

Simpler solution: There is a 1/4 chance that any given element of X is in A but not B. A is a subset of B if and only if no such elements exist, so the chance of this is (3/4)^n, Q.E.D. Ravi12346 01:59, 27 April 2009 (UTC)

[edit] Dice Rolls

Here's a solution that has not yet been posted, and leads to yet a different answer. Oy vey.

Let's name two events:

• A = Bob wins
• B = Bob rolls a six on his second turn *and* the game gets far enough for him to do so (mind, this is different from "given")

We wish to calculate neither of these things, but rather the conditional probability P(B|A), the probability of B given A. This can be done by using Bayes theorem, which states: P(B|A) = P(A|B) P(B)/P(A)

So we have three things to calculate: P(A), P(B), and P(A|B), then we can calculate the answer.

P(A|B) is just 1, because Bob rolling a six on his second turn implies that he wins.

P(B) is the number we know and loathe: (5/6)(5/6)(5/6)(1/6) = 125/1296

P(A) is the probability of any sequence that looks like this: *6, ***6, *****6, ..., where * represents any number other than 6. These sequences are all mutually exclusive, so we can just sum them up:

 sum_{n=0..inf}{ (5/6)^(2*n+1) * (1/6) }
 = sum_{n=0..inf}{ (5/6)^(2*n) * (5/6)(1/6) }
 = sum_{n=0..inf}{ (25/36)^n * (5/6)(1/6) }
 = (5/6)(1/6) sum_(n=0..inf){ (25/36)^n }

The geometric series theorem gives us that sum_{n=0..inf}{ (25/36)^n } = 1/(1-25/36) = 36/11. So P(A) = (5/6)(1/6)(36/11) = 5/11.

And thus, the probability we are looking for, P(B|A) = 1*(125/1296)/(5/11) = 275/1296, which is about 0.212.

I made a simulation here: [1]

Here's an easier way to get P(A):

• C = Sue wins

Given that Sue rolls 1-5 on the first roll (5/6 chance), Bob's chance of winning is the same that Sue's was at the beginning of the game (by symmetry).

So,

P(A) = (5/6) * P(C)

combined with

P(A) + P(C) = 1

solves to

P(A) = 5/11

We believe the solutions posted so far are incorrect. We claim that the answer is in fact 1/6, and this would apply on *any* of Bob's rolls (second, fifth, one-hundredth). Here's the logic:

Let's first count the total number of events in our event space. In Sue's first roll, there are 5 events that allow the game to continue (a 6 ends the game). Now, for every one of these 5 events, Bob can roll any number, but a 6 would end the game prematurely, so only 5 of Bob's first roll outcomes continue the game. So far, we have 5*5 events that keep the game going. Now Sue rolls a second time. Again, only 5 out of 6 events allow the game to continue, increasing the total to 5*5*5. Finally, Bob rolls a second time. Since this is the final level which we are looking for, we can accept any of the 6 outcomes (a 6 will result in a win, and anything else would keep the game going, but the question is only up to Bob's second roll). So the total number of event in our event space is 5*5*5*6. This logic can be extended to any roll beyond Bob's second. Let me sum it up as follows:

Sue's 1st roll = 5 events that keep the game going (a 6 makes Sue win)
Bob's 1st roll = 5*5 events (a 6 ends the game prematurely)
Sue's 2nd roll = 5*5*5 events (a 6 makes Sue win)
Bob's 2nd roll = 5*5*5*6 (at this level, we can accept all of Bob's outcomes)

Now, of those 5*5*5*6 events, how many result in Bob winning? In the next to last level of this "tree", for each of the 5*5*5 events present in Sue's second roll, only 1 gives Bob a win: a six (the other five make the game keep going, but we don't want this). Therefore, out of our whole event space, there are 5*5*5*1 events that result in Bob winning. Hence, the answer to the question is:

P(Bob wins in second roll) = 5*5*5*1/5*5*5*6 = 1/6

Weird, huh? It's simply the probability of rolling a six on a single die roll. Notice that the answer would be the same for any of Bob's rolls, since we just keep adding 5s in both the numerator and denominator of the fraction.
What do you think of this?
(Posted by Meithan and Tlamatini)

• I think that answers "What are the odds Bob wins on his second roll, given that Bob makes his second roll?", which was not the question. *ABC*
  
• That's only semantics, and as I understand the question, it assumes Bob makes his second roll. This is just a difference in how the question, stated in common language, is interpreted. We would need to ask the creator of the problem what he meant.
• In fact, we've been thinking it over. The phrase "Bob rolls a 6 before Sue" means that Bob won the game, of course. But this happens only once in the event space. The question is: "what is the probability this happened on Bob's second roll". As we understand it, it means it didn't happen in the first roll, so Bob actually got to roll for a second time. The question you have in mind, if phrased in a better way, would be: "What is the probability Bob wins either in his first or second rolls?" (Meithan and Tlamatini)
  

--
For Bob to roll a 6 on his second roll, the following sequence must occur (roll outcome in brackets, probability in parens):
Sue's 1st: [1-5] (5/6)
Bob's 1st: [1-5] (5/6)
Sue's 2nd: [1-5] (5/6)
Bob's 2nd: [6] (1/6)

Multiplying, P(Bob rolls a 6 on his 2nd roll) = (5/6)^3*(1/6) = 125/1296

• While I don't disagree with your math, I think it's an unfair distinction that the problem states Bob rolled a 6 before Sue. It's stated as a given, but it's then being calculated as a condition of the probability. It's like saying, "what is the chance of a coin coming up tails on THIS flip (and oh, by the way, assume you just flipped heads 100 times in a row)" Either we know it was 1-5 on the prior 3 rolls, or we don't. It's badly stated, much like the conveyer-belt runway. 216.240.30.23 17:04, 11 February 2009 (UTC)

The question isn't 'What are the odds that Bob wins on his second roll,' the question is 'What are the odds Bob wins on his second roll, given that Bob wins?' I don't think it's poorly stated, just trickier than it looks.

• I solved it the first way, (5/6)^3*(1/6) [What is the probability Bob rolled the 6 on his second turn? - no more assumptions] and with the assumption that Bob wins [What are the odds Bob wins on his second roll, given that Bob wins?]. I don't know if I got the correct answer but it's not that tricky. What I don't understand is why someone would think the answer to be (5/6)*(1/6). *ABC*
  • To answer ABC's question: The problem states that Bob rolled a 6 before Sue. Therefore, every one of Sue's rolls is between 1 and 5; only Bob can roll a 6 before the game ends. So the problem can be rephrased as "What is the probability that Bob first rolls a 6 on his second roll?" That probability is exactly 5/36. [I'm not saying this argument is correct, just that it's intuitive. Probability is deeply weird.]
    • Thanks! *ABC*

--

I hate these problems, where an ambiguity in the wording leads to two groups of people convinced they have right and incompatible answers. For what it's worth, if the problem means this:

1. the trial has already taken place,
2. we know that Bob won, and
3. we wonder what the probability was that it happened on his second roll,

then the answer is (5/6)*(1/6) = 5/36. I personally think that that's the most sensible interpretation of the wording of the problem, but since Randall wants that not to be the answer, then I think the problem is poorly stated.

• First, solve for the odds of Bob winning at all: Well, if he wins on his first roll, it's 5/36. If he wins on his second roll, it's 5/(36^2), on the third it's 5/(36^3)... well, looks like a geometric series. It sums nicely to 1/7.

Then, figure out the odds of Bob winning on his second roll: (5/6)^3*(1/6) = 125/1296. Multiply by 7 (dividing by 1/7) equals 875/1296. Finally can get this problem out of my mind.

It seems to me that the sum for Bob's wins comes to (5/11) not (1/7). Treating as a geometric series, the first term is (5/36) for Bob's winning on his first roll. As stated above, the odds of him winning on his second roll are (125/1296). Remember that Sue has a chance to win between each of Bob's rolls. Thus our common ratio is (25/36) not (5/36).

This is also logical. If Bob only had a 1/7 chance in winning, that means that Sue's chances were 6 times greater, merely by going first. Bob's 5/11 chance seems a lot more reasonable.

Then, if you divide Bob's odds of winning the second roll (125/1296) into his odds of winning at all (5/11), you get a final value of (275/1296). That is to say, given that Bob wins the game, there is approximately a 21.22% chance that it was done on his second roll. - E.Meader (who add this to the wrong comment the first time)

What is the probability Bob rolled the 6 on his second turn? - Doesn't it remain constant? Each time someone picks up the die 1/6.

E.Meader's result is correct. The probability that the second roller wins is (1/6)sum((5/6) + (5/6)^3 + ...) = (1/6)(5/6)geometric_series(25/36) = (5/36)/(1 - 25/36) = 5/(36 - 25) = 5/11. - Evan

--

I hate these problems, where an ambiguity in the wording leads to two groups of people convinced they have right and incompatible answers. For what it's worth, if the problem means this:

1. the trial has already taken place,
2. we know that Bob won, and
3. we wonder what the probability was that it happened on his second roll,

then the answer is (5/6)*(1/6) = 5/36. I personally think that that's the most sensible interpretation of the wording of the problem, but since Randall wants that not to be the answer, then I think the problem is poorly stated.

• That is the correct interpretation, but your answer is incorrect. The explanation at the top that gives 275/1296 is the correct answer for your interpretation. You can't just ignore Sue's flips once you know she didn't win. -- dazmax

I would agree that the problem is really "What are the odds that Bob rolled a six on his second turn GIVEN THAT Bob rolled a six before Sue?" However, I think your math for computing P(Bob rolls a six first) is incorrect.

• As noted, the probability of Bob rolling a six before Sue and on his second turn is (5/6)*(5/6)*(5/6)*(1/6) = (5/6)^3 * (1/6).
• However, the probability of Bob rolling a six before Sue is the series of the following probabilities:
  • Sue (not 6), Bob (6) = (5/6) * (1/6)
  • Sue (not 6), Bob (not 6), Sue (not 6), Bob (6) = (5/6)^3 * (1/6)
  • [Sue (not 6), Bob (not 6)] x 2, Sue (not 6), Bob (6) = (5/6)^5 * (1/6)
  • [Sue (not 6), Bob (not 6)] x 3, Sue (not 6), Bob (6) = (5/6)^7 * (1/6)

• In short, this becomes sum( (5/6)^(2i-1) * (1/6), i = 1 to inf) = (1/6) * sum( (5/6)^(2i+1), i = 0 to inf) = (1/6) * sum( (5/6)^(2i) * (5/6), i = 0 to inf) = (5/36) * sum( (25/36)^i, i = 0 to inf), which is a simple geometric series. That series has sum equal to a/(1-r), where a is the first term and r is the multiplicative part, so that equals (5/36) / (1 - 25/36) = (5/36) / (11/36) = 5/11.

• As such, the final probability is [(5/6)^3 * (1/6)] / (5/11) = [5^3 * 11] / [5 * 6^4] = (5^2 * 11)/(6^4) = 275/1296. 71.231.180.184 18:07, 11 February 2009 (UTC)

Simulation shows that the answer 275/1296 is correct.

• I can vouch for the fact that simulation shows 275/1296 is correct.

• I think I agree that this question is poorly stated. We have, as given information:
  • The rules of the game.
  • The fact that Bob rolled a 6 before Sue. Since this means Bob ended the game, you can restate it as "Sue never rolled a six."

• Given that, we don't even have to consider the probabilities of Sue's rolls -- we've been told that she never rolled a six. (Consider being asked the question, "I just rolled a die and it didn't come up six. What is the probability that it didn't come up six?") That means the chance that the game ended on any particular one of Bob's turns is just P(he gets to take that turn) * (1/6). But that gets us back to 5/36, which is not supposed to be the answer. I suggest that the wording of the "Bob rolls a 6 before Sue" needs to be adjusted.
  • "I just rolled a die and it didn't come up six. What is the probability that it didn't come up six?" -> 1 in 6!
    • I don't understand this at all. Obviously the probability a fair six-sided die did not come up six is 5/6 (assuming, naturally, exactly one side is labeled "6"). The probability that the die did not come up six given that it did not come up six is obviously 1. I don't know hwo you get 1 in 6. Also, be careful where you put your exclamation points, as 6! = six factorial = 720. 76.190.157.141 23:55, 31 March 2009 (UTC)

A more intuitive solution:

Everyone has already solved for "the odds that Bob will win on his second roll" - 125/1296, for "Sue misses, Bob misses, Sue misses, Bob hits" in that order.

The problem is that that answer is the odds that Bob will win on the second turn, out of the set of ALL GAMES. What we want is the odds that Bob will win on his second turn, out of the set of GAMES THAT BOB WON. How do we know how many games Bob will win?

Well, pretend that Sue and Bob roll simultaneously, but that Sue's die is counted first if it is a 6. This gives us 36 possible results. Of those, 6 are wins for Sue, 5 are wins for Bob (he loses the 6-6 tie), and 25 are "roll again". This means that there are 11 possible exit conditions of the loop, all equally likely, and Bob wins 5 of those. Thus, in the set of ALL GAMES, Bob will win 5/11 of them.

Therefore: In all games, Bob wins 125/1296 of them on the second turn. Bob wins 5/11 of all games. Therefore, Bob wins on the second turn in (125/1286) / (5/11) = 275/1296 of all games he wins.

Which is the same answer everyone else is getting. Using a faster method. -John 99.224.156.92 22:27, 11 February 2009 (UTC)

The reason I think some people (including me!) get confused: Sue's *first* roll doesn't matter, but her second roll does. The reason the intuitive "Ignore Sue's rolls and just get 5/36 with Bob's!" solution isn't correct is that Sue's *second* roll isn't irrelevant. If you think of the game as "Whenever Sue wins, roll that round again until she doesn't" (which is equivalent to a probability of 1/5 on 1 through 5 and 0 on 6), it should be apparent that of the 36 potential outcomes of Bob's two throws, some of them are more likely then others.

(And it's easy to show that Sue's *first* roll doesn't matter -- you get the same probability if you give Bob the first turn! (When operating under the assumption that Sue loses.))

An intuitive argument against the (5/6)*(1/6) value:

Consider the first two rolls made by each player. There are 5*6*5*6=900 where Sue doesn't receive a 6, and of those, 5*5*5*1=125 where Bob gets a 6 on his second roll, but not his first. This is where the 125/900=5/36 figure comes from. However, the value of "900" there both overcounts and undercounts the real sample space. For instance, it doesn't count the state "1, 6, 6, 3" (Sue rolls a 1, Bob rolls a 6, and if they kept going, Sue would roll a 6, and Bob a 3). The extra rolls after the game is finished are included here to keep the probabilities equal (all strings of four rolls have equal probability of occuring... if there's a 6 in there, you simply count how many strings with the same preceding rolls remain in the state space to get the relative probability). Now, this would be ruled out of the state space used by the 5/36 argument... but it counts, as Bob won. On the other side, the state "1, 2, 3, 4" is included in the state space by the 5/36 argument... but it doesn't completely count, as Sue could still win. Specifically, it only counts for a weight of 5/11 - the chance that Bob would go on to win from here (others have already covered this value well enough).

So if we take all those together, our state space, instead of 900 elements in size, is the number of states where Bob wins on the first go, regardless of what Sue would get on her second roll (5*1*6*6=180) plus the number of states where Bob wins on the second go (5*5*5*1=125), plus 5/11 of the states where neither roll a 6 (5*5*5*5*(5/11) = 3125/11). Add these up and we get 6480/11. So our final probability is 125/(6480/11), and not 125/900=5/36. Evaluate that out, and we get 1375/6480 = 275/1296... the same value the Bayesian method gets. Phlip 10:44, 12 February 2009 (UTC)

A second, intuitive argument to show that Sue's second roll matters:

Imagine if instead of the second player, Bob was the 1001st player. In order for Bob to get a turn, 1000 other people have to NOT roll a 6.

Meaning, in order for Bob to get a SECOND turn after failing to win in his first turn, 1000 people must again not roll a 6.

If you run this long enough, Bob will win a couple - but, of those wins, how many will come up when he beat the (1/6)*(5/6)^1000 odds, and how many will come because he bucked the (1/6)*(5/6)^2001 odds?

This should make it clear that the other players DO affect when Bob's wins will come, even if we take only the subset of games where Bob won. -John 74.14.228.170 17:27, 12 February 2009 (UTC)

To the 5/36 people:

You are understanding the problem and it's wording correctly, the problem with your argument is the false (but reasonable sounding assumption) that you can ignore Sue's rolls just because she lost. If this doesn't make intuitive since, consider the following modified problem:

Let's say instead of rolling one dice, sue rolls 100 dice and picks the best roll. Let's also assume that we don't know who won. Since Sue goes first, the odds of Bob winning on the first round are (5/6)^100*1/6=2.01244558 × 10-9 while the odds of bob winning on the second round are (5/6)^200*5/6*1/6=2.0249686 × 10-17. This means bob is roughly 100,000,000 times more likely to win on his first roll than his second roll (intuitively, he might have dodged Sue's 100 dice once but it's pretty inconceivable that he dodged them again). Now, let's assume we know Bob won. This doesn't change the fact that he's still 100,000,000 times more likely to win on his first roll than his second roll. This means that assuming Bob won, the probability that he won on his second roll<.0000001%.

Now, since the only difference between my alternative problem at this point and the one XKCD linked to is that Sue gets to roll more dice it should be clear that either the answer to the XKCD problem is <.0000001% or more realistically, Sue's roll does matter, even when you know that Bob won. (I just read John's argument after typing this and realized that it was pretty similar, but I already typed this all up so I'm going to post it anyway.)

Or if that doesn't convince you, run the simulation for all possible rolls(including Sue's rolls) up to some ridiculous point. Then once this is done, discard all sets that end up with Sue winning. Then calculate how many of the results where Bob wins have him win on his second roll. You'll get the same result as XKCD. 129.21.126.225 05:44, 13 February 2009 (UTC)

Take the odds that the game was won on the second round. 25/36*11/36 275/1296. Of the games Bob wins, the distribution across rounds will be the same as the distribution of games Sue wins, which will be the same as the distribution of wins overall.71.203.62.31 09:20, 14 February 2009 (UTC)

---

We know that Bob won. This means Sue did not roll a six at any time before Bob rolled a six. It does not matter what Sue rolled in the range of one to five because the dice has no memory so does not influence Bob's roll. The probability of Bob rolling a six on his second roll is the probability of not rolling a six on the first roll multiplied by the probability of rolling a six on the second roll. 5/6 * 1/6 = 5/36.

This commits like ten errors, but the most important is that you absolutely cannot ignore Sue's roles. It is true that distinguishing between 1, 2, 3, 4, and 5 is unnecessary, but distinguishing between these and a six is. Very roughly put, even given that Bob wins, it is more likely that he won earlier because the longer the game goes on, the more likely it is Sue could win so the luckier Bob would have to get to stay in and eventually win. Now, define P(A) = the probability that Bob wins, and P(B) = the probability that Bob wins on his second roll. The question then asks for the value of P(B|A) = the probability that Bob wins on his second role, given that Bob wins. There are a number of ways to calculate this, but a convenient one is to use Bayes' theorem: P(B|A) = P(A|B) P(B)/P(A). P(A|B) = 1, obviously, because if we know Bob won on his second roll he certainly won. P(A) = 5/11, which is explained in multiple sections including the nice argument that out of the 36 possible combinations of initial two rolls, Bob wins 5, loses 6 (since if Sue rolls a 6 then Bob rolls a 6, Bob still loses; in fact, he doesn't even get the chance to roll the second time), and the other 25 just lead to another set of rolls, so Bob wins 5/11 of the games. P(B) = (5/6)(5/6)(5/6)(1/6) = 125/1296, because in order for Bob to win on his second roll, first Sue must not roll a 6, then Bob must not roll a 6, then Sue must again not roll a 6, then finally Bob must roll a 6. Therefore, going back to our initial calculation, P(B|A) = 1 * (125/1296)/(5/11) = 275/1296. So yes indeed, the answer is 275/1296. 76.190.157.141 04:47, 31 March 2009 (UTC)

---

Revised by self: 4-3-09 3:47PM EST

I, the unschooled, must school all you math geeks who are probably at least undergraduates. I'll take you on a journey demonstrating the various flaws in logic that were made, and some other ones that COULD be made, before arriving at the correct solution. Basic calculus and set theory end up prevailing in the end.

You’re all wrong, because the puzzle is flawed, or intentionally much more deceptive than anyone anywhere seems to get.

Even the people who head down the clever, but incorrect road to arrive at 21.21% haven’t taken into account the fact that there are an infinite number of cases in which neither one ever, ever rolls a 6, for all of eternity. Nowhere in the rules was it stated that eventually someone HAS to roll a 6 in *general play* and end the game. It didn’t even state that the 6-sided die had a side denoting ‘6′, nor did it state if the game could move through an infinite number of iterations before one person finally rolls a 6 or not, but that’s just getting into set theory pedantry that’s unnecessary. Games can be infinite and never resolve, or infinite AND resolve, and you didn’t search “all possible games” since you didn’t search or account for infinity. Nor did you fully explore the question because of this. In this SPECIFIC instance, it was stated that Bob *DID* eventually roll a 6. Sue did not, thus her odds of ever doing so are 0 over the whole of the game, and his are 1, even over an infinite length game. This tells us that a game can be infinitely long and still resolve itself; the implications of this are outside the scope of what I'm writing here but become important below. Also at the bottom is a more complete justification for excluding Sue, if that wasn't enough for you.

The odds that it was on his second roll that it happened are uncomputable because of this basic fact: we don’t know how long the game was. Even if the odds of an infinite game happening are infinitely small, it is still possible by the rules. It might then be thought that this problem is not possible to solve. You could say the odds it happened on the 2nd roll are infinitely small, I suppose. I.e. 0, but this would hold true with any position you ask about by this logic, so it must be wrong, or it presents a paradox, since the puzzle explicitly stated that he did in fact roll a 6, eventually, so every position can't have a 0 odds. What it really means is that we can't assign a specific value to any one roll, however, but we CAN derive a meaningful answer as I will demonstrate, using correct logic.

(Any mathematician worth their salt should now intuit the cancellation of infinities I'm about to perform in dumbed down language...infinitely small odds of an infinite game, but also infinitely small odds of him doing it on his second roll in an infinite game...come on now people...)

Let’s look at it another way. The only question we *can* answer easily is, what is the probability that he rolled *a* 6 on his second turn. We know that, assuming he didn't do it on his first, that probability is independently 1/6. This might (erroneously) be said to be equivalent to asking *the* 6, because it is game-ending; in an infinite number of games which Sue does not roll a 6 before him, in which he does eventually roll a 6 and the game terminates, he will roll a 6 on his second turn with a probability of 1/6. No more rolls are made, and the sequence is made non-infinite, and thus computable. Thus, the probability that he rolled *the* 6 on his second roll is 1/6, because that’s the probability he will roll *a* 6 on *any* roll. Except this isn't the correct answer either.

Delving deeper than that, the answer actually becomes that the odds are "more than or equal to 0, and less than or equal to 5/36," or in plain English, no more than 5/36. He would've had to roll 1-5 on his first turn, but then maybe he didn't. 5/6 * 1/6 = 5/36. The answer is <= 5/36 because it is the result we can define for the infinite series at this point, but we know that if we continue out asking "his 5th roll? His 78th roll? His 100,000th roll?" ad infinatum we will eventually reach "infinitely small," as shown above. That is the reason for the "less than or equal to" part. This answer tells us that there is at MOST a 5/36 probability of this happening, even though practically we can't say for sure that that was the probability that it WAS what happened. We can only say what its upper limit was. In formal language, we write [0, 5/36) . 0 is excluded because he eventually rolls a 6, so there has to be SOME possibility, right?

But we're not QUITE there. Up above, we established that a game CAN run infinitely long and still resolve. To reiterate, the rules stated no bound on the length of the game, and probabilistically speaking, it is possible to never roll a 6 for all of eternity. But the problem also stated that Bob DOES roll a 6, so an infinite game can be resolved. We CAN assign 0 probability to every *discrete* position. So we write the answer an inclusive (0, 5/36).

People often come to probability through learning what their mistakes were, but they don't integrate it tightly enough. "The dice has no memory" is an indication of this. That is an argument that is made either to one who is ignorant of probability, or made for ones' own line of reason, possibly indicative of an improper understanding of the mechanics. But this is seriously basic computability and probability, messed up by attempts to be clever that just aren’t clever enough, because of the deceptive nature of the puzzle.

Before you cry "but wait! You CAN'T IGNORE SUE!" The problem explicitly TELLS YOU TO. It says, SHE NEVER ROLLS A 6. Even hypothetically if she rolls 5000000000000*5000^202000000 die before Bob gets to roll a single one, she NEVER. ROLLS. A. 6. in this game. Remember that we're talking about a specific game. Her range of rolls is NOT 1-6 with a 1/6 chance of either, it's 1-5 with a 100% chance of one of them each and every time, as indicated by "...rolls a 6 before Sue does." We know that at every possible point in this game (including "at infinity"), her odds of rolling a 6 are 0. The problem states it. Thus we have no need to distinguish between 1-5 and 6, or worry about how her going first gives her an advantage, because she has no effect. If the question was "What are the odds that Bob might win on his second roll, given Sue might roll a 6 twice before him, and the outcome of the game is undetermined" she would be relevant and the answer would be (0, 21.21%). But the outcome IS determined, so that isn't the question. It explicitly states that for this specific game, she doesn't have any chance of rolling a 6 and thus winning, because Bob rolls it and wins. They are mutually exclusive conditions. She is in fact canceled out of the equations if you actually take the time to write them out formally. So she is not relevant, and it becomes a game of "when will Bob eventually roll a 6?" That's a very, VERY basic probability theory mistake...but a very hard one to decide sometimes.

This problem is either incorrectly formulated (i.e. the one who posed it didn't understand its implications properly and thus didn't frame it well), or the level of "cleverness" was of a higher order than most seem to have realized. Not knowing its origin I can't hazard a guess as to which is true.

-WritingSama

I cannot even begin to understand your conceptions of infinity or probability except to say that they are mathematically nonstandard and nonrigorous at best and completely wrong at worst. You clearly demonstrate no understanding of an infinitely long game at the point where you ignore the numerous infinite series that others with the correct solution have computed, state that a six can be rolled in an infinitely long game (unless you specify that the game lasted for a specific number (say, omega) rolls, there is no "last" roll), and end up with a confusing, convoluted, and demonstrably incorrect solution. You don't even understand 0 probability, a rather important concept when dealing with infinite sets. In particular, you state that the probability of Bob winning on a given roll should be zero (but then later contradict this) and that it is impossible for the probability of every roll to be zero and still have winning be possible (in fact, there are many situations where infinite possibilities each have zero probability but one of them must occur). I have to go now, but when I come back later I'll try to give specific reasons your result is impossible. 76.190.157.141 21:50, 3 April 2009 (UTC)

Please re-read the argument. I was modeling the system set up by the problem given, which is not consistent with reality, and the usual analysis are not applicable to it because of this. The problem itself is "broken." My analysis diverges from a "real-world" approach because the problem is not a real-world problem; it is fundamentally flawed, but still partially solvable. I analyzed it by its own rules to provide the answer. Specifically, I (intentionally, for demonstrative purposes) went through a chain of false conclusions, finding what was wrong with them and then solving it to produce a new one, until eventually arriving at what I believe to be the correct one. That's why I directly contradicted myself. I wasn't as explicit as possible, but there's only so much I can type, being disabled. Mathematically speaking, it shows more rigor than most other things I've seen here. Ever hear that old joke about a biologist, a physicist, and a mathematician on a train that see a brown cow? The biologist says, all cows are brown! The physicist says, some cows can be brown. The mathematician says, there was at least one cow, at least one side of which was brown. That's a fairly good standard for mathematical rigor, actually. I can understand how if you don't understand set theory and how it applies to this problem, you might have trouble following the argument. I do look forward to hearing your critiques though :-P I'm certainly not terrifically formally educated, and I realize that I am fallible. The thing is, I do understand all the analysis others applied to it perfectly - and also understand their flaws in this context. They might be perfectly good in most other contexts, but this is a special, broken case, as I'd hoped I'd demonstrated. Finally, you said "in fact, there are many situations where infinite possibilities each have zero probability but one of them must occur," which is only tangenitally related, but I think I see what you're getting at. I thought I demonstrated how this applies? Did you not read it the first place I did so, and then miss the second?

I like to think I'm educated in these things, but Wikipedia probably isn't the best University around :P. Seriously, though, your comment still makes no sense to me. There is nothing about this puzzle especially non-real world. We could certainly play this game in real life, and while dice may not be perfectly random, we can approximate them to be very close. Your objection seems to be that there is a possibility of a game lasting for an infinite number of turns, but that is in fact the ONLY possibility which has probability zero, and as such we can safely ignore it for our analysis (it is given no weight when calculating probability). The probabilities of winning on a given turn can be arbitrarily small, but must be nonzero, so we must include all of them in an infinite sum (although there are easy ways around this, of course). Anyways, the only real flaw I can understand well enough in your analysis to point out is where you state Sue's rolls can be ignored; this is definitely not true, and several explanations above gave good parallels to help explain this. Imagine an analogous scenario where instead of rolling a six on a six-sided die to win, Sue only had to roll any number except one on a 1,000,000-sided die to win, while Bob still had to roll a six on a six-sided die as usual. Now, we are given that Bob somehow got extremely lucky and Sue did not win on her first roll, because we are given that Bob wins. However, we don't know when. Now, do you expect it to be more likely that Bob won on his first turn, or that he managed to get extraordinarily lucky again and have Sue again roll a one, such that Bob can win on a subsequent roll? It is clear that the first possibility is far more likely, and that the reason for this is that we cannot ignore Sue's rolls. The problem we are trying to solve is completely analogous but with a ¹/₆ probability replaced with ^999,999/_1,000,000.

A final note is that dice do not have memory. This isn't a mistake, this is just obvious. I mean, I just tested this by asking some dice what their last roll was and they couldn't tell me; couldn't remember a thing. I don't know what you meant by this statement.

To help me out here, maybe you could try explaining more precisely the error in the reasoning of, say, John. That might help me understand what you think the flaw is and why your answer makes sense (and, honestly, what it is). 76.190.157.141 01:47, 4 April 2009 (UTC)

[edit] Ants

@Shimavak: The problem cannot be solved recursively, since the ant that you're going to "put" after the longest run of n-1 ants (lets call this time t1) has to be put somewhere at time 0 and till time t1 is free to collide (and interfere) with the n-1 ants!

@Andrew: Assuming that you put ants at 0.5, 1.5, ... then only the first collision will occur at 50cm mark.

The answer is pretty straightforward: 100. @McGeddon provides the best solution, @Narapas's is also acceptable.

--Aniruddha

Simply assume they don't collide - as the ants all must start at the same time, move at the same speed, and reverse when ant x's location = ant y's location, we can model the difficult and complex behavior by simply switching the ants. Put them all in a row, going the same direction, and put one on the edge of the ruler. They'll get 100 seconds to move a full meter.

--Narpas

I believe this problem is best thought of in reverse. We know that the situation which will take the longest would be to have an ant turn around at the very end of the ruler before it falls off (having started from the other end), so we need to look at what configuration would cause this. We can then add an ant each time to provide the longest run time for that iteration to produce the longest run of the n-1 ants iteration, and simply expand to n=100. The rest is left as an exercise to the reader.

--Shimavak

Are we allowed to drop ants onto the stick all willy-nilly whenever we feel like it?

--Narpas

Since the ants are zero size, they can all exist at the same location at the same time. Put them all at 50cm facing the same way.. They all constantly collide with each other (at the same point) and so constantly turn around. Ants will stay on the ruler forever.

-- SoftNum

Two zero-size ants bouncing off each other is the same as two ants walking past each other, so this is essentially a question of where to put one ant, which is "at one end, facing the other" giving a time of 100 seconds.

-- McGeddon

Well, the question is asking what arrangement will do this, a simple one would be an ant every cm facing alternating directions, starting with one facing inwards at the very end. The amount of time for all ants to fall off will be the same as the amount of time for one ant to cross the stick, or 10 s.

Now the idea of them all being in one place with the same direction only holds if these "ants" aren't fermionic, though I believe that the fact that they are colliding in the first place means that they must be exerting some force on each other when they are infinitesimally close. If they're all stacked in one place, then they would not be able to deflect each other, so they'd all move to the end of the ruler together, to their doom.

Of course, if the deflection is self initiated, then the ants would constantly perceive themselves to be colliding and choosing to change direction, so they would always switch directions. But the key word here is "collide", and I think that implies that they have to approach each other....

Besides, if they were all in one location, the energy stored in this system would cause the ants to collapse into a micro black hole, which would then evaporate through Hawking radiation (or consume the Earth, if you believe the tabloids). Anyone know how to calculate the amount of time this would take?

Or you could try entangling th- <gets slapped by a physicist>

--SteveMcQwark 18:27, 1 March 2009 (UTC)

couldn't you not think length but width, so line all your ants up on the edge of the ruler and as soon as they step foward they would fall, so total time being around <1

-- I love this problem. I sat there for 5 minutes trying to figure out optimum ant arrangement. When i figured out that it doesnt matter, the ants are f*cked in 100 seconds anyway, I had to slap myself silly.

-- What if you put 50 ants 1cm apart on the left side of the stick and facing the center of the stick, and 50 ants 1cm apart on the right side of the stick and facing the center of the stick? They would all start bouncing back and forth, the ants toward the edges of the stick would be falling of quickly but the ants in the center would be kept bouncing for awhile. Longer than 100 seconds? I don't know. But how about placing all the ants at intervals of greater than and less than 1cm apart? You might be able to increase the time that way. Seems this would take a whole lot of math to figure out

.--

Well, it doesn't take a lot of math to figure out, just some modeling. So, you arrange the ants with one at each centimeter line, starting on the edges of the ruler, with 50 on the left facing inwards and 50 on the right facing inwards. After 1 second, ant 1L hits ant 1R at 50 cms, and turns around (here you can focus on just one side of the ruler, since the problem is symmetrical) At 1.5 seconds, ant 1 hits ant 2 at 49.5 cms. At 2 seconds, ant 2 hits ant 3 at 49 cms. This continues on until you reach 25.5 seconds, at which point ant 50 hits ant 49 at 25.5 cms, leaving ant 50 with 25.5 seconds left of survival (51 total). At 26 seconds, ant 49 hits ant 48 at 26 cms, leaving it with 26 cms left to go for a life-span of 52 seconds. This continues back down the line of ant-oscillations until you reach 50.5 seconds, with ant 1R hitting ant 1L at 50 cms, leaving them with 50 cms and seconds left to travel, for a life span of 100.5 seconds, which is the maximum possible for this problem!

100.5, not 100.

-Andrew

[edit] Blue Eyes Puzzle

The solution provided on xkcd is actually incorrect. The solution operates on the reasoning that each of the x number of blue-eyed people see x-1 blue-eyed people, and can assume that they don't have blue-eyes, so they can imagine that each of the x-1 they see individually sees x-2. In other words, if there are 3 blue-eyed people, each sees 2, and can assume that both of the 2 only see 1. Each blue eyed person watches the whole process from the perspective of a brown-eyed person until they collectively realize they are the final blue-eyed person. This works fine exactly up to the point where you developed the solution, but no further. The maximum number of blue-eyed people that this style of reasoning works for is 4.

If there was only 1 blue-eyed person, he would know his eyes were blue, because he sees 0 blue-eyed people; he could leave the first night. If there were only 2 blue-eyed people, each would only see 1 blue-eyed person, who they could assume sees 0 blue-eyed people, and the presence of the other blue-eyed person the next morning would prove that they see 1 blue eyed person also, so each one also must have blue eyes. If there were 3 blue-eyed people, each would only see 2 blue-eyed people, who they would imagine to see only 1 blue-eyed person. On the first morning, they would still see 2 blue-eyed people, and they would realize that if these were the only blue-eyed people, they would both realize it that day and leave that night. When they were still there the next morning, each would realize they were the third blue-eyed person, and they would all leave that night. If there were 4 b.e.p, they would each see only 3, and tentatively think that each of the 3 only saw 2. The first morning they each still see 3 b.e.p, but if each of these 3 only sees 2, then the next morning each of the three would realize they are blue-eyed, and leave the third night. When they don't leave the third night, each realizes they must each see 3 blue-eyed people, and they can conclude that they themselves are the 4th blue eyed person.

The problem comes at five blue-eyed people: 5 see 4 who apparently see only 3. The first morning, they still each see 4, but think each of the 4 only sees three. When each can see at least 4 each morning, they realize there is no way to deduce how many there are. At the very least, each of the 4 known blue-eyed persons must see at least 3 other blue-eyed people. This eliminates the helpfulness of the first day and night; the first morning, they each see 4. If there were only 4, each of the 4 would see 3. If there WERE only 3, each of the 3 would see only 2, and the process could continue as usual. But the blue-eyed people KNOW there are actually at least 4, so their reasoning cannot function based on the assumption that if there were 2 they would leave the second night, and if there were 3 they would leave the third night. Their collective understanding of the fact that there are 4 even though each of the 4 could possibly only be conscious of 3 undoes the reasoning of the solution. Each night effectively becomes the first night, because no new information is gained over time. The solution absolutely hinges on the possibility that each of the blue-eyed people could possibly see ONLY 2 others; this is the crucial first step in the reasoning process. With 5 blue-eyed people, they cannot possibly reduce their reasoning to allow for each to only see 2, so the deduction falls apart.

The true solution is that the guru provides no new information, and no one leaves. The solution provided on the site is enticing, but the assumption that because it works for 1, 2, 3, or 4 blue eyed people, it works for ANY number, is false. In fact, the premises are false in light of the solution that no one makes it off the island. If the guru was perfectly logical as the puzzle states, she would know no one could get off the island given her statement. A perfectly logical person would have simply said "There are 100 blue-eyed people and 100 brown-eyed people here."

Andrew

The Guru observes that she spoke, relizes that she is the guru and thus has green eyes, and leaves. edit: No, this is a retarded conclusion. First of all, why would the Guru not realize she was the Guru until she spoke? And why would knowing she was the guru inform her that she had green eyes? Nowhere on the island is a pamphlet that says "the guru has green eyes".

They are similar indeed, though in the case of the two examples you supplied the question is the opposite of the Blue Eyes puzzle, that being the number of people leaving instead of who and when. Either way, just providing the answer here (after conflict resolution): All the blue-eyed people leave on the 100th night. - Guest 18:04, 11 February 2009 (UTC)

I'd like some more explanation to this answer. As they all know that there are at least 99 blue eyed people, the statement of the guru adds no new information. Apparently they use the statement as a trigger to start counting days. But that was neither agreed nor the only logical thing to do.--128.171.90.200 20:25, 11 February 2009 (UTC)

• Consider the case where there are only 2 blue-eyed people (A and B) on an island, surrounded by non-blue-eyed people. The Guru makes that statement that she sees at least one blue-eyed person. Both people with blue eyes see one blue-eyed person, so they can't determine their own eye colors. However, if A were the only blue-eyed person, then A would have to leave that night. So when morning comes and B observes that A has stayed the night, B realizes that A must have seen another blue-eyed person, and that must be B. Person A follows the same logic, and both leave on the second night. Extend this for n blue-eyed people to reach the solution. (Note that because no one leaves until the nth night, the Guru's daily observations become superfluous after the first day.)
  • That would work but not in this case, because the trigger is wrong. It would work if they were dropped on an island on a certain day or the ferry started running on a certain day. The Guru's statement holds no information, because everybody can see at least 99 blue eyed people. The brown eyed people have the same information: that there is at least 1 brown eyed person there. If the trigger was that the ferry started running on some day, both the blue and brown eyed people would leave on the same day and the guru would spent eternity alone on the island. (So she'd better keep her mouth shut :) --72.234.171.208 23:50, 11 February 2009 (UTC)
    • The guru's statement does impart some new information; after he speaks, everyone on the island knows that everyone else on the island knows that someone on the island has blue eyes. They all already knew there was at least one blue-eyed person. They just didn't know that everyone else knew.
      • It's worth mentioning that there is absurd amounts of discussion of this puzzle (and a few variants also) yonder. Phlip 12:06, 12 February 2009 (UTC)
        • If everybody can see either 99 or 100 blue-eyed people, everybody knows that everyone can see at least one blue-eyed person (actually everyone can see 98 or 99 blue-eyed people), so there's no new information.
          • There is new information. To keep things simple, lets assume *lots* of people on the island, so blue eyes are very rare. Thus each person, including each blue eyed person, assumes that they do not have blue eyes. Now, if I'm on the island, I know at least one person has blue eyes. And I know *that everyone knows* at least one person has blue eyes. But I do not know that everyone knows that everyone knows that everyone knows (...) that at least one person has blue eyes to arbitrary depths of recursion. That is, we do not have common knowledge of at least one person having blue eyes.

• • • • • • Thus, I look out, and see 100 blue-eyed people. I look at one of them, imagine him surveying the island. In my imagination, he looks around, sees 99 blue-eyed people, and imagines one of them surveying the island. In his imagination, he looks around, sees 98 blue-eyed people, and imagines....etc.

• • • • • • Eventually, I come to an imaginary person who sees no blue eyes.

• • • • • • However, once the guru speaks, *all mental levels* suddenly contain at least one pair of blue eyes. Thus, this really is new information. Maxwell 02:14, 19 February 2009 (UTC)

• • • • • • Yeah, people keep saying that... but you're still wrong. Phlip 21:34, 12 February 2009 (UTC)
            • I think I have an idea here, but it's past midnight and I'm in that half-slumber where you have wonderful ideas. If in the first night, no-one leaves, everyone will know that there are at least 2 persons with blue eyes, based in the deduction that if person X saw only brown-eyed persons and heard the guru, he'd leave instantly. Then, if another day passed, the fact that there are 3 persons with blue eyes would be known (Gut feeling here, I can't explain how), and after 99 or 100 days (can't figure out the amount!) everyone would know that there are 100 persons with blue eyes. After basical math, all the blue-eyed would leave at the same time, and their combined weight would sink the ferry. Please, work on that idea while I get some well-deserved sleep.
    • Actually, the trigger is correct, the whole thing works by induction. The countdown can't start by the ferry coming to the island (well, it could if they agreed to do some sort of countdown, but without some sort of prior communication, the islanders can't prove anything). In order for the induction to work, it has to be true that even if there was only one blue eyed person on the island, they would still know it. The Guru's observation is important not because it gives new information, but because it gives information that is true independently of how many blue-eyed people are on the island as long as there is a positive number. Yes, everyone already knows there is a blue eyed person, but had there only been one blue-eyed person on the island, they wouldn't know it and the Guru's information would be useful. The induction requires knowing what would have happened had there only been one person on the island and so the Guru's information actually changes what can be reasoned with it. Without the Guru's information there is no base case for the induction. This type of puzzle is probably my favorite because it is just so ridiculously counterintuitive. It's not the Guru that provides new information, it's how the perfectly logical islanders respond to the Guru's information that provides new information, which thus incites a response/non-response which provides even more information....129.21.126.225 06:09, 13 February 2009 (UTC)

The two-blue case does not accurately represent the situation. Assume that there are three blue-eyed people. All of them have the same information: They all know the same things and have identical actions, so we'll follow A. A knows that there are two people, B and C, with blue eyes (He doesn't know about the third, himself). When the oracle makes the pronouncement, he doesn't know his own eye color. If he saw nobody with blue eyes, he would know his eye color, and would leave. Since nobody leaves, everybody sees at least one blue-eyed person. The next day, he knows that everybody sees at least one blue-eyed person(BEP), including everyone with blue eyes. There are therefore at least two BEP If there were only two BEP on the island, they would see exactly one BEP. Knowing that there were at least two BEP, they would both leave. Since nobody leaves, everyone now knows that everyone, including BEP, sees at least two other BEP. Therefore, there are at least 3 BEP. Now, A, who sees two BEP, knows that there is a BEP he doesn't see- himself!

Note that the brown-eyed people never get to leave, unless they know that the rest of the people have brown eyes.

Also, the trigger starts either when the ferry comes to the island, or when the pronouncement is made, whichever is later.

You've nicely set up a base case: that for 3 BEP, they all leave on the 3rd night. But no one has made an argument for the inductive step: If n BEP leave on the nth night, then n+1 BEP leave on the n+1th night. It's been alluded to by actually using 2 BEP leaving on the 2nd night as the base case for n=3. So, if there were n+1 BEP, each would see n BEP and expect them to leave on the nth night. Since no one leaves, they realize everyone else sees n BEP, meaning there must be an additional BEP, "the viewer". Each can then conclude that he has blue eyes. N.B. n=2 is the real base case. The use of n=3 as a base case uses this and does not describe the puzzle more accurately, it just offers a specific case of the solution.

Blue Eyes Puzzle - answer: 200 people leave on the third night after the ferry comes regardless of whether the guru has spoken yet. Fact 1 – everyone on the island is perfectly logical and perfect logicians. Therefore if one person can logically know something all will know the same thing logically if they have the same information. Fact 2 – there are 201 people on the island, 100 blue, 100 brown and 1 green (though the cardinal numbers aren't really important for – at least – all situations in which n > 3 for any grouping). The people do not know the distribution of eye colours Fact 3 – If there was 1 person with brown eyes and that person knew there was at least 1 person with brown eyes they could leave. If there were two it would take until the second day because each person would look at the other and say “if they were the only one, and perfectly logical, they would have left on the day 1, given that they didn't I must have brown eyes” and so on... -> infinity. Now, take a Brown eyed person, called Bob (why not...). He looks around and see 99 other people with brown eyes, but doesn't know if this is because there are 100 people with brown eyes, including himself, or just the 99 he can see. Should it be the case that there are 99 brown eyed people only (pessimistic assumption) then Bob can know that AT LEAST the other people can see 98 people with brown eyes (the 99 minus themselves). Leads to Fact 4 – everyone can see at least 98 people with brown eyes. There are at least 98 people with brown eyes (on the pessimistic assumption that bob doesn't have brown eyes and that everyone who bob can see who has brown eyes (99) each cannot know their eye colour and make the pessimistic assumption that there are only 98 people with brown eyes). Everyone knows this. Therefore there is at least one person with brown eyes (what the guru would have said to them if she had been talked about them). Now we split time into imaginary time (I.T.) and real time (R.T.). IT is the logical deduction of what the state would have been like had the RT run through to that point. Therefore everyone can imagine (in IT) that the ferry has been coming for 97 days and no one has left – they couldn't because there is at least 98 people with brown eyes no matter who looks at it. So IT day 98 = RT day 1. If it is the case that no one leaves (as is to be expected because everyone can see 98 people with brown eyes) then everyone can know that there are in fact 99 people with brown eyes because if there were 98 then the 98 would have left on the first opportunity after day 97 because they would see that there are 97 other people with brown eyes but that they did not leave on day 97 – given that that person could not see anyone else with brown eyes it must be them who is the other and so they can all leave. So on IT day 99 (=RT day 2) everyone looks around and sees that there are 99 other people with brown eyes, if it was the case that there were only 99 then each person with brown eyes would see 98 and know that there were in fact 99 people with brown eyes (because of their actions on RT day 1) and know that they can leave so long as they only see 98 people with brown eyes – because they must be person 99. If no one leaves on that day then we get to IT day 100, RT day 3 in which everyone knows that there are 100 people with brown eyes (Bob's “optimistic” assumption) but bob can only see 99 people with brown eyes and knows that there are 100 – so he must be no. 100. Thus everyone can leave. The same is true for those with blue eyes. --Joe

• People with brown eyes cannot leave the island, because they cannot logically conclude that their eyes are brown instead of grey, purple, red, black, etc. They don't possess the knowledge that there are only blue-, brown-, and green-eyed people on the island. Similarly, the Guru cannot leave the island. --Mark
  • I agree the Guru cannot leave, but I fail to see why the observation that our Bob made (I can see 99 people with Brown eyes) cannot lead to the general claim "there are at least 98 people with brown eyes" - which is essentially a higher version of what the guru would say to the blue people. It must be true - no matter the colour of any individual's eyes - that in the situation where there are 100 people with brown eyes everyone can know with certainty that there are at least 99 people with brown eyes and moreover everyone can be sure that everyone else knows that there are at least 98 people with brown eyes (e.g. the universe of people with brown eyes for bob is 99 people - if he assumes he doesn't have them - and so he knows that everyone in that universe knows for a fact that there are at least 98 people with brown eyes (everyone excluding themselves) so there is common knowledge there which goes far beyond what the Guru would say - if she felt like talking to brown eyed people) --joe
    • The point is that, although Bob can see 99 people with brown eyes, Bob can imagine a scenario where Bob has red eyes. Therefore, in Bob's imaginary scenario, the first brown-eyed person to his left (1BEPL) would see 98 people with brown eyes. In Bob's imaginary scenario, 1BEPL could imagine a scenario where 1BEPL has red eyes. Therefore, Bob can imagine a situation where 1BEPL imagines that 1BEPL has red eyes, and so in this imagination of an imagination, the second brown-eyed person to Bob's left (2BEPL) would see 97 people with brown eyes. This continues down the line, until...

• • • Bob imagines that 1BEPL imagines that 2BEPL imagines that 3BEPL imagines that 4BEPL imagines that ... that 99BEPL imagines that he has red eyes. Therefore, Bob can conceive of a situation where all the brown-eyed people he sees aren't sure of the color of their own eyes. Without knowing a Guru-style comment (new information which says, essentially, "At the highest repetition of imagining another person's thoughts, it is impossible to imagine that nobody has blue eyes") it is impossible for Bob or any other brown-eyed person to leave the island.

• • • Indeed, you say, "[Bob] knows that everyone in that universe knows for a fact that there are at least 98 people with brown eyes," but what this story requires is that he knows that everyone knows that everyone knows that everyone knows that everyone knows...etc.

• • • Incidentally, in order for the progression of imaginations to collapse, days have to pass where nobody leaves. That's why the blue-eyed people, armed with the Guru's new information, are able to leave on the 100th day. And that's why, on the 101st day, the brown-eyed people (whose level of imagination went one level deeper) say "Oh, darn! I guess our eyes aren't blue." But they still don't know what color their own eyes are. --Mark

All blue-eyed people leave at midnight on the 100th day after the Guru makes her declaration. All green- and brown-eyed people stay behind. The Guru's declaration contains new information, which is the necessary triggering event. It works as follows:

On Day 0, the Guru states, "There is at least one blue-eyed person on the island." This is an equivalent statement to, "If you can see nobody with blue eyes, you may leave at midnight tonight (on Day 1), knowing your eyes are the blue ones." However, nobody leaves at midnight on Day 1, because they each see at least one other person with blue eyes. We know this'll happen because we can see the eye-color distributions.

Since nobody leaves the island, everyone recognizes that there must indeed be at least two blue-eyed people on the island - the one who would've left on Day 1, and a second blue-eyed person whose presence prevented the first from leaving on Day 1. However, now we have what is essentially a second iteration of the Guru's statement, one which everyone knows. "There are at least two blue-eyed people on the island." This is an equivalent statement to, "If you can see one other person with blue eyes, you may leave at midnight tonight (on Day 2), knowing your eyes are also blue." However, as before, nobody leaves at midnight on Day 2, because they each see at least two other people with blue eyes. Again, we know this'll happen because we see the eye-color distributions.

This continues following the same formula. The next rendition of the Guru's statement becomes "There are at least three blue-eyed people on the island: if you see two other people with blue eyes, you may leave at midnight tonight (on Day 3), knowing your eyes are also blue." Because this can be expanded, we can generalize it to become "There are at least N blue-eyed people on the island: if you see N-1 other people with blue eyes, you may leave at midnight tonight (on Day N), knowing your eyes are also blue."

But what is the maximum limit on N? We know that each person with blue eyes sees 99 other people with blue eyes. This satisfies the predicate in the second part of the the Guru's statement written above for N = 100. Therefore, 100 blue-eyed people leave the island on Day 100. The brown-eyed people (and the Guru) are stuck behind, because they never had an initial Guru statement on which they could base their logic for their own eye colors.

Note that this is not induction: each new version of the Guru's statement takes as data the fact that nobody left the island at midnight. --Mark

--Just because no one leaves the island doesn't confirm that there are at least x-amount of blue eyed people. After 100 days a blue eyed person would observe that no people have left the island, but for all he knows he could have brown eyes. ALL the blue eyed people would have to GUESS that they had blue eyes. After 100 days a blue eyed person observes that he can still see 99 blue eyed people on the island, but that does not give him any information about his own eye color. No one has left the island after 100 days because all the blue eyed people logically know that they could have eyes that are brown or green or hazel or black, and as far as I can tell no one ever WILL leave the island.

1) Suppose there is just one blue-eyed person on the island. That person, seeing no other blue-eyed people, will leave on the first night. Everyone else will know that because he left on that first night, they all don't have blue eyes.
2) Suppose there are just two blue-eyed people on the island. Those people will both see one other blue-eyed person. When that one blue-eyed person doesn't leave on the first night, they know that there isn't just one blue-eyed person on the island (as per scenario 1). They'll both leave on the second night. Everyone else will see two blue-eyed people leave on the second night, and will all know that they do not have blue eyes.
3) Suppose that there are just X blue-eyed people on the island. Those people, seeing X-1 other blue-eyed people, will leave on the Xth night because X-1 people did not leave on the X-1th night. Everyone else, seeing X blue-eyed people leave on the Xth night, will know their eyes are not blue.
You should remember that the experience of blue-eyed people is different from the experience of non-blue-eyed people. Blue-eyed people will see one fewer blue-eyed person in the population than non-blue-eyed people.
--Mark

The fact that everybody already knows all the rules means this doesn't work. This would only work if there are only one or two blue eyed people on the island, and the logic doesn't chain up. It only works for two people because they would expect the other person to leave if they didn't have blue eyes themselves (as if that was the case that would be giving the sole person with blue eyes new information), thus making them not leaving be new information. If they see many people with blue eyes (and thus know that everybody else sees many such people), they do not learn anything when nobody leaves, and there is no difference in their knowledge on the 98th day than there is in the first. Besides, the Guru isn't giving any new information, as per the rules being known everybody already knows the Guru sees people with blue eyes. Whoever came up with this puzzle didn't think it out right, and nobody leaves.

The guru announces that he can see at least one person with blue eyes. 1) If there is just one blue-eyed person, learning that there is a single blue-eyed person means that he now knows the color of his own eyes and is free to go the first night. 2) If there are exactly two blue-eyed, each of them sees just one person with blue eyes. Because each of them doesn't leave on the first night, both of them now realize that they must also have blue eyes, and then leave on the second night. 3) If there are exactly three blue-eyed, each of them sees two people with blue eyes. If they were the only two people with blue eyes, it would be situation #2 and they would both leave on the second night. Because that doesn't happen, all three of them now know that they must have blue eyes and leave on the third night. 4) In general, then, let's assume f(N) that if N people have blue eyes, they will sort it out within N days and leave (as I've demonstrated in the cases of 1, 2, and 3). Then, if there are N+1 people with blue eyes, each blue-eyed person sees N people with blue eyes. Based on our assumption, N people with blue eyes will have figured it out in N days. Seeing that they don't, it must be the case that there are N+1 blue-eyed people and they will all leave on the N+1 day. In other words If f(N), then f(N+1). 5) Because f(1), f(2), and f(3) are true as demonstrated, and since f(N) implies f(N+1) as demonstrated, for any number n of blue-eyed islanders, they can figure out exactly how many of them have blue eyes in n nights and leave. In the case of this example, then, an island containing 100 blue-eyed islander will figure this out in 100 days and leave. Sadly for the people who don't have blue eyes, each of them was waiting for the nth night to see if the situation resolved itself. Because it did, the can conclude that they don't have blue eyes, but are stuck not knowing the color of their own eyes as a result.

Here's why I'm not really buying it: Every islander already knows that no one on the island can suspect that they are the only person with blue eyes. For that matter, everyone on the island knows that everyone else can at least see 98 other people with blue eyes. (If I'm blue eyed but don't know it, I know that there at least 99 people with blue eyes. That means each of those people will at least see 98 other people with blue eyes). The guru's announcement means nothing to any of the islanders. He just as well have announced that the sky is blue. If they wanted to start "counting down" the induction, they could have done so immediately without the aid of the guru. For that matter, all of this holds true for the brown-eyed people as well. This leads me to believe that something's afoul thinking of this inductively, and I suspect it's because ultimately each islander has to believe that at least one person on the island may have reason to believe that there is only blue-eyed islander, and thus there could be a "first night" which either will or won't happen. In other words, learning that someone else on the island has blue eyes has to plausibly be new information for at least one islander, from the perspective of at least one other islander. This is only going to be true when there is a sufficiently small number of blue-eyed islanders (but I'm making myself dizzy trying to figure out exactly how small).

[edit] The Monty Hall Problem

This question has been definitively answered, defended, and answered again. The latest treatment I've seen for it can be found in Michael Shermer's column in the October Scientific American.

Short answer: Yes, change your choice.

The article also has a link to a demonstration on the web you can use to convince yourself. Or, just get three playing cards and a friend, and play the game a few times, keeping score. It's amazing how many people just won't spend a few minutes doing this. --Sidelobe 18:48, 11 February 2009 (UTC)

The answer assumes that the host always shows you another door. On the show, this was not always the case: if you chose correctly, you were more likely to be presented with the choice. If you were incorrect to begin with, Monty would sometimes just open your door and give you the goat. Let's suppose the odds look like this:

Initially incorrect: 50% chance of getting the choice
Initially correct: 100% chance of getting the choice

Then the game has changed. Given that you have the choice, the odds are now stacked in favor of keeping your door. This becomes more obvious if you change the odds to 0%/100%, where you should never change your choice because you're right if you even got to this point. --70.103.74.5 19:46, 11 February 2009 (UTC)

Yes, but the puzzle clearly states that both A) he always opens a door at this point and B) the door he opens has a goat. Period.

Not so short answer: Yes, change your choice. The probability that the car is behind the door you choose the first time is 1/3, the chance that it's behind one of the other two doors is 2/3. Keep in mind that Monty knows where the car is. He now opens one of the remaining doors (with a goat behind it). The probabilities haven't changed though: Initial door: 1/3, the (one!) remaining other door: 2/3. Thus changing your choice yields a 2/3 probability of winning the car. If you don't believe it, try it out!

You can put it into a look-up table. Assume that the prize in behind door #1 and that the host always picks a door that wouldn't win.

Contestant    Host       Change
  1 (win)    2 or 3   3 or 2 (lose)
  2 (lose)     3         1 (win)
  3 (lose)     2         1 (win)

If you don't change, you have a 1/3 chance of winning. If you do change, you've got a 2/3 chance of winning.

Actually the answer is No. It is not and advantage, nor disadvantage, to change the choice. When Monty opens door #3, the chances of your first choice to be right ALSO goes to 2/3. He will always open one of the doors and leave the option between the other two. It creates some kind of psychological illusion that something has changed, when in fact it didn't.

Um, slight problem there. How can the chance of your first choice being right change? When you made the first choice, you had no information about the location of the goat, and thus your chance is simply 1/3. The fact that you know something now can't help you with a decision you made in the past. I especially wonder how it can also be 2/3, given that probabilities are always between 0 and 1. Timotiis - 87.115.129.80 13:19, 16 February 2009 (UTC)

So? 2/3 is between 0 and 1...

If you pick door A and the host opens door B, the probability it is behind door C is 2/3. Thus the probability it is behind door A cannot also be 2/3, as that totals 4/3, which is greater than 1. Timotiis - 87.114.33.159 14:09, 11 March 2009 (UTC)

For a fresh take on a classic problem, suppose the host has forgotten which door the car is behind. Nervously (he might be out of a job if he gets this wrong!), he opens one of the other two doors - and fortunately for him, there's a goat behind it! Mopping the sweat from his brow, he asks if you'd like to switch. It turns out that *now*, it's neither advantageous nor disadvantageous for you to do so - the odds are 50-50! -rzh

I shouldn't think so - the important thing is not that the host knew where the goat was, but that you now know where a goat is. Your original chance of picking the car was 1/3, so the chance the car was behind the other two was 2/3. As you now know it isn't behind one of the other doors, and the chance your original pick was correct hasn't changed, you still have a 2/3 chance of winning if you switch.

The literature is that Monty must know what is behind the doors for the probability of 2/3 to be right (you have skipped the case where the host opens the door containing the car accidentally). The other assumptions are needed too. If you are presenting the "Monty Hall" problem I feel you have to present something fairly close to the original - it does not need to be made more complex, as the beauty of it is its apparent simplicity.

Let's assume for simplicity that you pick door A. There are six scenarios:

Car behind A, host flips B. If you switch you lose.

Car behind A, host flips C. If you switch you lose.

Car behind B, host flips B. The host has flipped winning door.

Car behind B, host flips C. If you switch you win.

Car behind C, host flips B. If you switch you win.

Car behind C, host flips C. The host has flipped the winning door.

Each of these happens with probability 1/6. So the probabilities

P(host flips losing door & switching is good) = P(host flips losing door & switching is bad) = 1/3.

are equal. Thus if we condition on the host flipping a losing door, switching isn't advantageous.

Contrast this with the original version of Monty Hall. Here we have:

Car behind A, host flips one of the other doors. If you switch you lose.

Car behind B, host flips C. If you switch you win.

Car behind C, host flips B. If you switch you win.

Each of these happens with probability 1/3. So here switching doubles our chances. -rzh

For a different twist on the problem, think about this. You walk into the studio partway through the show. The host has just revealed a goat behind one of the doors, and you are not told which door the contestant picked originally. What is the chance you pick correctly? Timotiis - 87.115.129.80 13:19, 16 February 2009 (UTC)

I'm not sure if this is helpful, but think of the scenario of one hundred doors. 99 goats. 1 car. You pick a door, and then the host opens 98 doors. Should you switch? The answer is obviously yes. In 99% of cases, the host will have opened every door that is not a car for you. So, in 99% of cases, you would benefit from the switch.

Try it with 20 doors. 19 goats. 1 car. You pick a door, and the host opens 18 doors. Should you switch? In 95% of cases, the hose will have opened every door that is not a car for you. So in 95% of cases, you should switch.

In the original problem, it's only 66%. But it's still in your favour to switch -DevinB

My brain can only grasp the problem as a 50/50 success rate. However, running it through 1 million times, I get the following (Note my laziness with shifting the decimal to the right two):

0.333327% Correct Initially.

0.666673% Correct with Switch.

333327 / 1000000 initially Right.

666673 / 1000000 with Switch.

Being that it's 3 AM I may have poorly represented the problem. In code I set up an array of ints. I generated one random number to represent the initial choice. I randomly selected one of the ints ("doors") and set it to 1. This will represent the correct door. I then changed the remaining doors to 2, representing the losing doors. From that I set a 2 door that was not the selected number to 3, to represent the revealed door. If the selected door was 1, I increased the initial choice counter, if it was 2 I increased the switch door counter.

I acknowledge that the initial chance of getting the door right is 33%. However, once one of the wrong doors are revealed, you're left with only 2 choices(stay or switch), and 4 outcomes. 1) You stay and get it right. 2) You stay and get it wrong. 3) you switch and get it right, 4) you switch and get it wrong. That's 2 for right, 2 for wrong, 50/50.

An option is eliminated, so its chance of being the right one should be distributed amongst the unknown, correct? I know my logic is wrong, but why is it? Even in the case of 100 doors, the fact remains that you know one thing and one thing only: One of Two doors is correct. The numbers show that I'm wrong, and I trust them more than myself, I'd just like someone to help tell me why, or help me look at it the right way.

-Orc

A followup, since I kind of get it now. When you initially select one, you acknowledge that "this one has a 66% chance of being wrong", the host will reveal one wrong one, taking it out of the selection. This will leave you with the one you already marked as a 66% chance of being wrong (because those were the odds when you picked it), and another that is now only a 33% chance of being wrong. It is 5:30 AM and this is the only way that I can find peace in the results.

- Orc

Think of it this way: the way he always opens a wrong one other than the one you pick means that if you picked the right one initially, the remaining one that you can switch to will be a wrong one, which happens 1/3 of the time. If you picked a wrong one initially, which happens 2/3 of the time, the one you can switch to will always be the right one. It's not simply switching between one of three doors, but switching between winning and losing, and since you have a 2/3 chance of losing with your first pick, switching will give you a 2/3 chance of winning.

[edit] Resistor Grid

if we were to connect a power supply to the grid in a knights move pattern(assuming that we connect one negative terminal and one positive terminal) then we measure the voltage drop, and measure the amperage drop to calculate the resistance(we could use an ohmmeter, but this is usually more accurate).

for convenience, let the move be up two and left one.

this can be represented as:

up 2 left 1 up 1 left 1 up 1 left 1 up 2

here, the resistance would be 3(number of resistors the current must travel) divided by 2, and by 2 again. We half the resistance for each alternate possibility that contains the same number of resistors. This is because electrons can move here twice as fast when they have a second route to take. if we only had a 2x3 grid, then the resistance would be 3/2/2. (e.i. 0.75)

however when the size of the grid is increased to 4x5(the knights move in the centre) we have a list of other possible paths:

left 2 up 2 right 1 up 3 left 1 down 1

to a nearly limitless selection(try drawing it, the possibilities are almost endless), but when we introduce the limit of not being able to double back or visit the same point twice, we narrow it down quite a lot(just under a hundred, but my calculations aren't always perfect).

logically, we would divide 3 by how ever many possible paths their are, but this is not the case. when the path requires 5 resistors to move through, the resistance increases, so dividing by two is no longer accurate. we still need to divide, but by what? to obtain the number we divide by, we use the following algorithm/formula/whatever

1/(number of resistors) +1

this means that when the path is 5 resistors, we divide by 1.25(1/2/2 +1). please note that the path will always require an odd number of resistors.

using this logic, we can divide three as following:

3/2/2/1.25/1.25/1.25/1.25(etc.)/1.625/1.625/1.625(etc.)/1.15625/1.15625(etc.)

this will continue until we run out of paths. also, we can assume that since the number we divide by will always be greater than 1(we add one to it, remember?) that the resistance will never get larger. however, the resistance will always be greater than 0, because we never subtract anything from it. these two rules form together as follows:

the resistance will be above 0 and less than 3, and the resistance will be divided by a number greater than 1 but less than or equal to 2.

this should be able to be simplified by 10^-X, where X = is the number of available paths divided by number of resistors.

this applies to all grids large enough to accommodate the knights move.

since the grid is infinite, X is also equal to infinity(an infinite number divided by a smaller infinite number), so the resistance can be contained as:

 0.00000000000000000(an infinite amount of zeros)00000001

or, slightly over 0.

• But arent there an infinite number of paths? The path can go away from the second resistor for any amount of time and then go outside the other paths. IE the steps left*n down*n right*(2n+2)up*(n+1) left*n will always make a longer path (assume the marked nodes are as in the comic (right right up from one to the other)).--98.232.241.180 06:43, 17 February 2009 (UTC)

• For a grid, you can write the equation for the voltage at any node (in terms of nearyby nodes), and use 2-d discrete fourier transform methods to move toward an answer. avoid the "path" method. this method fails horribly for simple circuits, like a wheatstone bridge -- the middle resistor doesn't appear in the actual resistance equation, but by treating it as a set of parallel paths, it will. 71.32.45.51 06:15, 18 February 2009 (UTC)

• Also, "0.00000000000000000(an infinite amount of zeros)00000001" is not slightly over zero. It is equal to zero. It is also an incorrect answer to the problem (The correct answer can be found on the fora). 92.254.66.98 10:53, 18 February 2009 (UTC)

[edit] The Bridge

 C+D -> // 2 min
 D   <- // 1 min
 A+B -> // 10 min
 C   <- // 2 min
 C+D -> // 2 min
 ----------
 total 17 mins.

Alternatively

 C+D -> // 2 min
 C   <- // 2 min
 A+B -> // 10 min
 D   <- // 1 min
 C+D -> // 2 min
 ----------
 total 17 mins.

A slight variant of this puzzle is found in the Nintendo DS game Professor Layton and the Diabolical Box. The differences are it is phrased in terms of horses you have to take with you which you can only take 2 at a time (and ride one back), and they have speeds of 6, 4, 2, and 1 hours. However it is solved exactly the same way.

[edit] Coin Tosses 2

With a probability 1/2 [tail on the first toss] Bob will pay Sue $0.
With a probability (1/2)^2 [tail on the second toss] Bob will pay Sue $1.
With a probability (1/2)^3 [tail on the third toss] Bob will pay Sue $2.
...
With a probability (1/2)^{n+1} [tail on the third toss] Bob will pay Sue $n.
Therefore, the expectation value of how much will Bob pay Sue is:
<math>1/2 * 0 + (1/2)^2 * 1 + (1/2)^3 * 2 + ... = \Sum_{n=0}^{\infty} n (1/2)^n = 2</math>
So Sue should pay Bob $2 for the game to be fair. *ABC*

• The result of your sum is 1 and not 2 138.96.122.7
  • I don't think so, the terms of the sum are: 0, 1/2, 1/2, 3/8, ... The first three add up already to one. (Maybe you are missing the n inside the sum or something.) *ABC*
    • There shouldn't be a n inside the sum, I don't think. The 1/2 probability of getting 1 dollar includes the 1/4 probability of getting two dollars. You have to be successful in each iteration to get the next iteration, so really you just need to add the chance of getting each additional dollar. So value of the game=(.5)($1) + (.5^2)($1) + (.5^3)($1) + ... *Matt*
    • Actually your left term is different from your right term. In the left the terms are 0, 1/4, 1/4 ... In your rhs the terms are 0, 1/2, 1/2, 3/8...
    • It's just a geometric distribution. The sum is \sum_{n=1}^\infty n(1/2)^(n+1) = \sum_{n=1}^\infty (1/2)^n. ie. what Matt said, but if you stick the n inside the sum, the exponent must be n+1 (the probability of EXACTLY one head is 1/4, not 1/2). -- bradluen

• Solution 1: The infinite sum yields 1. (as stated by Matt)
• Solution 2: We can restate the problem the following way: Bob wants to play until he wins at least one time. Given this precondition we can already pay him in advance for his win. In this case all the coin tosses become independent. As Bob pays $1 for each win, Sue should pay the same to Bob for his (future) win. 138.96.122.7
• Solution 3: Recursively, the game gives a 1/2 chance of winning nothing, and a 1/2 chance of winning $1 and getting to play again. So if we call the expected value E, then E = (1/2)*0 + (1/2)($1 + E). This solves to E = $1.

• The solution cannot be $1 because the payoff will look like this for (Sue, Bob)

Heads: ( $0, $0) play continues (essentially Bob gives back sue her dollar)
Tails: ($1, -$1) Play stops
Heads, heads: (-$1, $1) Play continues
Heads, Tails: ($0, $0) play stops
Heads, Heads, Heads: (-$2, $2) play continues
Heads, Heads, tails: (-$1, $1) Play stops.
So Sue loses only if a tails occurs on the first toss, else she will always breakeven / win viceversa for Bob.

• • You say "only" as if it was a rare occurance... but that means that Sue loses half the time, breaks even 1/4 of the time, and wins 1/4 of the time... so she loses twice as often as she wins. But, when she loses, she always loses $1, and when she wins, she can win more than $1 (and averages to $2). So it's even (1/2 * $1 == 1/4 * $2), and the cost of $1 is fair. Phlip 11:52, 12 February 2009 (UTC)

• I think the simplest way to think about this puzzle is to assume that Bob and Sue keep playing the game forever. Then the situation becomes:

Every time a tails comes up (a new game begins), Sue pays Bob $x. Every time a heads comes up, Bob pays Sue $1.

Clearly, for this to be fair, x must be 1. --JDB

erm I'm just learning probabilities in school but the solution for the infinite sum, which I found logically to :be the solution of this problem( S = 1/2^n x n for n going from 1 to infinity) is Exactly 2 (the series seems to be convergent) :, and I found this computationally, which cannot be disproven that easily , sry ;p (atleast as far as 32-bit double :floats precision's goes, I mean...)

So that should be a definitive answer? I'm curious and eager to spread this so we need a consnsus here ; )

Simple c++ algorithm:

#include <iostream>
using namespace std;
int main() {
int i, inter;    //ITERations
double sum, aux; //and AUXiliary variable
while (iter != 0 ) {
    cout << "Insert num of iterations: (or '0' to exit)"; 
    cin >> iter;
    aux = 1;
    sum = 0;
    for (i = 1; i <= iter; ++i ) {
        aux /= 2;
        sum += aux * i;
    }
    cout << "Sum: " << sum << endl;
}
return 0;
}

You'll notice this algorithm alredy converges to 2 at a few iterations. 189.62.195.228 00:20, 14 February 2009 (UTC)

The problem is that Sue can win an infinite amount. Sue wins $0 1/2 the time, $1 1/4, $2 1/8, $4 1/16, $8 1/32... $2^n 1/(2^(n+2)). Or for each time she plays she wins 1/4 + 1/4 + 1/4 + 1/4 +... = infinity dollars on average. Wikipedia has a page on a similar problem.--98.232.241.180 07:22, 17 February 2009 (UTC)

• That is an other problem (St. Petersburg paradox). I have summoned some courage and added it to the front page as a variation of this game. I think it is more interesting anyway.
  • If you don't want to check the related wikipedia article, the solution is the same as above: the expected value diverges into infinity, which makes the problem a paradox. The solution to the paradox can be explained by the utility of money. Yeah if you play forever, you end up winning infinite amount of money. But infinite amount of money is not infinitely more useful than one dollar. If you could play a game where you pay $1 and have 1/10^40 chance to win 10^80 dollars, would you pay to play the game? I know I wouldn't.
  • I made a quick python script that simulates lots of games, and calculates the mean and standard deviation of the pots. Out of 10 million games, the average pot size was $13.52 but that doesn't mean nothing, because the standard deviation was $6283.88 :) I have no idea how much money I should ask from a friend to play this game:)
• Ok, I haven't read all of your solutions, but I did this with a simple equation. Define x to be the expected value Bob pays Sue (and thus the amount Sue should pay Bob). x=1/2*0+1/2*(1+x)=0+1/2+1/2x. thus, 1/2x=1/2, and x=1 -Emily

[edit] Smurfs and Gargamel

The smurfs agree among themselves that when the game begins, they will all check whether they see an odd or even number of red hats on other smurfs, and the first to be called on will claim that his hat is red if and only if he sees an odd number of red hats. At this point, each smurf knows the color of his own hat. If the first smurf was correct (has hat matched his claim) then there must be an even number of red hats, and if he was wrong there must be an odd number. If there is an even number, any smurf who sees an even number has a white hat, otherwise he has a red hat, and vice-versa.

-- Evan

• RE: Evan -- I'm not sure if this would work. They don't have any means of communication. They can see each other, but thats it. Plus, the amount of hats turned red is undefined. Meaning there is no base number to go off of.
  • I posted the problem, and Evan's solution is the one I was looking for. Maybe the problem is badly stated (in which case we should discuss improvements to the problem description). After the hats have been exchanged the smurfs can see each other. They can hence count the number of red hats (except their own ones). Suppose the first smurf yells 'red' because he has seen an odd number of red hats. Everybody should now know what color he has. If a smurf sees an even number of red hats he must have a red hat. Otherwise he still has a white hat. 138.96.122.7 19:20, 11 February 2009 (UTC)
    • The problem is that the other smurfs don't KNOW that "Red" means "odd number of red hats", since they can't communicate.74.14.228.170 20:16, 11 February 2009 (UTC)
      • They develop this strategy before the game. The problem states that the smurfs accept only "after a short discussion."
        • Objection withdrawn! -John 99.224.156.92 21:39, 11 February 2009 (UTC)

RE: Alternative 2. The first smurf calls out the colour of the smurf in front of him, he has a 0.5 chance of living and smurf 2 knows his own colour and smurf 3's. Smurf 2 then says his own colour in english if it is the same as smurf 3's. If smurf 3 has a different colour, smurf 2 calls out own colour in japanese (or with a terrible japanese accent if we assume Gargamel responds only to english). Smurf 3 then knows his colour and continues. -Corey

• This feels like cheating to me, since it adds extra bandwidth to the communication channel. Might as well allow him to pitch his voice to a frequency that encodes the colors of all the others' hats. The odd/even approach still works in this case, though: smurf 1 calls out 'red' when he sees an odd number of red hats; smurf 2 then knows his own hat's color based on whether he sees an odd or even number of red hats; for n > 2, smurf n learns his hat's color by comparing smurf 1's answer to the number of red hats he can see plus the number of red hats announced by smurfs 2 through n-1. --Evan
  • Evan - I know it does seem like it is adding an extra variable to the problem. I merely posted to get the discussion moving to see if anyone else has come up with a solution. However I don't believe your method will work for this version as each smurf can only see the colour of the smurf in front of him (behind him in order of choosing). -Corey
    • Only if you're proposing another variation; The original note2 says each Smurf can only see "the hats of the Smurfs in front of him" not "the hat of the Smurf in front of him." --Evan
      • Oh cool, that makes sense. Cheers.- corey

Another RE: Alternative 2. This is actually very similar to the main problem, but the smurfs need to store a mental variable of 'odd/even'. If the back smurf sees an odd number of red hats, he says red (doesn't matter if he lives or dies). All the other smurfs now know there are an odd number of reds remaining, so initialise var = odd. If smurf 99 can see (var) red, he says white and we proceed. Otherwise he says red, the other smurfs flip the value of var, and we proceed. Similarly if the back smurf saw even, he says white and the other 99 smurfs initialise var = even, and proceed as above. -- TLH

Solution to Alternative 3: Call an assignment of hat colors to Smurfs a pattern and call two patterns equivalent if they are the same on all but finitely many hats. This equivalence relation partitions the set of possible patterns into equivalence classes. Note that by observing the hat colors of all the other Smurfs but not his own, each Smurf can tell which equivalence class the pattern belongs to -- his own hat color is irrelevant because patterns which differ on finitely many Smurfs are equivalent. The Smurfs invoke the axiom of choice to select (and agree on) a distinguished representative pattern for each equivalence class (that is where the magic is required). Once the hat colors are assigned, each Smurf determines the equivalence class of the pattern by examining only the hats of the other Smurfs, then says the color of his hat in the preselected distinguished representative of this equivalence class. By the definition of the equivalence relation, only finitely many Smurfs get their hat color wrong.

The smurfs build a line. It starts with two smurfs. The third smurf sees if they have the same or a different color. If it is the same he goes left of them, of they have a different color then he goes between them. The following smurfs will do the same. At some point there will be two colors in the line and from that point on every following smurf has to go between the to colors. So he doesn't have to know his hats color, but the border between red and white hats will be left or right of him. In the end you have a line that is devided in two colors. Every smurf but the last two ones know the color of their hats, because its that of their neighbours.

• Course, the problem with risking any finite number of Smurfs to find out the code is ... what if Smurfette is in the finite set? If she goes, their entire species is lost. So they have to stipulate that she is asked later (or earlier depending on the version of the problem). - Derrill

[edit] Prisoners

• The solution to the problem as stated is to have one prisoner designated the 'counter'. The light is stated to be in the 'off' position to begin with. Any prisoner can turn the light 'on' if they've never flipped it before, but only the counter can turn it off. Once the counter has turned off the light 99 times, then 99 prisoners and the counter have been interrogated.
  • Without knowledge of the light's starting position, on or off, then the counter cannot be sure the first time they turn off the lightbulb if they have counted a single prisoner or no prisoners. The way around this is to have everyone turn the light on twice. The 198th time they flip the switch off, they will have either counted the 99 prisoners who have flipped the switch on twice, or 98 prisoners who have flipped the switch on twice, and one who only flipped it once (but was nevertheless interrogated)

There are multiple solutions, this PDF from a Berkely student seems to be comprehensive. [2]

• The referenced pdf contains the solution. However their initial problem is different. Here the time between interogations is random whereas in the pdf the time is fixed to be one prisoner a day. 138.96.122.7
  • I added the alternative version (1 prisoner a day) to the front page. 138.96.122.7 19:08, 11 February 2009 (UTC)
    • It doesn't really make a difference to the standard solution (except that the prisoners know not to speak up until at least 100 days have passed — and their method will require much more than 100 days anyway).

• This PDF from a Stanford mathematician is more comprehensive, and addresses many variations, including where prisoners do/don't know the current time.

Isn't there a simple solution where everyone counts ? I would think that what you need to track is a change in state, not who did what/when. So what you do know is that the second time anyone goes in for interrogation, they change their state from new to interrogated. So you just need to count those unique events

• If this is your 1st time in the room, leave the light off
• If this is your 2nd time in the room, leave the light on
• If this is your 3rd or later time in the room, leave the light off
• Keep count of the number of times you see the light on,
  • When you get to >100, everyone has been in the room twice.

I can't see how that will work... there will only ever be 100 occasions in all when the light is left on (namely, after each prisoner's second visit) so it's vanishingly unlikely - one in a googol squared I believe... - that one prisoner will see all 100 of those occasions.'

Unknown initial state

The papers mentioned give a strategy for an unknown initial state of the switch, but only for the case where one prisoner is taken to the room each day (trivially, the first prisoner turns it off to begin with). Our problem doesn't give prisoners the knowledge of who the first prisoner is. My strategy:

Choose a counter (the others are drones).

The drone operates in 3 stages:

Stage 1: Do nothing. Move to stage two after visiting the room with the light on.

Stage 2: If you visit the room with the light off, turn it on and move to stage 3.

Stage 3: Do nothing.

The counter:

Start an internal counter at 0.

If the light is on when you arrive, and you turned it off last time you were in the room, increase your internal counter by one. On all visits, toggle the light.

Note: Drone stage 1 ensures that if the light began in the on position, the counter knows about it and was able to reset it. The counter always toggling the light allows drones to move both from stage 1-2 and stage 2-3 (and so be counted).

-Matt

[edit] Pirates

P1 will propose that all odd-numbered pirates (p1, p3, ..., p99) receive 1 gold piece. Each odd-numbered pirate will vote in favor of this proposal, so it will be accepted.

We can reach this result by induction:

In general, a pirate proposing a division will always vote for his own proposal (Survival). If pirate n is able to propose a division D(n) (worth W(n) to himself) that would be accepted, then his survival is not in doubt. Define M(n, i) as the most that pirate i can expect to receive when there are n pirates left. Pirate i will vote 'no' on any division proposed by pirate n that gives pirate i less than M(n-1, i) (due to greed) or the same (due to bloodthirstiness). He will vote 'yes' on any proposed division that gives him more.

1. D(100) and D(99) exist, since in each case the lead pirate can propose that he keep all 50 gold, and his 'yes' vote will ensure acceptance.

For n < 99, if D(n+1) through D(100) exist, then D(n) exists iff pirate n can 'buy' the votes of 50 - ceil(n/2) other pirates. 'Buying' the vote of pirate i consists of paying him more than M(n-1, i). Due to greed, a pirate will choose the 50 - ceil(n/2) cheapest votes, propose to pay the minimum M(n-1, i) + 1 on each, and keep the rest for himself. At most, pirate n will be able to keep ceil(n/2) gold.

2. D(98) exists, since D(99) and D(100) exists and M(99, 100) = 0 (when there are 99 left, p99 keeps it all), so p98 can buy p100's vote for 1 gold and keep 49. This makes M(98, 99) = 0 and M(98, 100) = 1.

3. For even n with 1 < n < 97: if M(n+1, i) = 0 for even i and M(n+1, i) > 0 for odd i, then there are exactly 50 - n/2 pirates whose votes can be bought for 1 gold. D(n) will then consist of 1 gold for each other even-numbered pirate and the rest for pirate n. This makes M(n, i) = 1 for even i and M(n, i) = 0 for odd i.

4. For odd n with n < 98: if M(n+1, i) > 0 for even i and M(n+1, i) = 1 for odd i, then there are exactly 50 - ceil(n/2) pirates whose votes can be bought for 1 gold. D(n) will then consist of 1 gold for each other odd-numbered pirate and the rest for pirate n. This makes M(n, i) = 0 for even i and M(n, i) = 1 for odd i.

5. By induction, D(1) consists of 1 gold for each other odd-numbered pirate (49 of them), and the remaining 1 for pirate 1.

Beyond 100

1. With 101 pirates, the first needs 51 votes, and 50 odd-numbered pirates' votes can be bought, if he keeps none for himself. If his proposal failed, there would be 100 pirates left, and those pirates would get nothing.

2. With 102 pirates, the first needs 51 votes, and 51 pirates votes can be bought! He can buy any 50 and keep nothing.

3. With 103 pirates, the first needs 52 votes, but only has enough gold to buy 50. He dies.

4. With 104 pirates, the first needs 52 votes . . . and pirate 103 doesn't have an acceptable proposal, so he will vote yes for nothing! He dies too if this proposal fails. 50 out of the same 51 pirates' votes from step 2 can be bought, bringing the total to 52.

5. With 100 + n pirates, where 2^i < n < 2^(i+1) for some i > 0, the first needs 50 + ceil(n/2) votes. He can buy 50, and has n - 2^i free votes: his own and the votes of pirates 100 + 2^i + 1 through 100 + n - 1. But from n < 2^(i+1) we get n - 2^i < n/2 <= ceil(n/2) and there aren't enough votes. These pirates die.

6. With 100 + 2^(i+1) pirates for some i > 0, the first needs 50 + 2^i votes. He can buy 50, and has 2^i free votes: his own and the votes of pirates 100 + 2^i + 1 through 100 + 2^(i+1) - 1. This is enough for him to survive and take nothing.

So at 200 starting pirates, they'll die until there are 164 left.

--Evan

Shouldn't the next "live" after 108 be 116 (50 bribed, plus 109 to 116 don't want to die)? Similarly, shouldn't the live numbers be 100 + 2^n? -- bradluen

Yes, thanks! I've fixed it. --Evan

Won't pirate 103 vote no always? He's not able to survive or make money, so he should go for bloodthirstiness and vote no to kill off 104. --Aegeus

 No, because he *can* survive by voting yes along with 104 and the 50 other pirates that are getting gold. --Evan

There is an implicit assumption in this proof. We have "Pirate i will vote 'no' on any division proposed by pirate n that gives pirate i less than M(n-1, i) (due to greed) or the same (due to bloodthirstiness). He will vote 'yes' on any proposed division that gives him more." where M(n,i) is the *most* he can expect. This assumes that if pirate n-1 could bribe either pirate i or another pirate for, say, 2 gold pieces, pirate i could be bribed for at least 3 gold, but not for less. However, it is ambiguous whether or not this would actually happen. Would pirate i accept a bribe of 1? How about of 2? Rejecting and accepting the pirate n's proposal both do not have defined weights in the pirate's priority list. Accepting guarantees them money, but rejecting gives them the *possibility* of getting more money (and more deaths).

Now, this case never actually arises, so it does not affect the outcome, but I still find this to be a minor problem with the provided solution. Interestingly, this case does arise if a tie did not count as an acceptance. --Ezbez

I think what Ezbez said (or a related concept) also needs to be considered in the case of 104 or more pirates with the problem as stated.

Note: I'm reversing the numbering so that the highest numbered pirate is the one making the proposition. That way if they are killed, everyone keeps their number and the solution is equal to the case with fewer pirates to start with. It was already established that 101 would give a coin to pirates {odd 1..99}, and so 102 needs to give a coin to 50 out of {even 2..100, 101}.

Now 104 proposes an assignment to some 50 of {1..102}. 104 and 103 will vote for the proposal, to stay alive, as will 102 if he's assigned a coin, for greed. Anyone in {1..102} that is not assigned a coin will vote against, for bloodthirst. What should the rest do? They know that if they vote against, 104 and 103 will be killed, and 102 will make a proposition that will be accepted. However, they don't know exactly what 102's proposition would be.

102 can choose any 50 from {even 2..100, 101} only. Obviously anyone chosen by 104 in {odd 1..99} should vote for 104's proposition. The even ones and 101 pose a problem: it isn't clearly defined what they should decide. Would they choose the certain coin from 104, or a 50/51 chance (although 102's probability distribution could be anything) of getting a coin from 102, plus having two guys killed?

If we extend their stated greed to estimated expected value, they should always go for the coin now. That would allow 104 to choose any 50 from {1..102}, 108 from {1..104}, etc.

Without knowledge of them doing this reliably, I guess 104 couldn't take the risk of getting killed. That would mean that 104 can only choose from {odd 1..99, 102}. This too is different from what was previously said, although "50 of the same 51 pirates' votes from step 2" is quite near. Similarly, 108 could choose from {even 2..100, 101, 103, 104} and 116 from {odd 1..99, 102, 105..108}. --Nix

100 pirates: My thoughts are the same as been discussed. p1 offers gold to 49 other pirates, and keeps one for himself. I was thinking "wait, the other pirates will be bloodthirsty and kill p1, since p2 would offer them a similar deal". However, they would all be rational enough to know that this would create a chain reaction that would eventually get them killed (except the lowest few, but they wouldn't be enough to turn over the initial vote).

Actually, now I'm thinking that p50 (and some better ranked) may be able to vote no on the first few resolutions to get more money or kill more pirates without losing their life to the same logic. I'd have to think about it more --Case

100 pirates: I'm thinking the bloodthirstyness would give the following scenario: No matter what p1 proposes, the 51 final pirates would vote no, same goes for p2-49. When p50 makes a proposal the final 26 pirates will vote no, same goes for p51-74. Then the final 14 pirates would vote down and kill p75-86. Now the last 8 pirates will band together and murder p87-92. 5 pirates will then vote down p93-95. The next two pirates, p96 and p97 fare no better. p98 is killed by p99 and p100. Now there are only two pirates left and p99 proposes to give himself the entire treasure. Since he has 50% of the votes, he gets the entire treasure.

Being "perfectly intelligent, logical and rational" (and this being common knowledge), wouldn't they see the next step coming and so determine that voting against will only help you get killed, never mind getting no gold? This should be easiest to see in the case of three or four pirates left. Assuming p98 proposed to give p100 some coins (1), why would p100 vote to kill p98 as that would lead to getting none from p99? Now, if you had them not care about how much they get, p98 would get killed but still, p97 wouldn't, since p98 would have to vote yes to save his own life. --Nix

Perhaps I'm misreading/oversimplifying this, but wouldn't the top ranked pirate get all of the coins? If everyone cares about survival first, the top ranked pirate will always vote for himself, and since a pirate can only die by being the top ranked living pirate, every pirate will attempt to keep themselves from being the top ranked living pirate, meaning that they'll vote to follow the top ranked pirate. The top ranked pirate, realizing this, will give all of the gold to himself on the wealth priority, and the bloodthirst priority will never come into play.

Doesn't D(-1) matter? --Mark

"The pirates are perfectly intelligent, logical and rational." I think this is a hilarious proposal in itself, to say nothing of an intellectual discussion on their methods of profit distribution. Par for the course for XKCD, though; I love it. :)

Think of it this way: except for the last one or two pirates, if all the pirates before them are killed the dilemma for all the rest of them is essentially the same as for the initial head pirate. They would all know that if they repeatedly vote for deaths it will bring it to themselves and their own death. Unless the last so many pirates are able to collude and make a deal ahead of time they have no choice but to vote yes whatever the first pirate says.

Oops, was mistaken there, I realized earlier. As was said earlier if it gets to the second to last pirate he can keep everything, but you can extrapolate backwards from there. When it gets to pirate 98 he can offer the last pirate one coin, and thus get his vote (as otherwise he would get nothing), and one additional vote is all he needs. Then for pirate 97 he also only needs one additional vote, but he can't make the same offer, as then the bloodthirstiness would come in since pirate 100 would get 1 coin either way but would rather have an extra pirate die. However he doesn't need to offer an extra coin, as he could instead give him nothing and offer one coin to pirate 99. Pirate 96 need two extra votes, which he can get by offering one coin each to pirates 98 and 100 (it doesn't matter that they would also get that coin from some of the later pirates because they know pirate 97 has a winning strategy under which they get nothing). Going this far the pattern seems clear: any pirate would have to offer one coin each to every other pirate, starting with two pirates after him. Therefore the solution is: The 1st pirate would keep 51 coins, and give away 49 coins, one each to every other odd numbered pirate. However this only raises the question about why perfectly intelligent, logical, and rational pirates would agree to this method in the first place, since half of them would always be guaranteed to get nothing, the rest other than the head pirate to get only one piece of loot each, and there would be a bloodbath if they acquired loot consisting of only a small number of coins.

[edit] Cyclic List

I'd use a tortoise+hare solution.

In pseudocode:

loop = true

Tortoise = first object in linked list

Hare = first object in linked list.

Try:

While (Tortoise != Hare) do

{

Tortoise = Tortoise.next

Hare = Hare.next.next

}

catch nullpointerexception {loop = false}

print "There is a loop:" + loop}

Basically, Tortoise moves through the list one item at a time. Hare moves through two items at a time. If there's no loop, Hare will run off the end of the list and throw a NPE after NumEntries/2 iterations. If there is a list, Hare will enter it and loop it until Tortoise catches up to it or it catches Tortoise.

As for how to find WHICH entry is the first in the loop... I don't suppose I can just cheat and have Tortoise mark each entry as it goes past, eliminate hare entirely, and just have tortoise check for it's marks? The problem is, that requires changing the objects, which is generally cheating in puzzles like this. -John 74.14.228.170 20:28, 11 February 2009 (UTC)

Oh, duh, gotta run Tortoise and Hare's advancements once each before the While starts, or you fall out immediately. But still!

• no. marking is not allowed.
  • yeah, that's to be expected. And I suppose, since it's a proper linked list, you can't cheat and have each entry somehow know where it is in the list?
    • In case you haven't seen the solution (or don't want to see it). No: you can't know the position. The solution is extremely simple and elegant.

Here the same solution (just for the predicate) in Scheme:

 (define (cyclic? L)
   (define (tortoise/hare t h)
      (or (eq? t h)
          (and (not (null? h))
               (not (null? (cdr h)))
               (tortoise/hare (cdr t) (cddr h)))))
   (if (null? L)
       #f
       (tortoise/hare L (cdr L))))

• Here is a solution for the second part of the problem (finding the first element where the list starts to cycle). We assume that the list is cyclic (simply run cyclic? before). The idea of the following algorithm is, that we have one pointer p1 starting from the beginning and one, p2, running inside the loop. The difficulty is to "sync" these two pointers so they will meet each other at the first possible list-element.
  Now reusing the 'cyclic?' idea we have a tortoise and hare. When they meet the tortoise has advanced by n steps, whereas the hare must have taken 2*n steps (it is twice as fast). Set p2 to be equal to the tortoise's pointer. (Simply think of p2 as having advanced by n steps). If we advance p2 by another n steps it will have done 2*n steps (similar to the hare). If we start another pointer p1 at the beginning then p1 and p2 will obviously meet. At the very latest p1 and p2 will both advance by another n steps. However, as p1 and p2 advance at the same speed they might meet earlier at the very first element of the cyclic list.

 ;; L must be cyclic.
 ;; returns the list where tortoise and hare meet.
 (define (cyclic L)
    (define (tortoise/hare t h)
       (if (eq? t h)
           t
 	    (tortoise/hare (cdr t) (cddr h))))
    (tortoise/hare (cdr L) (cddr L)))
 
 (define (first-cyclic L)
    (define (iter l1 l2)
       (if (eq? l1 l2)
           l1
           (iter (cdr l1) (cdr l2))))
    (iter L (cyclic L)))

[edit] Two Beagles

Solution: 1/3, because there are four equal-chance possibilities at first (MM, MF, FM, FF), the shopkeeper narrows it to three (MM, MF, FM), and one of these three is MM. -- dazmax

Further Clarification: When she shopkeeper says that one of them is male we do not know which is male the first or the second in the set. This is why HAVE to treat these as a pair. These can be described as MaleA(Ma) or MaleB (Mb). At this point we can establish all possibilities. There is only one possible female so we cannot account for two:

1. Ma + Mb 2. Mb + Ma 3. Ma + F 4. Mb + F 5. F + Ma 6. F + Mb

There only two out of these six which are all male, options 1&2. Hence 2/6 reduces to 1/3.

-ttremblay

Perhaps you should consider that when the shopkeeper asks the guy who's giving them a bath, he will only check both if the first he checks is a female (assuming he's a rational, efficient guy). So it's either male first, then a 50% chance of another male, or Female First, and the next is a male (meaning a 0% chance the other is a male, as we know it's a female). Logically then, there is a 50% chance that the other beagle is a male.

I believe.

• You believe wrongly. Whether the bather checks one or both puppies is irrelevant - the information he imparts to the shopkeeper is "at least one puppy is male". There are four possibile sets of two puppies - MM, MF, FM, FF - and since at least one is male, we know you don't have the FF. That means that you have either MM, MF, or FM. Of those, the "other puppy" is female 2/3 of the time. -John 99.224.156.92 04:08, 15 February 2009 (UTC)

I think there is some confusion as to combination vs. permutation here. The order of the beagles is irrelevant; MF would be the same as FM (to be further called "one of each"). We know that it's not FF, so that leaves MM and "one of each". Two equally likely choices, 50%.

• This is actually a good way to see why it's 2/3. Like you say, it's either "both male" or "one of each". But "one of each" comes up twice as often as "both male", precisely because there are two orders of it. (You can try this with flipping pairs of coins, for a nice experiment.)

i'd like to say that the logic of this eludes me. if we have one puppy of an unknown gender, he has a 50% chance of being a particular sex. now we have two puppies, each with a 50% chance of being a particular sex. it is true that there is a 33% chance of any one configuration (both male, both female, or one of each), but each puppies sex is independent of the other, they each, individually, still have a 50% chance of being male, now that we checked one, it doesnt affect the initial probability that any given puppy of unknown gender is male. we essentially eliminated the set. all we have now is one puppy of unknown gender, regardless of what gender the other one was. if i am wrong i don't understand, but would like to know where i went wrong

• it is true that there is a 33% chance of any one configuration (both male, both female, or one of each). That is the mistake. They do not have equal chances, because MF and FM both have the same chances as MM and FF.

  Let's use hard figures: First puppy will be either Adam(M) or Betty(F), 2nd puppy will be either Charlie(M) or Daisy(F). There are 4 possible, equally probable possibilities:

  • Adam & Charlie (MM), 25%
  • Adam & Daisy (MF), 25%
  • Betty & Charlie (FM), 25%
  • Betty & Daisy (FF), 25%
• There's one situation that yields MM (25%), one FF (25%), and TWO that yield MF (50%). In our problem FF has been eliminated, so there's three situations; one that yields MM (33%), and two that yield MF (66%).

Here's a more intuitive way of thinking about it: what the bather has told us, by saying that at least one of them is male, is equivalent to just saying "they are not both female". And what the question is asking, by asking what the probability that the other is male as well, is equivalent to "what is the probability that they are both male". So read the question in full as "what is the probability that both dogs are male, given that they are not both female?" and it is much easier to see why 1/3 is the correct answer. - Adam

• so, lets look at the case of a lazy checker. (you can apply this two the N dog case as well to make it more tedious, but obvious)

with a 50% chance, the first dog was the first male found with a 50% chance, the second dog was the first male found (1+ males found as premise) if the first dog was male, there is a 50% chance of a second male. if the second dog was the first male, there is a 0% chance of a second male. so, in 100 cases, 50 would have found the male first. 50 second. of these cases, 25 would have two males. this is 25 cases with two males, 75 cases without. or 1/3rd of the cases.

An interesting corollary is the situation where the two dogs are completely indistinguishable except for gender; that is, they behave like particles and Heisenberg applies (always a reasonable assumption for dogs, I know). In this case, the probability is indeed 50% because the FM and MF cases are treated as the same. 76.190.157.141 06:48, 2 March 2009 (UTC)

CORRECT SOLUTION: 2/3. The order of the puppies is irrelevant, so the different options are MM, MF and FF. It is obviously not FF. We now have two possibilities: MM and MF. I will now label the two male puppies Ma and Mb. So our options are MaMb or MF. The person bathing the dogs checks to see if one of them is a male. He is either looking at:

• Ma, and so the other is Mb.
• Mb, and so the other is Ma.
• M, and so the other is F.

Thus the probability of it being MaMb (ie MM) is 2/3.

Unlike particles, these dogs do not cease being distinct entities because the only thing you know about them is whether they are male or female. MF and FM are always different, though in permutations you count them as two instances of the same category. That doesn't mean you can ever ignore them.

Specifically, the three possibilities are MF, FM, and MM, which we know are all equally likely because we assume each dog initially had a 50% chance of being male or female. Which dog the checker looked at is irrelevant; in fact, why not assume he looked at both and just answered the question honestly (i.e., at least one was male, but he's not telling what the other was)? Regardless, all three possibilities are equally likely, so the solution is: 1/3. 76.190.157.141 02:16, 5 March 2009 (UTC)

Wouldn't it be a 50/50 chance? The bather has said that one of the dogs is male. Therefore the probability of whether both dogs are male depends only on the second dog, which has a 50/50 chance of being male or female.

Yes, it's 50%. One puppy is male, so the question becomes "What is the chance that the other puppy is also male?" There is ONE puppy of unknown gender. The chance of one unknown puppy being male is 50%.

Think of it this way. You have two boxes, each box has one puppy in it. You open one box and see that the puppy inside is male. What is the chance that the puppy in the other box is male? 50%

A reasonable analogy, except that it fails to consider the possibility that the first box opened contains a female, and the person checking had to proceed to the second box to check that one. Essentially, yes, there is a correlation between the answer received over the phone and the gender of the second puppy. It collapses out the possibility that both puppies are female, but that's all. It does not assure you that the first puppy checked of the two is male. --Mark

Well I think the answer could be 1/4. Look CAREFULLY at the question the shopkeeper asked, and at the gender of the person being asked. One what? One gendered entity in the room? If so, the answer is automatically yes because the person being asked is male. So no information is gleaned about the dogs, and the chance of both dogs being male is 1/4. -- TLH

Ok since this is a "puzzle" and not a real situation, of course the bather isn't going to say "one" or "both" are male. he answers the Boolean question with a Boolean answer. given that ONE of the dogs is male, what are the chances that the other dog is male? Mind you, the bather could logically have checked BOTH dogs at the same time (which is why the ordering does not matter!) You have two pennies, what are the chances the other one comes up heads if one comes up heads? it's all very cute to claim that there COULD be Betty and Daisy, but in actuality why would there need to be two discreet females? Assume that the first dog (in a one dog at a time bather lookup) is female. The answer is still the same (yes, at least one is male). Now assume the bather checked the male first (and if so, why would he bother checking the second one since he was going to be a Boolean smart-ass anyhow?)... the answer is still the same. the question is essentially "what are the chances of a single dog being male or female" --- now hear me out! When you talk about genetics or other such statistical things, in every other circumstance if you say "this thing has a 50% chance, what is the probability that two discreet occurrences have the same outcome?" IE one male, one female, or two males, etc - in all cases where one outcome is NOT known, the answer would be 1/3rd. (funny how some of you are getting that confused here!) - and that is why this is a tricky problem. Because the first instinct is to say 1/3rd if you've ever worked on blue/brown eye charts or gender of children charts in school.

here's another thing to bring this home: John has two children. What are the chances that 1 is a boy and one is a girl? (answer, 50%) what are the chances that both are boys? 25%. right? i was corrected here, the number of outcomes is three but one is more likely hence 25%.

But here, we say "john has two children, at least one of which is a boy. What are the chances he has two boys?" the answer is 50%! --genewitch

[edit] String Burning

You have two ropes that take half an hour each to burn, but burn at a completely variable, unpredictable rate. How can you accurately measure out 45 minutes using these two ropes?

--dunno if this is hard enough, but its fun

A. Burn one normally. 30 mins.

Then ignite the other at both ends - however the variability goes, the two parts meet after 15 minutes.

Murk

Is the question worded wrongly? "Each piece of string takes one hour to burn". --Luke

As stated (with 2 1-hour ropes) 1)light both ends of rope A, and one end of rope B, simultaneously. 2)after 30 min, when rope A finishes, light the unlit end of rope B. 3)after 15 more min, rope B finishes. --Pabo 00:37, 13 February 2009 (UTC)

You light one string at both ends, and the other at one end. Wait for the first string to burn up, then light the other end of the remaining string.

The first string will take 30 minutes to burn, at which point the second string will have 30 minutes left to go. Lighting it at its other end will reduce this to 15 minutes, for a total of 45 minutes.

--Evan

I think this puzzle should be rephrased in the XKCD way[3]:

You have 2 pieces of string of different, unspecified length, and some matches. Each piece of string takes one hour to burn. There's a guard who stabs people who try to fold the strings in half.

Using only the matches and the strings, measure 45 minutes. --Andras

Ill offer the guard two nice pieces of string if he will tell me when 45 minutes is up. ( he has a watch to check when his shift ends )

Another solution: light rope A at both ends and somewhere in the middle. When one pair of burning meets, light one end of rope B; when the other pair meets, light the other end of rope B. When the two burning parts meet on rope B, it's 45 minutes. (First rope gets 15 minutes on average, the second rope gets 30 minutes and takes the average for you.)

Note: the original solution is this one in the limit as "somewhere in the middle" approaches one of the ends of rope A.

Lay a very large number of matches end-to-end. Light both ends of rope A and one end of the match chain. When rope A finishes, count how many matches have burned. Burn half that number more, and it's been 45 minutes. This method is only guaranteed to be precise within one match-burn. I'm just adding it so there can be a lateral thinking solution along with the quantitatively better ones. --Michael

Wind the two ropes together.Cut of exactly 1/4.Light it at one end.- This solution only works for some instances, and has a big margin of error :) --Balazs

Do the matches have a constant burn rate? If they do, just burn a rope at one end and keep burning matches (always starting the next one once the previous one finishes) and when the rope is done multiply your number of matches by 0,75. --Felix

[edit] Magic Watch

Let 1 stand for the proposition that the car is behind door number 1, 2 that it is behind door number 2, and 3 that it is behind door number 3. Let Y stand for the proposition that a yellow flash means yes and B stand for the proposition that a blue flash means yes. Two questions (with non-english syntax) that will let you determine the right door are:

"Is it the case that (1 and Y) or (3 and B)?"

"Is it the case that ((1 or 2) and Y) or ((2 or 3) and B)?"

If the car is behind door number one the yellow light will flash for both questions. For door number 2 the light will flash each color once and for door number 3 the blue light will flash twice. I wish I had been first to post one of the harder ones, but I do what I can. -- NHUP (New Hopefully Unique Pseudonym)

• What? The two questions you propose don't sound like yes or no questions, and even so would require the above paragraph about what yes and no mean. Since you only told us that we had two questions, an explanation of your questions shouldn't be allowed. (In any case, the solution might be fine if you explain it in simple english.)
  • They're yes or no questions. They're symbolic logic statements that evaluate to either TRUE or FALSE - and he's asking the watch if they're TRUE. -John
  • As John said, they are yes or no questions, just like "It it the case that the sky is blue?" is a yes or no question. They don't, strictly speaking, require the explanatory paragraph, but they would be significantly longer and harder to make sense of if you wrote them out in totality. That's why I wrote them out as I did. -- NHUP
• Why would you need "Y" and "B"? They're simply "yes", and being ANDed, and anything AND yes is just the anything. If you write the questions as #1: "is it behind 1 or 3?" and #2: "Is it behind (1 or 2) or (2 or 3)?" you will get the same answer... except that the second question will ALWAYS result in a yellow flash, no matter what, because either 1, 2, or 3 is true, meaning either (1 or 2) is true or (2 or 3) is true, meaning that "(1 or 2) or (2 or 3)" is always true. -John 99.224.156.92 14:25, 13 February 2009 (UTC)
  • "Y" and "B" aren't simply yes. On days when a yellow flash means yes "Y" is true and "B" is false. On days when a blue flash means yes "B" is true and "Y" is false. Certainly anything being ANDed with a true statement is always itself, and anything ANDed with a false statement is always false. That's the point. The (Proposition 1 and Condition) or (Proposition 2 and not Condition) format allows you to effectively ask a different question depending on whether the Condition is true or false. In our case this effectively allows us to ask different questions on days when blue means yes and days when yellow means yes. -- NHUP
  • Ah ha! I reread what I wrote and it finally penetrated. I wrote "Let Y stand for the proposition that Y means yes and B stand for the proposition that B means yes", which isn't very helpful. My mistake. I'll edit it to say what I actually meant. Sorry about that. -- NHUP

Another solution (a little easier I think):

Your two questions:

"If I ask you if behind door number 1 is a car, will you turn blue?"
"If I ask you if behind door number 2 is a car, will you turn blue?"

If it turns blue on the first one, then the car is on door number 1.

If it turns blue on the second one, then the car is on door number 2.

If it turns yellow on both, the car is on door number 3.

-- Andrés

• This solution is just a generalization of the old one about the liar and truth-teller twins. If you get n questions, you can always phrase them in this way to find out n pieces of information, and (like in this case) can often use process of elimination to get the last one, if there are n+1 pieces of information to be had.

• Your solution should read "If it turns the same color on both questions, the car is on door number 3. Proof:

Let your first question be labeled 'x' ("If I ask you if behind door number 1 is a car, will you turn blue?") and the second one 'z'.

case 1: car-1, blue=yes x-b z-y

case 2: car-2, blue=yes x-y z-b

case 3: car-3, blue=yes x-y z-y

case 4: car-1, blue=no x-b z-y

case 5: car-2, blue=no x-y z-b

case 6: car-3, blue=no x-b z-b

your logic stands unless the car is behind door 3, and blue means no. therefore, when the same color flashes, the car is behind door 3. --psolms

• • No, you are wrong... it's impossible that it turns blue on both questions, since if it turns blue it means the car is on the door the question refers to. It's really a lot simpler that the way you put it. You can look at each question separately, so there are only 4 cases (blue means yes/no, car in behind door or not). In case 6, when you ask question x it would not turn blue: If you ask the question "Is the car behind door 1?" the answer would be no, since it's on door 3. Because blue = no, it would turn blue. So the answer to the question "If I ask you if behind door number 1 is a car, will you turn blue?" is YES. And yes = 'yellow'. So it would turn yellow, not blue. -- Andrés

This is a good solution because it actually can solve the problem with 4 doors. In general, to solve the problem with 2^n doors requires n questions.

- Dan Loeb

Another solution I thought of that plays around with the puzzle's interpretation:

1. First ask the watch: "Is the car behind an odd-numbered door?"
2. Then ask the watch: "If the car is indeed behind an odd-numbered door, is the car behind the first door?"

Explanation: The first question results in either a blue or yellow flash, lets call it color A.

The second question results either in a blue, yellow or no flash: The question is either a yes/no question or not a yes/no question (actually: not a question at all), depending on the car being behind an odd-numbererd door or not. As the watch cannot answer a non yes/no question, it will not flash.

(You might consider this a question within a question, but stating "If I ask you if behind door number 1 is a car, will you turn blue?" in one of the earlier solutions is also two questions in one).

If the watch doesn't flash the second time, the car is behind door #2,

Otherwise:

If it flashes color A, the car is under door #1

If it flashes the other color, the car is behind door #3

-Koos G.

The second question is still a yes/no question, just an if-then one. I know you phrased it "If X, is Y true?" but the only way I can think of how to interpret that is "Is it the case that 'If X then Y'?" In that question, there will always be a flash. Unfortunately, Y does not depend on X here, and in fact X can be determined to be true or false. Since it is false, the if-then statement is always true.

So if the car is under DOOR 1: Yes, yes DOOR 2: No, yes DOOR 3: Yes, no

Therefore if it flashes the same color twice, it is behind door one. Unfortunately, if it flashes two different colors, there is no way to tell whether it is behind door 2 or door 3.

• Wait... We don't know if Blue=Yes or if Yellow=yes. This doesn't matter if the car is behind door #1, because it'll be the same colour twice, but what if this happened:

"Is the car behind an odd-numbered door?": Yellow "If the car is indeed behind an odd-numbered door, is the car behind the first door?": Blue

What do you do then? -Arca

Since it wasn't stated that the game show had a time limit, on Day 1 ask the following two questions:

Is a car behind doors 2 or 3? Is a car behind doors 1 or 2?

If the light flashes the same color for both questions, the car must be behind door 2, if it flashes different colors, it cannot be behind door 2, see below.

On Day 2, ask the following questions:

Is a car behind doors 1 or 3? Is a car behind doors 1 or 2?

Once again, if the light flashes the same color after both questions, the car must be behind door 1. If it flashes different colors, the car cannot be behind door 1 or 2 (see above), and so it must be behind door 3.

Game show host receives compensation for his patience.

One car richer. But if you really wanted this car so bad, couldn't you just sell your magic watch?

-JohnEsh

Sure, the question was somewhat misstated, but even as it is, wouldn't you be happier getting the car right away rather than waiting a day? To do that, you'll have to use one of the two-question solutions. Alternatively, you could ask two questions around 11:59 PM and when you are able to ask more at midnight, ask the other two. That way you only have to wait a very short period of time.

But I still prefer the two-question solutions. 76.190.157.141 00:46, 10 April 2009 (UTC)

-

This can actually be solved with just one question, assuming that when given a question the watch can't answer, it either explodes or does nothing:

"Is (door1 = car AND blue = true) OR (door2 = car AND yellow = true) 
 OR (door3 = car AND you flash false to this question)"

If (door1 = car AND blue = true), or (door2 = car AND yellow = true), the watch will obviously flash blue for door 1 or yellow for door 2. If both parameters are false and the car is behind either door 1 or 2 (door1 = car, but yellow = true/viceversa), then the next parameter (door3=car AND you flash false to this question) is found false as well because the car is not behind door 3. You would still get blue for door 1, and yellow for door 2. If the car IS behind door 3 then the first 2 parameters are obviously false. The third parameter is now a contradiction, and the watch cannot flash true or false. I hypothesize that since the watch is 100% correct, it will wait until the question has a possible answer, and will flash false immediately after you drive your car out from behind door 3.

-

My solution involves using the mutually exclusive or operator, essentially asking if either of two possibilities are true, but not both.

1. Does blue mean yes XOR is the car behind door #1? (in more english terms: Does blue mean yes OR is the car behind door #1, but not both?)

2. Does blue mean yes XOR is the car behind door #2? (Does blue mean yes OR is the car behind door #2, but not both?)

Since they're both the same question for different doors, the same logic can be applied to the answer for both questions.

So the answer to question 1 can be either yellow or blue, and either yellow or blue can mean yes or no.

Case 1: Answer - Yellow, Means - Yes Since Yellow means yes, that tells us Blue means no, which tells us the first part of the question is no, and since the overall question evaluates to yes, that means the car is behind door #1

Case 2: Answer - Yellow, Means - No Since Yellow means no, that tells us that Blue means yes, which tells us the first part of the question is yes, and since the overall question evaluates to no, that means the car is behind door #1

Case 3: Answer - Blue, Means - Yes Since Blue means yes, that means the car is definitely not behind door #1

Case 4: Answer - Blue, Means - No Since Blue means no, that means the car is definitely not behind door #1

The same logic applies to the second question.

Essentially, Yellow on the first question means door #1, Yellow on the second question means door #2, and Blue on both questions means door #3. It is not possible to get yellow to both questions. - Rahul

I think it would be trivial to use this XOR solution to solve the problem even with four doors, since you could split them up into groups of two for the first question, then ask which of the two in the second. Note that this makes use of all four possible combinations of answers, whereas your solution only makes use of three. Is there a good reason to leave it at three doors instead of four? We could even generalize it to 2ⁿ doors with n questions, although that is hardly necessary. 76.190.157.141 22:00, 7 May 2009 (UTC)

[edit] Light Bulbs

All Square Numbered bulbs will be turned on. A bulb will be turned on, if it has been flipped an odd number of times. A flip of a particular bulb occurs if the bulb is a integral multiple of a number. SO all bulbs which have odd number of factors will be turned on. Only Square numbers have Odd number of factors. -- Ramachandran R

Only prime numbers and perfect squares will be OFF. 1 Turns on all the lights on, 2 will turn 2 off, and nobody will turn it back on. The same holds true for all primes. For numbers which have factors that are not square roots, each factor not a square root will have a complementary factor which will turn it back on. In the special cases of 64 the only 6th power in the set, 2 and 4 complement 16 and 32, while 8 changes state to off. -- someone

• First sentence is terribly wrong, but the approach is correct and is basically the proof of Ramachandran's last statement about square numbers. The stuff about prime numbers is true but redundant. -- TLH

Full reasoning:

Light number N is toggled once for every person numbered with a factor of N. A light will be on iff it is toggled an odd number of times. Factors X of N occur in pairs (X, N/X) except for the case where X = N/X, which implies that N = X^2, a square number. Therefore only square-numbered lights are toggled an odd number of times, and the result follows. -- TLH

when run through an algorithm, you create the following task: let A = person number let B = bulb being toggled

for A = 1 to 100
 for B = 1 to 100
  if B/A has no remainder then toggle B
  increase B by 1
 next
 increase A by 1
next

this yields the following output:

1is on, 4is on, 9is on, 16is on, 25is on,36is on, 49is on, 64is on, 68is on, 70is on, 72is on, 74is on, 76is on, 80is on, 82is on, 84is on, 85is on, 86is on, 87is on, 91is on, 93is on, 94is on, 95is on, 96is on, 98is on, 100is on.

-- Jakerman999

scratch that, I made the mistake of starting at zero for one of my counters which made it accurate up to 64, but after that fails. after fixing the problem, I'm left with all perfect squares on(1,4,9,16,25,36,49,64,81, and 100). sorry about the mistake

-- Jakerman999

Wait, what? There must be a problem with my algorithm, as I get all perfect squares as being "on".

It's modus operandi is a rather brute-force one, so I don't see where it fails (though I do use a bit array that could be messing up or something).

In sorta-pseudo code:

boolean s [100]; for (i = 1 ; i <= 100 ; i ++)

 for (j = 1 ; (i*j) <= 100 ; j ++)
   toggle s[i*j];
 next

next

On my linux box, I just used grep to filter the output of my program (written in C; not the above pseudo-code), and I get 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 as being "on".

--69.249.155.229 01:22, 25 February 2009 (UTC)

Another way to think about it - so we don't need a computer is... Lights that remain ON after the 100th person must be numbers with an ODD number of factors. ie. the factors 1: 1 turns on (remains on); factors of 4: 1 turns on , 2 turns off , 4 turns on (remains on). etc. Squared numbers are the only numbers that can have an odd number of factors because one of the factors is matched by itself. (For 4: 1 matches 4, 2 matches 2; but For 20: 1 matches 20, 2 matches 10, 4 matches 5) -- Vikas R

[edit] The Lake Monster

Partial solution : Assuming the lake radius is 1 m. Obviously, if you try to run away on the oposite direction of the initial position of the monster, you will row 1 m and he would run <math>\pi</math>

I figured out a limit situation, where i would run in a smaller circle, with an angle of <math>\pi</math>, and he would run the same direction that i do. In that case, my smaller circle radius must be <math>\frac{1}{4}</math>, because he is 4 times faster than me. When i'm in that case, i can instantly try to escape him in the opposite direction, and i only have to run <math>1 - \frac{1}{4} = \frac{3}{4}</math> Therefore, i would get there in <math>\frac{\frac{3}{4}}{\frac{\pi}{4}} = \frac{3}{\pi}</math> the time he would. So i could escape him.

if course, to attain this limit, i should run in a spiral and get an relative angle to him as much closer to <math>\pi</math> as possible.

But there i assume the 1 second rule is false. The time difference between me and him must be something like <math>\frac{\pi-3}{4} \frac{r}{s}</math> r being the radius and s my speed. so we can't predict it.

with my solution, the monster would need to get <math>F=\pi + 1</math> times faster than me to defeat my strategy, if i'm correct.

oh, and if you don't read LaTeX, then ask your great master to support the math thingie. Batchyx 10:17, 22 March 2009 (UTC)

Don't have a solution to the escape portion though I did find the true identity of this "monster". It is quite obviously a raptor. Why has no one else realized this? You people should do less math and more reading of XKCD. - TheBigBadWolf

Just a logical solution, no math: let's say the monster starts at the south so you start moving north. To get where you'll be, he has to move [pi r], while you have to move [r]. He can go either west or east, and your responses will mirror his choice here so it doesn't matter; let's say he goes west. Once he's moved (pi r)/4 and is at the southwest "corner" of the lake, you start rowing towards the northeast corner, an extra (pi r)/4 from where he was headed; now he still has to move [pi r], if he wants to be waiting for you, while you have to move [r-x1] to get there. Once he's moved (pi r)/4 again and is at the west side of the lake, you change your destination to the east side of the lake; now he has to move [pi r] to get where you'll be, and you have to move [r-x1-x2].

I won't go through the geometry, but when the [x1, x2, ...] series' sum gets big enough, your trip to the shore will be short enough that you can do it faster than the monster can run [pi r]. - Otter

What Batchyx said, reworded and expanded:

If your boat travels in a small circle around the center of the lake you can complete a full rotation quicker than the monster. If your boat travels a larger circle near the perimeter of the lake, the monster will keep up with you. Somewhere in between there is a break even circle where you can make one rotation around in the same time it takes the monster to make one loop around the lake. This circle has a circumference 1/4th of the circumference of the lake. If the radius of the lake is R, the radius of this break even circle is R/4. Inside this circle you can go fast enough to keep the center of the lake between you and the monster and you can spiral outwards, remaining opposite of the monster. Once you reach the break even circle you will be (3/4)R away from the shore, while the monster is πR away from that point. In the time it takes you to travel (3/4)R, the monster can only travel 3R which is less than πR, allowing you to escape. Note: It's not actually possible to reach the break even circle with this method but you can get asymptotically closer the longer you spiral.

To know how close you need to get you can calculate the minimum size circle you need to spiral to. The monster will need to travel πR, in which time you can travel (π/4)R. This means you need to spiral greater than R-(π/4)R or (1-π/4)R away from the center of the lake before you make a beeline for the shore.

To calculate the speed the monster needs to travel to make escape impossible assume you travel at a velocity of v, and the monster travels at vx. The radius of the break even circle in this case will be R/x. This means you will need to travel a distance of R-R/x to get to shore. The amount of time this takes is (R-R/x)/v (time = distance / speed). The monster must cover πR in this same amount of time. The amount of time it takes the monster to get there is πR/vx. Setting these equal we get:

(R-R/x)/v = πR/vx

R-R/x = πR/x

1-1/x = π/x

x-1 = π

x = π + 1

The monster must travel π+1 times faster than you to make escape impossible. No calc needed. Further analysis will show that if the monster is traveling 4 times as fast as you will need to make almost one full loop of the spiral before being able to safely head to shore. -Hannibal

The above analysis seems perfect, but once you leave the "safe" circle, going straight to the nearest point of shore is not the best option.

The monster moves at x times our speed. Let's represent the lake by the unit circle, say we're at (1/x,0) ready to leave the safe circle, the monster is at (-1,0) and will start moving counterclockwise. Let the angle from the origin towards (1,0) be 0 and increase counterclockwise (as usual), so the monster starts at -π moving towards positive. All angles are measured from the origin, not our position. The distance from our start position to shore at angle α is √((cos α - 1/x)² + (sin α)²) = D(α). Assuming we don't go back into the "safe" circle, the monster will never change direction. By the time we've moved D(α) to reach the shore at angle α, the monster will be at angle -π + x D(α).

For example with x=4, if α=0, the monster is at -.1416 (π-3 away from us as expected). If α=π/8, it's at -.0418. Since we're at π/8 then, we're a lot farther from the monster: π/8≈.393, the angle difference .435. Actually, the difference increases all the way up to .587 for α=arccos .25 which is the maximum angle we can use without cutting into the safe circle.

Fixing α to arccos (1/x), D(α) is simplified to sin arccos (1/x) = √(1-1/x²). The maximum monster speed is just below when -π + x√(1-1/x²) = -π + √(x²-1) = arccos (1/x). x≈4.603338848751700 and α=arccos (1/x)≈1.352.

Now, I'm not saying even this is the optimal evasion, I don't know. Anyone care to try to improve with a dynamic rowing direction? --Nix

You actually don't need all this complex math. All you have to do is start at the center and row in the opposite direction of the monster's initial position. This will work unless the monster can run at 2π times your speed. Oops, nevermind. I accidentally thought the monster would have to travel the circumference, rather than half that.

[edit] Ball and Balance

I can't see a heading for this one. My solution is to number each coin and make the following weighs.

1, 2, 3, 4, 5, 6 vs 7, 8, 9, 10, 11, 12

1, 3, 5, 7, 9, 11 vs 2, 4, 6, 8, 10, 12

1, 4, 5, 8, 9, 12 vs 2, 3, 6, 7, 10, 11

As no coin is in the same group as another three times, only one coin will end up being on the heavy or light side three times, and that coin will be the counterfeight. If it is on the heavy side, it is heavyer and visa versa. -Azazyel

This has the problem that you don't know whether the counterfeit is heavier or lighter than the others, and more. For example, if the left side is heavier in every weighing, you don't know if 1 or 5 is heavier than the rest, or 10 lighter than the rest. To make it in three weighings, you'll need to introduce the possibility of equal weights by leaving out some coins. Proof: If every weighing only introduces 1 bit of information, you can't possibly distinguish between 24 states (counterfeit one of 12 coins, and lighter/heavier) in three weighings. An optimal first weighing could be 1, 2, 3, 4 vs 5, 6, 7, 8 and what you weigh next would depend on the result. Didn't think this to the end though. --Nix

Here's a step in the direction of an answer. Suppose the answer relies on eliminating some coins with every weighing and once we've eliminated each coin we're done with it. Then the optimal first weighing must be coins 1, 2, and 3 versus coins 4, 5, and 6. If the pans don't balance, you know the counterfeit must be one of coins 1-6; if they do, you know that the counterfeit is one of coins 7-12. Either way, you are down to six coins. There is no better first weighing because any other weighing would in some cases eliminate fewer than six coins, which will in the worst case leave you with more coins to distinguish among, and we want to be able to get the answer 100% of the time. With six coins we cannot do better than weigh 1 against 2 or, equivalently, weigh 1 and 2 against 3 and 4; either way, in the worst case we eliminate two coins and have four left. With four coins we cannot do better than weigh 1 against 2, and in the worst case, where 1 and 2 balance, we still have 3 and 4 left to distinguish between. We have failed. Therefore, either the answer does not rely on eliminating coins with each weighing, or the answer relies on somehow re-weighing coins we have already eliminated to distinguish the counterfeit. --satyreyes

I guess this falls under not relying (only) on eliminating coins with each weighing, but 1, 2, 3, 4 vs 5, 6, 7, 8 is better than 1, 2, 3 vs 4, 5, 6. If the sides are equal, you only have 4 unknown coins to sort through. It's true you can't sort six unknowns in two weighings, because there's 12 states to distinguish and the max you can hope to separate is 9 (3 possible results in both weighings). If the sides are not equal, you have an additional bit of knowledge to help sort the 8: you know which side was heavier. That's 8 possible states left to separate regardless of which way the first weighing went, sounds doable with two weighings. --Nix

Nix is correct. Capital letters stand for measurements: A first, B second, C third. The program starts with measuring A as 1, 2, 3, 4 v 5, 6, 7 8. If A equal, the oddball is in 9, 10, 11, 12. You would then measure B as 9, 10 v. 1, 2. If B equal, the oddball is in 11, 12. You would then measure C as 11 v 1. If C equal, the oddball is 12. If C not equal, the oddball is 11. If B not equal, the oddball is in 9, 10. You would then measure C' as 9 v 1. If C' equal, the oddball is 10. If C' not equal, the oddball is 9.

If A not equal, then measure B' as 1, 2, 5, 6 v 3, 7, 9, 10. If B' equal, then oddball is in 4, 8. Measure C'' as 4 v 11. If C'' equal, the oddball is 8. If C'' not equal, the oddball is 4. If B' not equal, then oddball is in 1, 2, 3, 5, 6, 7.

If in A 1, 2, 3, 4 were lighter than 5, 6, 7, 8, and if in B' 1, 2, 5, 6 were lighter than 3, 7, 9, 10, then the oddball is a light 1 or 2 or a heavy 7. Measure C''' as 2, 7 v 11, 12. If C''' equal, then the oddball is 1. If C''' heavy, the oddball is 7. If C''' light, the oddball is 2.

If in A 1, 2, 3, 4 were lighter than 5, 6, 7, 8 and if in B' 1, 2, 5, 6 were heavier than 3, 7, 9, 10, then the oddball is a light 5 or 6 or a heavy 3. Measure C'''' as 3, 5 v 11, 12. If C'''' equal, then the oddball is 6. If C'''' heavy, the oddball is 3. If C'''' light, the oddball is 5.

If you've been able to follow my notation so far, you should be able to extrapolate this situation for the other two cases of lightness/heaviness. Each ball is uniquely identified in this schema. However, this fails to determine if 12 is heavier or lighter than other balls if it is indeed the oddball. --Mark

I didn't try to follow or verify all of your thought, but doesn't this fix your 12: if A equal, B = 9, 10 vs 11, 1. If B equal, C = 12 vs 1. If B not equal, C' = 9 vs 10. If C' equal, 11 is the oddball, see B for light/heavy. If C' not equal, see B for light/heavy and use that knowledge to determine oddball from C'. --Nix

This is impossible. There are three weighings. Each can give you one of two results. This gives a total of three bits of information. Just enough to find one coin in eight or to find one and four and see if the counterfeit is lighter or heavier. Finding twelve coins and telling if the counterfeit is lighter or heavier requires at least five weighings. That is just a lower limit. You might need more. --DanielLC

Each weighing can give one of 3 possible results (right side heavier, equal weight, left side heavier). I think that means that you have more than 3 bits of information.

I see. That would give you 27 possible measurements, when there are 24 possible answers. I'm still not sure this is possible. -- DanielLC

A relatively simple explanation: Weigh 4 vs 4. If one side is heavier, weigh 3 from the heavy side + 2 from the light side vs 1 heavy and the 4 remaining 'normal' coins. If the 'heavy side' is still heavier, the counterfeit is heavier and it's of the 3 'heavies' on that side, which can be determined in one weigh. If the 'heavy side' is now lighter, it's either one of the 2 'light' coins on that side or the 'heavy' coin that switched sides, which can also be determined in one weigh. If the sides were even, it's one of the 2 'light' coins set aside after the first weigh. The remaining scenario is that the original weigh was even. In that case, weigh 3 of the remaining coins against 3 'normal' coins from the first weigh. If the balance is uneven, you know if the counterfeit is one of those 3 and if it's heavier or lighter, and can be determined in one weigh. Otherwise it's the final unused coin, and you weigh it against any normal coin to determine. The trick here is to break coins into groups of three where the weights are known, or 'groups' of 1 where the weight is not.

I figured out a way. It isn't simple, but I doubt there is a simple way. I'll explain in pseudocode. The coins will be referred to as A through L. + Means the counterfeit is lighter, - means it's heavier. -- DanielLC

 switch(ABCD?EFGH)
 <
 {
   switch(ABE?DFI)
   <
   {
     switch(A?B)
     <
       return(A-);
     =
       return(F+);
     >
       return(B-);
   }
   =
   {
     switch(CG?IJ)
     <
       return(C-);
     =
       return(H+);
     >
       return(G+);
   }
   >
   {
     switch(DE?IJ)
     <
       return(D-);
     =
       impossible
     >
       return(E+);
   }
 }
 =
 {
   switch(ABC?IJK)
   <
   {
     switch(I?J)
     <
       return(J+);
     =
       return(K+);
     >
       return(I-);
   }
   =
   {
     switch(A?L)
     <
       return(L+);
     =
       impossible
     >
       return(L-);
   }
   >
   {
     switch(I?J)
     <
       return(I-);
     =
       return(K-);
     >
       return(J+);
   }
 }
 >
 {
   switch(ABE?DFI)
   <
   {
     switch(DE?IJ)
     <
       return(E-);
     =
       impossible
     >
       return(D+);
   }
   =
   {
     switch(CG?IJ)
     <
       return(G-);
     =
       return(H-);
     >
       return(C+);
   }
   >
   {
     switch(A?B)
     <
       return(B+);
     =
       return(F-);
     >
       return(A+);
   }
 }

Edit: I figured out a simple way. Basically, if there are n coins, you compare coins 1 through n/3 to coins n/3+1 to 2n/3. If they're the same, you have n/3 coins left to compare, and you need to figure out if it's lighter or heavier. If they aren't, you pair coin x with coin x+n/3 for x <= n/3, and you have n/3 pairs of coins to sort through, and still need to figure out if the counterfeit is lighter or heavier. Once you know, you can tell which coin in the pair is the counterfeit. For example, if the lower numbered coins are lighter, and the counterfeit is lighter, the counterfeit must be one of the lower-numbered coins. --DanielLC

[edit] Tally Game

According to the group sizes, I'll denote for example III IIIII II III with 2335. It doesn't matter in which order the groups are on the board.

I first tried to find a clean separation between winning and losing states on paper, but didn't get as far as I wanted.

Clearly, of the states that only have groups of one, an odd amount of them means the player to move will lose.

A set of paired groups (e.g. 11112255) loses unless they are all ones. The player to move first must break a pair. Their move can be matched by removing an identical portion of the pairing group (leading to a smaller set of paired groups), or if that would lead to only groups of one, removing one more or less stick so that it ends up an odd amount of ones.

Obviously any state that leads to one of the known losing states by one move is a winning one. States that only lead to known winning states are losing. This way, new rules can be inferred, one by one, but that isn't really fun as a puzzle. The simplest new losing state is 123. No losing state can be reached from it, but any move will have a follow-up that reaches a losing state. Now, states like 12x, 13x, 23x with x>3 are winning since they can be reduced to 123 in one move. This leaves 145 as the next losing state, also 246.

At this point, I was bored enough to let the computer calculate up to the initial state of 357. It seems all the losing states can be combined with each other and paired groups added or removed at will, although I don't have a proof. For example 123 + 145 – 11 = 2345. Maybe this could lead to a general way to determine the status of a state without any recursion or pretabulation of states.

Anyway, the computer told me that 357 is a winning state. In addition to my first two rules (ones and pairs), the smallest set of losing states you need to force victory is as small as {123, 145, 246, 347}. Whatever situation you end up in, you can always find a move that results in one of these states, as long as you make those moves.

--Nix

This puzzle is a game called Nim, with the interesting extension of being able to split stacks instead of just take from the end. Being able to split stacks doesn't affect the outcome though; the Nim strategy still works.

The trick here is to write the game state in binary and consider the XOR function. Here, 3 5 7 would be 11 101 111 and the XOR of this is 001. First thing to note is that the game ends when the XOR is 000.

The key fact to use is that someone presented with a non-zero XOR can always zero it with the right move, and someone presented with a zero XOR will always disrupt that (with ANY move) and make it non-zero. You can always find a zeroing move by taking from the end of a stack (usually the largest, but not always).

Now the game rules say that the person who takes the last stick loses, but it's easier to first consider last-stick-wins. To win, all you have to do is present your opponent with a board XOR of 0 at each turn. They are forced to disrupt that to non-zero, and you can again respond by zeroing it. Since sticks are finite and are only being removed, you will eventually present them with a zero board and therefore win. This strategy doesn't need any look-ahead whatsoever, just take each stack in turn and flip the relevant bits; if the stack reduces in size, make that your move (there will be at least one that reduces).

As for last-stick-loses, you need to control the game by doing the same as above, but change the method at the last minute in such a way that your opponent is forced to present you with an XOR of 0. You need to alter the method when presented with one stack greater than 1 and the rest equal to 1. You need to either take all but 1 from the big stack or take the all of the big stack, whichever results in an XOR of 1 (basically leave an odd number of 1-stacks). You win!

-- TLH

I didn't exactly follow the above logic, but if you take all but 1 from the big stack, your opponent takes two from the end of the stack of 5, and now has achieved symmetry and can beat you without breaking a sweat. So your conclusion is wrong. I'm pretty sure Nix has it right.

-- AANNOONN

You are correct, you did not follow :P

'The big stack' in that paragraph refers to a late game state where all but one remaining stacks are of size 1, and the other one is of size greater than 1 (the big stack). At this point you abandon the XOR 0 recipe and take from that big stack, to leave an odd number of 1-stacks. This will either mean taking the whole stack or turning it into a 1-stack.

For example, if presented with 1 1 1 7, you need to take all 7. If presented with 1 1 1 1 7, you need to take 6. The point is that, to get to that stage, you need to follow the XOR 0 recipe then abandon it in favour of leaving an odd number of 1-stacks.

Read that paragraph again, it does not refer to starting out. -- TLH

[edit] Dumbass, MD

Add another of pill A to your hand, then grind the four pills with a mortar and pestle. Divide the powder into two piles and take one pile today and the other tomorrow. ~Stephen

Well, my first thought would be to count all the remaining pills, so I know if I've got two A or two B in my hand.

My second thought would be to set aside all three, take one pill out at a time from my remaining supply, and use the time I have to sue my doctor for malpractice. However, I suspect that's not the solution you want. -John 99.224.156.92 23:39, 11 February 2009 (UTC)

Get out another A pill then cut all the pills in half and then take one half of each pill that day and the other half the next day. -dw

But then you might still take the wrong halves. My solution would be to split the 2*A and 2*B up infinitely, i.e. grind them into a powder, mix it properly, and cut that in half. Then you'd have roughly 2*AB. I don't know if the problem statement requires an integer solution and the pills have to be taken as a whole, can anyone clear that up? --Steve

I think the half solution is fine - after chopping you have (a,a) (b,b) (b,b). If you remove just the left halves, you know you have a full B pill and half an A pill in your hand. Then, you get another A pill, cut it in half, and add that to your hand. You now have a full A and a full B pill in your hand, with the remaining half pills being what you should take tomorrow (another full A and a full B). From then on, you return to your original routine, possibly after pouring food colouring into one bottle ;) - Tim J 150.203.160.121 01:17, 12 February 2009 (UTC)

You can actually make sure that you take the right halves. Take out another A pill, so you have 2 As and 2 Bs; put them in a row and cut them all in half. You don't know which is which, but you *do* know that each half is the same as the opposite half; they are in a row (a 4x2 matrix of halves now), so shift one row to the right by 3. Up to symmetries and rotations, the only options for arrangement are 1212 and 1122 (with 1 mapping to either A or B); try it out on paper and see what you get. You'll see that shifting one row of halves to the right by three (with wrap-around) in every case gives opposite pill types at the same position in each row. So you have 4 pairs of half-pills; take two pairs for the next two days, each pill will be 1/2 A and 1/2 B. The 'grind it all up into a powder and talke half the powder' solution is smart too; I don't know how precisely you can measure (or cut) for the sake of answering the riddle, but it seems to me that some cutting must be involved.Wsa 21:19, 13 February 2009 (UTC)

ED - On closer inspection, Tim J has it just as certainly as I do. As usual I'm overthinking things. Wsa 21:23, 13 February 2009 (UTC)

-_- don't we have 2 hands? A in one hand and B in another?

I'm fairly sure I have a guaranteed answer, as long as we're allowed to cut the pills in half (like the people above me are saying). I would take out another A pill, and line up the four pills on my table. At this point I have no idea which pills are which, but that doesn't matter. I then, very carefully, cut each pill laterally in half, so that instead of worrying about left and right halves, you now have four top and four bottom halves. But no matter how the pills are arranged in their line, if you then consume (say) all of the top halves, you must have two A-halves and two B-halves. Tomorrow, you take all the bottom halves as you finish your application to sue the doctor who gave you identical, ten million dollar, life-or-death pills, and breathe a small sigh of relief. Does that sound about right to anyone else? -Azukar

why does it matter if you cut them laterally? 1/2 of a pill is 1/2 of a pill. if you just add an A to the line, cut them all in half and take half, you will have the right amount, no matter which way you slice it. --psolms

The lateral solution has the advantage that it's also practical - one cut, and a sweep, and you've got the right amount. I don't think it's logically any different. Tim J 150.203.160.121 05:24, 18 February 2009 (UTC)

Azukar: I was really just reacting to @ED's solution, which seemed unnecessarily complicated. @psolms You're right, cutting laterally or whatever the opposite of laterally is (literally?) doesn't have any logical advantage, but @Tim J has it right: it's more practical and has less chance of screwing yourself over even further by mixing up halves somehow. -Azukar

That said, can we get some kind of confirmation from the originator of this puzzle, though? Randall or whoever first uploaded it? -Azukar

I came up with the same answer, add another A pill and cut them all in half, eat, then live another precarious day. I know this is the answer, but technically speaking, one is not supposed to cut pills in half willy nilly (http://health.usnews.com/usnews/health/articles/040531/31pill.htm) though I'm sure if the riddle said "identical pills right down to the dividing line in the center" the jig would be up. Now, if there is a line dividing the pill (some do, some don't), if you have consulted with a doctor, or the manufacturer, they may say it's ok. One must do this because the manufacturer may not guarantee that there is exactly 50% of the "medicinal" components in either half of the pill. The same goes for nicotine patches, gel pills, especially slow release pills, etc. Pills can be made of very low actual amounts of medicinal ingredients, and high amounts of filler, so the distribution of said medicinal ingredients may not be uniform. I was impressed that at least one person can conceive of something more expensive than printer ink. --Durak March 20, 2009 17:09 UTC

Add another A pill to equalise your remaining pills, then sell those 4 pills for $40,000,000. Doesn't matter how you label them as they're indistinguishable and it's not you who'll die from it. Use the money to buy new, labelled pills from your doctor. This avoids cutting pills in half. -- TLH

cutting, or gring the pills works fine, but there is a problem if the pills have a licquid centre instead of a solid one. in this scenario what would you do?? Simple answer -> Die.

[edit] PEARLS! White Pearls and Black Pearls

Yragle the pirate has 100 white pearls and 100 black pearls. The white pearls are worthless, the black pearls are priceless. He will let you arrange the pearls in two sacks, and then after he mixes up the pearls in each bag and shuffles the bags he will let you pick a pearl from one of the two bags. How should you distribute the pearls between the two sacks to maximize your odds of getting a black pearl?

--again dunno if this is hard enough, but its fun

A single black pearl in one bag and all the rest in the other? Probability slightly less than 75%. I think I saw a similar problem in a Martin Gardner book. John Fouhy. 125.236.197.192 22:53, 11 February 2009 (UTC)

That's the correct answer in the puzzle's context. Realistically, though, you'll be able to tell which bag is holding nothing and which is bulging with pearls, so your odds are more probably 100% if you're paying any attention. (You could argue that he's giving you a random bag, but if he's the one choosing the bags, he'll give you the one with the white pearls.) --70.103.74.5 00:41, 12 February 2009 (UTC)

The bag is chosen by coinflip 207.172.84.58 06:56, 16 February 2009 (UTC)

My thought process was as follows: black/all: 50/100 50/100 in each bag, giving 25%, then 100/100 and 0/100 giving 50% then looking at the talk page: I initially understood the solution as written to be 1/100 and 99/100 which didn't make sense, before realising 1/1 and 99/199 gives almost 75%. I miss maths. design has left me dumb

The probability is 74.87%, which makes sense. After all, the one bag with only black pearls gives you a black 100% of the time, and you choose it half the time, which means that even if the other bag had no blacks, you'd have a 50% chance of getting a black. The almost-even chance of getting a black in the other bag is gravy at that point.

It's doesn't matter: the probability of getting a black pearl it's always 1/2. Suppose you have P balls in bag 1 and 100 - P in bag 2, the probability of getting a black pearl is calculated this way :

P1 = Pr( pearl = black | coin = heads ) = P/100

P2 = Pr( pearl = black | coin = tails ) = 1- P/100

Then since the coin is fair:

Pr ( pearl = black ) = 1/2 P1 + 1/2 P2 = 1/2

so this was in a way a tricky question . Bunder 200.104.73.121 00:35, 14 April 2009 (UTC)

Your formulae don't make any sense (to me anyway). If P1 is supposed to be the probability of getting a black pearl from bag 1 given that you're selecting from bag 1, then that would be (number of black pearls in bag 1) / (number of pearls in bag 1). You don't have a variable for "number of black pearls in bag 1"; and why do you still have a number 100 floating around in connection with bag 1? Or do you mean that P is the number of black pearls in bag 1? - If so, it looks like you're assuming that each bag must contain 100 pearls total, which isn't specified in the question. 87.114.43.251 13:53, 4 May 2009 (UTC)

[edit] Bit Algorithm

 int count(int n) {
   int c = 0;
   while(n) {
     c++;
     n = n & (n-1);
   }
   return c;
 }

I don't know who submitted the above, but there are far better—just look at hamming weight (aka population count) on wikipedia for some examples. Heck, there's even an entire article in "Beautiful Code" about "the quest for a faster population count" (or something to that effect). --69.249.155.229 01:27, 25 February 2009 (UTC)

Yes, there are better, but this is the best answer given that it's both intuitive and correct.

n ^= n & -n;

also works. (n & -n) is useful if you want the least significant bit for some reason. --80.175.250.218 17:04, 13 March 2009 (UTC)

Wait -- which of these meet this critera from the puzzle:

"Your algorithm [...] should be in O(i) where i is the number of 1-bits inside n."

All of these seem to be O(log(n)) -- if you add a ton of 0s, the algorithm takes longer. Or are we assuming that & is an atomic operation taking constant time no matter the bit size?

[edit] One-lane Highway

The number of clumps is a discrete random variable, so the expected value is the probability-weighted sum of the possible number of clumps. Call the expected value E(N).

If N=1, the expected number of clumps is always zero: E(1) = 0. If N=2, there are two possibilities: the car in front is faster or slower, resulting in 0 or 1 clumps. These are equally likely, so E(2) = 0/2 + 1/2 = 1/2.

If N>2, examine the three cars at the tail of the line. Each is either faster than the car in front of it or slower. Presumably the probability of each case is the same. If it is faster, it will clump with that car. If it is slower, it will fall back. Now remove the last car; the number of clumps is be reduced (by one) only if this car is faster than the car in front of it, and that car is slower than the next car. If this car was slower, it wasn't part of a clump, and if the car in front of it was faster than the next one, they still form a now-smaller clump.

So for N>2, E(N) = (3/4)E(N-1) + (1/4)(E(N-1) + 1) = E(N-1) + 1/4 = (N-2)/4 + E(2) = N/4

--Evan

I don't believe this is the case... consider the speeds (in whatever units you prefer): 1, 3, 2, 4. Now, these will form one clump, travelling at a speed of 1... and removing the last car wouldn't remove a clump. However, your argument claims it *would* (4 is faster than 2, 2 is slower than 3). A more accurate criterion: the last car will fall back and become its own clump iff it's the slowest car of the mob... simply put, the slowest car of the mob will always be the head of the last clump. It's reasonable to assume that the last car will be the slowest with probability 1/N. So E(N) = E(N-1) + 1/N... that is, E(N) is the sum of the first N terms of the harmonic series. Also, a minor point: E(1) = 1, not 0 (one car will necessarily form one clump). Phlip 11:04, 12 February 2009 (UTC)

Wait... rereading... does a car on its own count as a clump or not? I guess not... that makes things trickier. But my "1, 3, 2, 4" objection still holds regardless. Phlip 11:05, 12 February 2009 (UTC)

Yes, my analysis was wrong. Counting a car on its own as a clump would certainly simplify things, though!

I'll have to re-think this. --Evan

As I see it, this problem reduces to 'Estimate the number of cars travelling slower than all cars in front of it'. For the first car, the probability of this will be 1, for the second 1/2, for the 3rd 1/4 etc. For the nth it would be 2^(1-n). So it seems to me that the estimated value for n cars would just be the sum of these from 1 to n, which is just 2-2^(1-n). It's interesting how if this is right, even as n approaches infinity the estimated number of clumps is never going to surpass 2. Not entirely sure about my second assertion though :s --Luke

I am not an expert at probability, but it seems to me that the probability for the third car is 1/3. If you have three numbers, the probability of the first being the largest is 1/3, not 1/4. In that case, the answer becomes the sum of the reciprocals of the integers from 1 to 100. This assumes that a single car by itself is a clump. -Tiax

• This one problem seems... specially ... problematic to me. Look: to start solving the problem you need to determinate the chance of velocity of random car 'A' be higher or lower then velo of car 'B'. One would assume it is '50-50' but it doesnt look like so... for example, whats the probability of car 'A' being 10mph slower then 'B' that can go from , say, 1 to 50mph? If the car 'B' is at 15 mph the chance is 0. My point is, chances of one car being faster then the other are higher then one slower then the other, cause cars cant be at 0 speed and can't have minus speed (cant go reverse, since its 'one way highway). If this is '(Another interview question)' I hope it is for traffic engineer job appliance test interview ;)

189.62.195.228 00:35, 14 February 2009 (UTC)

• I worked out the solution for n=1,2,3,4 and the sequence goes 0,1/2,5/6,13/12, or the sum of 1/i for all i from 2 to n. It seems self-evident to me that the sequence will continue in the same manner, although I would be hard-pressed to prove it; this agrees with what Tiax said. -Paul

• Phlip - my take on it yields the same recursion yours does; only difference is that E(0) and E(1) are both 0. My take on it is at Chasing Cars for the truly bored... DukeEgr93 01:10, 15 February 2009 (UTC)

I think I've found the easiest way to prove the harmonic series result. In the 1/n of the arrangements of n cars in which the last car is the slowest, it falls behind, so the number of clumps is the same as if the last car were not there. In the other (n-1)/n arrangements, the last car is part of a clump containing the slowest car and zero or more other cars. If there are other cars in the clump, it would exist without the final car. Thus the presence of the last car creates a clump only in the 1/(n-1) of these arrangements in which the clump consists of the last car and the slowest car. So a clump is added in ((n-1)/n)(1/(n-1)) = 1/n of the possible arrangements, and E(n) = E(n-1) + 1/n. Since E(1) = 0 we have E(n) = 1/2 + 1/3 + 1/4 + ... + 1/n for n>1. -- Evan

• Ohhhh - that's good. The only way adding a new car to the end will form a new clump is if (a) the new car is not the slowest and (b) the penultimate car was the slowest of the n-1 cars. As an aside - how does XKCDB not have math tags? DukeEgr93 15:14, 15 February 2009 (UTC)

Here's my take. We can consider the relative speeds of the N cars as integers from 1 to N. Thus the situation is represented as a permutation of {1,2,...,N}. For each i, 1 <= i <= N, let X_i be a random variable which is 1 if car with speed i is at the head of a clump, and 0 otherwise. In our permutation world, this means X_i is 1 iff the numbers 1,2,...,i-1 come before i in our permutation. The probability of this happening is 1/i (since each of the numbers 1,2,...,i has an equal chance of appearing last relative to the others), so E(X_i)=1/i. By the linearity of expectation, we have E(N) = E(X_1) + E(X_2) + ... + E(X_N) = 1 + 1/2 + ... + 1/N, which approaches log N as N -> infinity. -rzh

Yes, computer simulation confirms that the expected number of clumps is definitely always the sum of the harmonic series to the nth term. Even more interestingly, though, is that I've come across a shocking realisation as to why this is the case. It turns out that for any clump of size x, the expected number of clumps that size is always 1/x, so long as x<=n. This explains why for n cars the expected number of clumps of any size will be 1 + 1/2 + ... + 1/n, and inadvertantly solves the problem of what happens if you don't regard a lone car as a clump. The expected number of clumps would then just the the harmonic series sum minus one (yes, DukeEgr93, math tags certainly would be useful). I've manually worked this out for all n<5, and shown by simulation that it holds for all n<20, but I lack both an elegant proof or the capacity to think of one at the moment, so there you go. At least now we know the answer. --Luke

Another approach that gets you the harmonic series (which is definitely the right answer) is to consider adding the cars to the highway at random in order of speed, from slowest to fastest. The slowest car, alone, is a clump. The next slowest is either ahead of or behind it, so it forms a new clump with probability 1/2. (And expected value 1 * 1/2 = 1/2.) The next slowest car has three possible positions (in front, behind the front car, last), and forms a new clump only in one, so that's 1/3. And so on -- car N only forms a new clump if it's placed at the front of the pack, with probability 1/N. --dj

I just thought of a solution that at first seemed the exact opposite of the consensus, but is actually pretty close once you do the math. In my case, I assume that one car is indeed a clump.

Let's call the number of clumps for N cars C(N). We start by looking at the slowest car. It, and all the other cars behind it form a clump. The expected position of the slowest car amongst the N is (N+1)/2, so the expectancy of the number of cars in front of it is (N-1)/2. All the cars in front will clump around independently of the "slow clump", so they have their own expectancy C((N-1)/2) of clumps. Now, we have a recursive relation: C(N)=1+C((N-1)/2).

For example, we have 15 cars. The expected placement of the slowest car will be eighth, so cars 8-15 will clump together. Now we are left with the front 7. They have their own slowest car, whose expected placement is 4th, clumping 4-7 together. The next expected clump is 2-3, and then 1 alone. While this "expected placing" doesn't seem like rigorous mathematic proof, it has been known to work remarkably well for such problems.

Solving the recursion equation, or just looking at the example, leads to an answer of C(N)=log2(N+1). What bothers me is that the harmonic sum diverges like a natural logarithm and not a log of base two, more specifically: Sum(1/N)~ln(N)-0.577.. which would mean that for large number I'm off by a constant factor of ln(2). Why this is so I'm not sure. Perhaps the true "expected" position should be 1/e places from the end to even out the true probability.--Yashkaf 19:38, 23 March 2009 (UTC)

Yashkaf, I can see two problems with the way you set up your recursion. First, you sometimes need to know the expected number of clumps for a non-integer number of cars, which doesn't make sense. Second, you are commuting expectations around in a way that I am not sure is justified (e.g. using the expected position of the slowest car in place of its actual position.)

The way I think of this problem is pretty similar to what people have already said. Consider the starting positions of the cars as a permutation of N, with 1 representing the slowest car, 2 the next slowest, and so on. Then the number of clumps is just the number of right-to-left minima in this permutation. These are counted by | signless Stirling numbers of the first kind. That is, c(N,k) is equal to the number of permutations of N with k right-to-left minima. These are known to satisfy the recurrence c(N+1,k) = Nc(N,k) + c(N,k-1), which can be proven in a number of ways, including ones that are equivalent to some of the proofs above. Then the expected number of clumps is 1/N! * sum_k c(N,k)*k. This can be expanded using the recurrence to 1/N! * sum_k (kN+1)c(N-1,k) = 1/N! * sum_k c(N-1,k) + 1/(N-1)! sum_k k*c(N-1,k) = 1/N + 1/(N-1)! * sum_k k*c(N-1,k). So by induction the expected number of clumps is 1/N + 1/(N-1) + ... + 1/2 + 1. --96.26.213.147 01:52, 26 March 2009 (UTC)

We have N cars, the expected location of the slowest car is in the middle thus forming one group from the back up to the mid point (we have at least 1 group), consider all the cars ahead of this group as the new subset M, perform the same thing and we'll have another group that goes up to the 3/4 N mark from the back for 2 groups. We can do this as far as till the next subset X is at least 1 car long. So for N starting cars we'd expect X number of clumps where 2^X = N giving X = lnN/ln2. (This makes more sense for N being a large number and doesn't make sense at all for N = 2 as in that situation we'd expect 1.5 groups where as my formula would give 1) - -- EDIT: just saw someone already posted a similar answer ... damn ... (another problem with this method is that it tends to overestimate the number of clumps as verified by simulation, the reason as far as i can work out is because the the average number of clumps is different than the clumps resulting from the average positions of the cars ... that is the only way to get N clumps is if the cars were lined up in order of speed but there's (N-1)! ways to get 1 clump)- Dominic Leung 31 Aug 2009

[edit] 2 envelope exchange problem

• So, assuming m and 2m are in the envelopes, the expected value when picking one at random would be 0.5 m + 0.5 2m = 1.5 m. Once you pick an envelope, there is some value x in the envelope. The expected value of a swap would be 0.5 (x/2) + 0.5 (2x) = 1.25 x.
  

Hmm... Only thing I can think of is that there are two independent variables each with two states - which envelope is picked and whether they are swapped. Each has an equal probability (0.5 per envelope and 0.5 chance of swapping) so

E = p(pick m & ~swap) m + p(pick 2m & ~swap) 2m + p(pick m & swap) 2m + p(pick 2m & swap) m

E = 0.25 (6m) = 1.5m

E_~swap = (p(pick m & ~swap) m + p(pick 2m & ~swap) 2m)/p(~swap) = (0.25 * 3m) / (0.5) = 1.5m

E_swap = (p(pick m & swap) 2m + p(pick 2m & swap) m)/p( swap) = (0.25 * 3m) / (0.5) = 1.5m

Maybe? I feel like swapping should not matter since, were there two players, there's no way it is preferable for both to swap... DukeEgr93 16:08, 15 February 2009 (UTC)

So what's the probability distribution? If you tell me it's uniform and finite, there's an easy solution. If you know what's in the envelope, swap if it's below half the maximum value. If you don't, well, it doesn't matter. If you tell me the distribution is such that the density decreases as m goes to infinity, I rather suspect that it will work out that it doesn't matter whether you swap or not (as there's more than a 50% chance you'll get the lower value if you swap). If you tell me that the distribution is uniform and infinite, I haven't the faintest bloody idea what you're talking about, and I know perfectly well you can't tell me which real number is the probability that m is between 1 and 100. Thornley 03:01, 18 February 2009 (UTC)

Unless you know the probability distribution, this is just like The Necktie Paradox below. You either picked m or 2m. If you picked m, you gain m from a swap, otherwise you lose m, for an expected value of m/2 - m/2=0. If you know the probability distribution p(x) (the integral of p(x) from a to b is the probability that a <= m <=b) and you can look in your envelope, then you can do better. You can come up with a strategy and use it to define a function S(x), such that when your envelope contains x, S(x)=1 if you will swap, otherwise S(x)=0. The expected return of your strategy for a given m is [2mS(m) + m(1-S(m))]/2 + [mS(2m) + 2m(1-S(2m))]/2 = m(3 + S(m) - S(2m))/2. Since the expected return of either never switching or always switching is 3m/2, the expected advantage of your strategy for a given m is (S(m) - S(2m))m/2. Thus the expected advantage of your strategy in general is integral(xp(x)(S(x) - S(2x))/2)

For example, if p(x) = 1/n for 0 < x < n and zero otherwise (uniform, finite) then the expected advantage is integral(x(S(x) - S(2x))/2n) from 0 to n) = sum(b^2 - a^2)/4n over all ranges (a,b) where S(x) > S(2x) minus sum(b^2 - a^2)/4n over all ranges (a,b) where S(x) < S(2x). The optimal strategy is S(x) = {1:x<n}, for which S(x) > S(2x) from n/2 to n and S(x) < S(2x) nowhere, giving an expected advantage of (n^2 - n^2/4)/4n = 3n/16.

--Evan

All this math is silly. The paradox implies an unknown distribution. The paradox arises when you assign a dollar value to just one envelope and you don't know if its the greater or the lesser amount. No one has posted a resolution yet. -Ari

• I certainly have, but since it was the least interesting aspect of the problem, I only spent two sentences on it. Here it is again: "You either picked m or 2m. If you picked m, you gain m from a swap, otherwise you lose m, for an expected value of m/2 - m/2=0." As I said under The Necktie Paradox, if you don't know the probability distribution, then knowing the dollar value of just one envelope is useless. Trying to incorporate it into your analysis gets you tangled up in the (unknown) probability that your known value is the lesser value. --Evan

• If you think that all the math I did for the case when the probability distribution is known "is silly," then you are incorrect. I've successfully tested, via software simulation, my solution for the case in which the distribution is uniform and finite. --Evan

For any reader who is sure that I must be wrong, based on an analysis such as the one found at Wikipedia, I should clarify that my strategy-based analysis fails for the discrete distribution given there, and probably for the exact same set of other possible infinite distributions described on that page for which P(X=a) > 0.5P(X=a/2). This does not, however, invalidate either my approach or the Wikipedia page's conditional probability approach for the infinitely large and often interesting set of distributions for which that peculiar property does not hold.

In fact, distributions for which the "paradox" arises are very weird distributions indeed. I think that there cannot be a physical system that approximates these distributions without losing the paradoxical property due to having a finite upper bound. For example, if you set k=0.998 in the distribution given by Wikipedia, then there is a better-then-half probability that the envelope contains more money than there are particles in the universe. Set it near its lower bound of 0.5, and there is a small (but not vanishingly small) probability that the envelope contains more than a quadrillion dollars.

--Evan

Evan,

Again, it becomes a paradox when you plug in a number, until then its not a paradox. We're assuming each envelope is 50/50 to be greater than the other. Plug in a number and do the arithmetic, its quite simple math, and you'll see that you haven't solved the paradox.

-Ari

"assuming m and 2m are in the envelopes, the expected value when picking one at random would be 0.5 m + 0.5 2m = 1.5 m"

Extend that statement to cover both envelopes; the expected value of each envelope is 1.5m. Now go through the situation - you pick an envelope. It has expected value 1.5m. You are offered to switch to an envelope that also has expected value 1.5m. Hence, there is no advantage or disadvantage to switching.

Furthermore, consider that assuming the value of yours is x leads to the expected value of the other being 1.25x. Then you could flip your selection for an expected 25% rise in payout. But then you could flip again for another expected 25% rise in payout. This is clearly absurd, so the error must be in the initial assumption. That is, fixing the value of one and working with an expected value for the other in terms of the first was an invalid start, since the first is dependent on the same random variable. We have to do as above and consider them both as expected values.

Finally, feel free to add dollar values. Say $10 and $20. The expected value of each is $15 and that's all there is to it. As a point of interest, you can also generalise the problem to having two envelopes each independently containing $10 or $20 - the expected value of each is still $15. The problem just rules out the cases where they both have $10 or both have $20.

To summarise, I'm saying that the 'switching is better' argument contains an initial error in fixing a value that is still considered random, so there ought to be no paradox. -- TLH

[edit] Manhole covers

I think I've seen this question already somewhere... My logical guess is that as circle minimizes the area for linear bounds, you'd waste less iron for the cover, which is very expansive. Manufacturing costs should also be actually lower for round holes, since they can be drilled easily, are more stable structurally because they don't have edges (are uniform, cylindrical). Should I also mention traditional values?... 189.62.195.228 00:42, 14 February 2009 (UTC)

Actually, I believe it's due to the fact that any other (feasible) shape would be able to fall through it's appropriate hole, when positioned at the correct angle.

• I think it is a combination of being easier to roll and not falling into their hole. Could also make them general Reuleaux polygons but...that would be hard. And finding shafts with general Reuleaux-polygonal cross-sections would be a good trick. DukeEgr93 01:17, 15 February 2009 (UTC)

I've heard that it's because of 1. Rolling capacity 2. Impossibility of falling through the hole and 3. It doesn't matter which way you put the cover back on, since it has circular symmetry.

• in fact, some manholes in the UK are square, and some are made up of two triangular sections (therefore rectangular). so really, this problem is rather silly. --86.142.140.162 06:24, 16 February 2009 (UTC)

If we only wanted to make sure the manhole doesn't fall through the hole, any shape of constant width would work. Since we're casting the cover and the piece of metal that we'll embed in concrete for the manhole to rest on, I don't think any convex shape is much harder to manufacture. We have a theorem that states that the Reuleaux triangle has the least area of any curve of constant width. This is about 10% less area than a circle with the same width, so we'd use approximately that much less steel if we chose this shape (assuming we'd use the same width). But then a few of the other good properties of a circle that are mentioned above would be missing. In reality, I've seen a 7-sided Reuleaux polygon being used (I think this was on someone's weird manhole cover picture blog :). I think that was very artistic and beautiful, for a sewer cover -- max

Because rotational symmetry allows them to be rotated in order to lock / screw them into place. - Taisto

So they don't fall into the hole. -rriker

Because manholes are round. 173.19.216.102 07:23, 18 February 2009 (UTC)

Manholes aren't "drilled," they're cast from iron or steel or whatever the manufacturer pleases—you'd need one hell of a hole saw to drill a manhole, and then you'd still have to engrave the logo/emblem somehow. Oh, and so long as you've got something to create molds with, you can create any shape you might desire. At that rate, the premise of the question—that other shapes are, in fact, easier to manufacture—is quite silly.--69.249.155.229 01:32, 25 February 2009 (UTC)

Why not equiangular triangles? --?

Suppose you had an equilateral triangle that measured 1 meter on each side, and was .05 meters deep. The smallest cross-section for this would be a rectangle that measured .866 meters in length by .05 meters. This rectangle easily fits within the equilateral triangle hole, within .116 meters from any of the sides, assuming no lip. Therefore, the reason they don't use equilateral (equiangular) is because they still fit within the hole. --Mark

I've spent a couple of years in the infrastructure trade, and yes there are other types and sizes. as a general rule, the rectangular ones are used when a larger access hole is requires. Say you need a lenght of 2m but don't need a big width the they use a triangular section cover which is the interlocking rectangle/square shape dicussed above. its easy to lift and replace and lighter than a massive circular manhole would be. Circular ones are used on road surfaces and for a few reasons. If you put the manhole back incorrectly, and a car drives over it, the manhole cover won't spin/fall and no traffic accident. The manhole cover is circular so it won't fall down the manhole when you are putting it back, roadsurface manholes are notoriously deep (+2m) and its a pain dragging a cover back up. third reason is safety, if you leave the manhole open and it falls shut, it won't come straight down the hole and smack you on the head. (this is the main reason i've been informed)

You can make a triangular cover that doesn't fall through. Buldge the sides out using a compass at each corner and draw it, so that the shape is constant diameter at every orientation. It's not a circle, try it.

You're describing a Reuleaux triangle, which is an example of a shape of constant width. There are infinitely more such shapes, but none are as easy to manufacture as a circle. Even if this is not the case, no other shape rolls as easily, and all must be oriented before placing back in the hole. 76.190.157.141 20:11, 21 March 2009 (UTC)

http://en.wikipedia.org/wiki/Manhole_cover#Circular_shape has answers. - oxy

[edit] Traffic Jams 2

• I think the center of mass of the jam moves backwards. While the accident is in place, the cars in the jam are moving at speed 0 while cars behind them are accumulating; the center of mass of the jam at this point is moving backwards with each car that piles in. Once the accident clears, assuming there are enough cars in place that they all don't just gun it, the front of the jam loses mass as cars peel away while the back of the jam still adds cars, meaning the center of mass of the jam actually moves backwards faster. The jam will clear only if the people in the front are so frustrated that they start leaving faster and with smaller delays than the cars getting clogged. DukeEgr93 15:44, 15 February 2009 (UTC)
  • On some satellite images you can actually observe this happening -- the traffic jam crawls backward along the highway like a living thing. If the flow of traffic remains roughly constant (so that cars going out are replaced by cars coming in) it can last forever!
  • Another really interesting visual of this can be found here Shockwave traffic jam recreated for first time
• It creates a standing wave that moves backwards. There has been a fair amount of research on this type of jam. The wave eventually shrinks through on and off ramps.
• The center of mass moves backwards if the cars have length, otherwise its fixed.
• The center of mass actually moves forward at 65 mph, if all drivers have perfect reaction time and acceleration. Reaction time and car length control the speed; acceleration controls dissipation (and it always dissipates backwards).

[edit] Delicious Cake

Are we allowed to use capital punishment? Enforces cake discipline and possibly leads to two parties getting half a cake each.

Person cutting picks last.

The first person cuts the cake into two portions. Each subsequent person selects any portion, and divides it into two portions. The last person does not cut, but selects a portion, out of all available portions. They then select their portions in reverse order (see below, this is incorrect) , but no one may select a piece not descended from their cutting.

The first person will cut out the correct size for him, leaving the majority out. The second will cut the same size out of the majority piece, and so on, until the second to last cuts the remainder in half. No one will make an unfair cut, since that would make some pieces bigger and some smaller; Those who cut after him would get the bigger pieces, leaving him with the smaller.

Anyone who makes a mistake gets a smaller share, with those cutting after him getting the larger share; Error punishes only the erroneous.

3-person example: A cuts first, slicing out 1/3 of the cake. B takes the 2/3 piece and divides it evenly. Perfect distribution. If A were to cut the cake in half, B would cut a small slice out of one of the halves. C would take the untouched half, B would get half, minus a sliver, and A would be left with the sliver. If A makes his cut fairly, and B divides his off-center, C takes the largest piece, B is left with the smaller piece he cut, and A gets the fair piece he cut.

If different portions of the cake have different relative value, then assume perfect knowledge, logic, and skill in cutting. The same rules apply.

• Actually, there's a mistake here. Assuming the cutting order goes A then B, we know that A has an incentive to cut the cake into a 1/3 piece and a 2/3 piece to ensure that she would get an equal piece; however, there is no reason B should cut the 2/3 piece into equal pieces. Say B liked person C more. Then, B could cut the 2/3 up unevenly. Then, C would pick the biggest piece, B would pick the 1/3 piece that A originally picked, and A would be left with the small piece. The way to remedy this situation is to actually have A choose the cake second. Now, if B wants to ensure that she gets an equal piece, she has to cut the cake evenly.
• So, if cutting is in the order A then B, then choosing happens in the order C then A.

• Not if the person couldn't choose a piece that they didn't cut (Except for person C, of course)

--

Alternative solution:

Assume there are N people.

The first person divides the cake into N pieces. The other N-1 people select (but do not take) the piece they would want, in any order. The cutter takes and eats the piece left over. Now recursively run the solution again with the remaining N-1 people and the remaining cake. Recurse until you get down to two people, then use the "I cut, you choose" method.

It's always in the cutter's interest to divide the cake as equally as possible; if there's a "smallest" piece, the cutter will be left with it.

This solution is, in my view, easier to understand, but the necessity of reassembling N-1 pieces into a completed cake for redivision makes it less practical in the real world.

- Graeme

• Perhaps score the cake instead of completely cutting it? Then you just smooth the icing over for each subsequent step.

--

Alternative solution:

You let each person cut a piece out of the cake. Each cut piece is shown to the people that don't have cake yet (except the cutter). If someone wants the piece of cake, the piece goes to that person. If no one wants to have the cake, the piece goes to the cutter. Then the next person gets to cut.

This will even work with more favorable pieces of cake. If you want a piece that you really like, you will have to cut it smaller or risk losing it to someone else.

--

Another Solution:

Take a knife and move it slowly over the cake. Whoever (including the cutter) thinks the piece is as large or larger as a third of the cake yells "stop", at which point the piece is cut and given to the caller. This works for every number of people, even if they have different priorities. The one who is last and doesn't yell stop is also garantied to get a piece he thinks is larger then 1/3rd of the cake.

--

A solution for the case of two people with different opinions of what makes the cake valuable (A likes frosting, B hates it):

Each person divides the cake into two halves that they feel are equal. A would have a small half with lots of frosting and a large half with less frosting, while B would have a large half with more frosting and a small half with less frosting. At this point, by definition, each person would be equally happy with either half by their division, so they each take their smaller half. This leaves a small portion of the cake in the middle. The process is repeated ad infinitum until the remaining cake is insignificant. Note that this doesn't work with dishonest people, and is not the most efficient division. A more efficient division would start with a smaller division than halves (such as each person dividing into 3 pieces and taking the smallest. The best solution would be with an infinite number of pieces)

--

There is a very interesting article on this problem in Notices of the American Mathematical Society ("Better ways to cut a cake" by Steven J Brams, Michael A Jones and Christian Klameler, Notices vol. 53 num. 11 p. 1314, Dec. 2006). They define a number of different desirable qualities that an algorithm may have. These are

Envy Freeness - Each person Thinks he got the best-or-equal deal.

Efficiency - No other allocation is better for anyone without being worse for someone else

Equitability - Each person gets the same value (according to their own valuation-function)

Strategy-Proofness - A person maximizes their worst case outcome via honesty (so lying always hurts the overall solution, but if your algorithm has this it also hurts the individual that lied.

For two players the normal Cut-and-Choose method is Envy Free, Efficient and Strategy-Proof but not equitable (Playing optimally, the person that cuts can't ever get more than 50% under their valuation, so usually the one that chooses does better). They provide an alternate method that provides this third property (which is basically the above solution except that it involves an impartial judge that the players tell their valuation functions to, instead of an infinite sequence of new 50/50 points).

In the case of three players they have an example that implies that Equitability and Envy-Freeness are incompatible (for their assumed limitations on how many cuts you get). There is a 3-person 2-cut envy free method and some envy free methods for 4 people, but no known envy-free method for more that had bounded number of cuts. Brams,Jones and Klamer do give an Equitable procedure for any number of players, though. They also show it is strategy proof (A truthful player gets at least 1/n of the cake-value no matter what the other players do, and a lying player may get less).

--

In a policy analysis class, I had professor who (rather satirically) used cake division as a way of demonstrating a dozen different versions of equity. As with everything in the class, the intended message got across (there are many different and often opposing ways of viewing fairness, so be aware) but most people left with a more cynical message in mind (fairness can and will be twisted to whatever supports the desired result).

In this case, I'd say have all three people hold a knife over the cake, with each knife meeting in the center. They are free to move their knife to whatever position they choose, and will get the piece to the left of their blade, but may not actually cut until all three agree. Since any move can be easily matched, and no one gets anything until there is agreement, they will either reach a fair deal, or no one get's cake (or there will be a knife fight, but if that's the case, they have bigger issues)

--

You cut, we choose. One person is selected to cut the cake. The remaining two will flip a coin to decide who chooses a piece first and then second after the cuts have been made. The cutter is left with the final piece. The only strategy for the cutter to maximize his result is to cut equal pieces. The same is true for any number of people (assume some other strategy to randomize the choosing order). The important thing is that each of the people who do not cut will have a chance to choose and the order will be selected at random after the cutting, which avoids any coalition between the cutter and a single chooser. I suggest that the cutter is the one with the most steady hand or the best spacial awareness so that they have a shot at making equal cuts.

[edit] A Special Place

The first, obvious place is the North pole. Walk a mile south, and however far you walk to the east or west, and the pole is always one mile to your north.

The infinite collection of places are near the South pole. Think of the circle one mile in circumference that lies at nearly 90 degrees south latitude. From any point one mile north of the line, you would walk to the line, circle the Earth once, then walk back to your starting point. Now think of the nearby circle with a circumference of one-half mile: one mile east or west on that line circles the Earth twice, leaving you back where you started.

In general, for each integer n > 0, define L(n) as the set of points on the line of latitude, south of the equator, of length 1/n miles; define S(n) as the set of points one mile north of the points in L(n). Starting at a point in S(n), we walk south 1 mile to a point in L(n), then circle the Earth n times, returning to the same point, then walk back north. There are a countably infinite number of sets S(n), each containing uncountably many points.

--Evan

What about a globe where the circumference was four miles, ie: a radius of 4/pi.

Since the globe has a radius of 4/pi, any combination of three mile long lines and two 90 degree turn projected onto the surface will result in returning to the same spot, provided the angles are both clockwise / anti-clockwise.

To summarize, there is an infinite collection of latitudinal circles near each pole for which every point on the circle satisfies the problem. In addition, the North Pole satisfies the problem. Finally, the South Pole and the portion of the globe less than or equal to one mile from the South Pole actually satisfies the wording of the problem, because the question is phrased "if you walk south 1 mile . . . ," which is an impossible premise at those locations, thus making the if-then statement true there. 76.190.157.141 06:26, 16 March 2009 (UTC)

I may be taking this completely the wrong way, but we had a perfectly smooth earth (so rivers valleys etc are gone, and a perfectly spherical earth, as such then this removes the slight bulge in radius around the equator. so as such, wouldn't any point on the sphere have the same geography as the north (or south)pole and thus anypoint on the earth fill the criteria? (this is more a question than an answer so please confirm or deny how accurate i am)

Every point on the sphere is geometrically identical, but we defined a set of coordinates on it such that a given (arbitrary) point is "North." That is sufficient, I think, to distinguish every point on the sphere, assuming we take clockwise and counterclockwise ("East" and "West") from above to be distinct. Besides, think about it: Obviously if you are standing at the equator, walk one mile south, one mile east, and one mile north, you will no longer be at the point where you started; in fact, you will be approximately a mile east of that point. 76.190.157.141 18:53, 17 March 2009 (UTC)

The sphericallity (a real word?) of the globe is irrelevant in determining the poles. The poles are defined by the rotational axis. Granted, rotation is the reason for the equatorial bulge, but this is an example of common cause, not cause and effect.

-Greg

The axis of rotation is the way we define the poles on the Earth, but the reason is not important. The fact that we define poles at all implies that each point on the Earth is geographically distinct. 76.190.157.141 20:13, 21 March 2009 (UTC)

Oh, and obviously you need a Prime Meridian, too. I sort of forgot to mention that. 76.190.157.141 00:58, 14 April 2009 (UTC)

One of my favorite. I always puzzle my friends with it, but slightly changed. Instead of asking where they are, they get attacked by a bear and should tell its color :)

That's a classic version, although typically people give the erroneous answer that the way the problem is stated implies one must start on the North pole, when in fact there are infinite circles upon which one could be, half of which are on Antarctica, where there are obviously no polar bears. But admittedly, if one satisfies the conditions of the problem and is then attacked by a bear, it is probably a polar bear, and they are probably within a 1.159 miles of the North Pole, because they certainly aren't at the South Pole. 76.190.157.141 00:57, 14 April 2009 (UTC)

[edit] The Necktie Paradox

There certainly is a problem: two different meanings of "the value of my necktie" are used interchangeably. In the faulty analysis, "I lose the value of my necktie" means "I lose the value of the more expensive tie" while "I win more than the value of my necktie" means "I win more than the value of the cheaper necktie", or more accurately "I win the value of the more expensive tie."

We have two ties, T1 and T2, worth t1 and t2 dollars respectively, where t1 < t2. There is a 50% chance that you have either one. If you have T1, then you will win t2, but if you have T2 you will lose t2. Now the expected value of taking the bet is t2/2 - t2/2 = 0.

--Evan

This doesn't resolve the paradox. If we assign a dollar value to one tie but don't know if it's the more expensive one, we still have the paradox. To avoid confusion, let's label the tie in unknown state (we don't know if it's the pricier one) TA. If TA has a price of $10 then there are two cases. If TA is T1 (the cheaper tie), then you gain more than $10. If TA is T2 (the more expensive tie) you lose $10. If the probability is 50/50, you do indeed have an advantage. This is the same as the envelope problem. Evan's analysis is correct until you assign a dollar value to one tie.

-Ari

• Ari, I don't understand your objection. What does your "If we assign ..." have to do with this problem, as stated? You seem to be saying that I am correct until we change the problem into a different problem. Even then, your analysis is incorrect; it can be paraphrased as "if my tie is cheaper, I will win the value of the more expensive tie, but if my tie is the more expensive tie, I will lose the value of the more expensive tie." You are confusing yourself by changing the value of "the more expensive tie" between the two cases. Just as in the envelope problem, unless you know the probability distribution for the values of the ties, knowing that the value of one of them is $10 does not help you at all. --Evan

  Evan, this is a paradox because depending on how we approach the problem, we arrive at two different conclusions.  Your analysis
  is correct and leads to the conclusion that there is no benefit to the game.  My analysis is also correct and leads to the
  conclusion that there is a benefit to a player of the game, hence the paradox.
  
  My approach is quite simple and does not involve changing the value of "the more expensive tie."  The only assumption required
  is that whatever the price of Tie 1, Tie 2 is 50/50 to be more expensive or cheaper, in other words, it assumes an infinite
  uniform distribution, which is quite reasonable based on the question.  Just try it out.  Pick any value you want for the first
  tie.  Then do the arithmetic.  
  
  If you still don't believe this approach is valid, consider this.  Let's say you and I were actually playing this game and a
  third party read the game to us.  In other words, the situation is identical to the problem.  I happen to turn my tie over and
  realize the price tag is still on the tie.  I haven't gained any new information about whether my tie is more or less expensive,
  and yet the situation now fits into my analysis (i.e. if the price tag says $10, I'm 50% to lose $10 and 50% to win more than
  $10).  If you want to argue that the discovery of the price tag fundamentally changes the game then you're in trouble; if we
  agree that both ties have an infinite uniform distribution of possible prices, then finding the price tag on one tie gives you
  absolutely no new information, since literally any price on that price tag leads to the same analysis.

-Ari

• Ari, the only way your assumption could be true would be in case of a uniform price distribution infinite in both directions, ie the prices of the neckties could be negative. --Djak

What's the problem here? Each person has a 50% chance of winning, and 50% + 50% is 100%. --anonymous

This is a special case of the two envelope problem in which they cannot see the contents of their envelope. I suggest we just merge it with that one. -- DanielLC

• Absolutely, the expected value that each man walks away with is the same; (tie 1 + tie 2)/2 just as with the envelopes. -- TLH

The statement "I have a 50% chance to win" is wrong. And the seeming paradox vanishes when you compare "I will win a tie worth more than my tie" to "I will lose a tie worth more than the other tie"...

The envelope riddle in its current form doesn't make any sense - if you think they're both the same, it's the one that should be removed.

Iri

[edit] A Night at the Opera

Anyone who sits in their intended seat (other than the last person) can be ignored, as since no-one sat in the seat before they got in, they might as well have been in it all along.

The first person has a 1/N chance of picking their own seat (and then obviously the last person gets their seat). They also have a 1/N chance of picking the last person's seat (when they obviously don't). In any other case, someone else has to randomly pick a seat with a 1/N' chance of picking the first person's real seat (last person gets own seat), a 1/N' chance of picking the last person's seat (last person gets wrong seat), and in any other case someone else has to randomly pick a seat, go to the start of this sentence.

If this isn't sorted out before the penultimate person, they have a 50% chance of picking the 1st person's seat and a 50% chance of picking the last person's seat, and the branching probabilities finally end.

At any stage, the chance of a successful exit is the same as the chance of an unsuccessful exit, so the final chance after everything is cancelled out for the last person is 50%.

(Unless of course, there's only one person and only one seat, in which case they have a 100% chance of getting it right)

The obvious extension of the problem: given N seats, what are the chances that the Kth person in line gets the right seat?

• • I think the probability that the kth person gets their own seat, out of N, is 1/N if k=1 and (N-k+1)/(N-k+2) if k>1 DukeEgr93 20:21, 17 February 2009 (UTC)

[edit] Three Men and a Bellboy

• "Now, the three men have each paid §9, a total of §27. With the bellboy's §2 this only amounts to §29, where did the other § go from their §30?" - The stimulus? DukeEgr93 18:38, 17 February 2009 (UTC)

For purposes of the puzzle, let's say that each man enters the hotel with §10. They each pay §10 for their room, so now the landlord has §30 and the men are all broke. Then the landlord remembers the special offer, and gives the bellboy §5 to take to the men - at this stage, the landlord has §25, the bellboy has §5, and the men have nothing. The bellboy keeps §2 and gives the rest to the men, so the location of all the money is:

§25 with the landlord

§2 with the bellboy

§3 with the men

So, of course, all §30 is accounted for. The 'disappearance' of one § is due to an error in the puzzle's logic. We have to look at the whole puzzle as one exchange, not a series of exchanges. The puzzle assumes that all §30 involved was the total amount of money that changed hands; but ultimately, §3 went back to its original owners. Thus, only §27 was displaced; §25 went from the men to the landlord, and §2 went from the men to the bellboy. --70.104.241.91 20:07, 17 February 2009 (UTC)

I found the above explanation a little confusing but perhaps I'm saying the same thing. When the puzzle says "the three men have each paid §9, a total of §27" That is $25 for the room, AND the $2 the bellboy received. So the part of the question stating "With the bellboy's §2 this only amounts to §29" is gibberish, the bellboys 2 is in the 27.

Right, the explanation of the puzzle contains a misleading factual error. The $2 is added to the $27 when it should actually be subtracted.

Actually, it should be ignored, not subtracted, otherwise you would be 2 dollars short. (27-2+3=28)

I feel the following may be relevant to this puzzle: http://xkcd.com/169/

I don't think this is a particularly "counterintuitive" or "tricky" puzzle. The only tricky part is that you deliberately mislead people with the $29. Which is fine - but I don't think it fits the spirit of this page.

[edit] The Four Numbers

Consider a*b*c*d. We can obtain this product from our partial products in three ways:

(a*b)*(c*d), (a*c)*(b*d), (a*d)*(b*c)

Two of these pairs exist among our five, and one is missing. We therefore find two pairs of numbers in our five which have the same products. In this case, it's 2*6=12 and 3*4=12. The remaining pair must also have the same product, so it is 5*(12/5)=12 -Tiax

No, just because you found 12 doesn't mean that's the only possibility. The problem forgot to state that they are positive integers (otherwise their is no unique solution). Taking that into account, see that you are given 2, 3, and 5 as products. These primes indicate that there must be a 1 in the set of four. The six products are therefore: 2, 3, 4, 5, 6, 15. According to my solution, the above uses (1*2)*(2*3)=12 and (1*3)*(1*4)=12, doubling up factors in both cases. -Matt

2, 3, 4, 5, 6, 15 doesn't make sense to me. As I said above, you need to have a constant value for a*b*c*d, but I don't see any way to get that with the 15. Suppose that we call 15 a*b. We have five options for c*d. These yield the values for a*b*c*d of 30, 45, 60, 75 and 90. In none of these cases can we pair off the remaining four to obtain the same product.

Also, are you sure it's supposed to be only integers?

-Tiax

There is no solution for integers. The primes indicate that, necessarily, 1, 2, 3, and 5 are a, b, c and d. However, none of these multiply to 4. --Mark

The four numbers are definitely *not* integers. There's no solution for integers. In particular, the missing number isn't integer, either. --Quiss

Matt's solution can't be right -- he is mixing up the products (the numbers given in the problem) with the original a, b, c, and d. Mark is also correct -- if the solution were limited to integers only, the existence of three primes among the products would force the fourth original number to be 1, and make the existence of the 4 among the products impossible. So by contradiction, the original a, b, c, d cannot all be integers. The more I think about it, the more I think Tiax is right, the sixth product must be (12/5). So now... can we come up with four numbers a, b, c, and d such that their pair products are 2, 3, 4, 5, 6, and 12/5?

Before I go on, I want you to note that it doesn't matter which products (ab, ac, ad, bc, bd, cd) we assign to 2, 3, 4, and 6 as long as we keep the fact that ab*cd = 12, ac*bd = 12, and ad*bc = 12 true. It's only going to affect the final distribution of the names 'a', 'b', 'c', and 'd' among the four numbers we eventually find. (You can prove this, if you doubt it, by messing around with variable substitution for a while, but I won't prove it here, because that's long and I'm tired. Suffice it to say, it's true.)

Assume for the minute that ab = 6 and therefore cd = 2. Thus ab/cd = either ac, ad, bc, or bd, because one of those other multiples must be 3. Exactly which is irrelevant, as I mentioned above. Let's pick 3 = ac. Then 4 = bd. Now a whole bunch of relations are possible. 2ac = ab, thus b = 2c. 1 + cd = ca, thus a = d + 1/c. I'm too tired right now to come up with a solvable system, but I think that from ab = 6, cd = 2, ac = 3 and bd = 4 we should be able to either:

a) find a, b, c, and d, and prove that either ad or bc = 5 (which one this is DOES matter because it adds another, non-symmetric constraint to the distribution of names, and I don't know whether it'll be ad or bc just from glancing), or

b) find a, b, c, and d, and prove that neither ad nor bc = 5 (in which case the premise of the question is false), or

c) show that there are no such a, b, c, and d that satisfy the system I began above -- although I doubt this to be true. -Riker

Thinking about what I said above again, you could also add constraints like bd + ab / cd = {either ad or bc} to bring the 5 into it. Or get simpler and write bd + 1 = {either ad or bc}, or ab - 1 = {either ad or bc}. But you might have to write up two different systems (one assuming that ad = 5 and one assuming that bc = 5) and try to solve both of them separately. -Riker

You had to go ahead and do that, didn't you? I don't know if it's the only solution, but I got (in arbitrary order) a = 4(3/10)^.5, b = 5(3/10)^.5, c = (3/5)(10/3)^.5, d = (10/3)^.5. Thus ab = 6, ac = 12/5, ad = 4, bc = 3, bd = 5, and cd = 2.

For people who prefer decimal representations, a ~ 2.1909, b ~ 2.7386, c ~ 1.0954, d ~ 1.8257.

The way I solved this was by a stroke of luck: I made a 2x2 "magic square" of products (the entries in the squares are, clockwise from upper left, a, d, b, and c), with expected products of columns, rows and diagonals written in around the exterior of the square. I chose the columns to be (left to right) the pair 12/5 and 5, and the rows (top to bottom) to be 4 and 3. I figured that since 12/5 and 4 were related by an almost-factor of 4, we could put 4X in their shared box, and (3/5X) in the box beneath it.

From here I went to the other column, which was easy: the upper one had to be (1/X), while the lower one had to be 5X. Diagonally, these multiplied to 20X^2 and (3/5)X^-2. Knowing that these had to equal 6 and 2 (respectively), and more specifically that one was three times the other, I solved for the equation 20x^2 = (9/5)x^-2. That's where the factor of (10/3)^.5 comes from.

I hope you've enjoyed this presentation. I'm going to go sleep. --Mark

OK, the way I approached this problem was as follows:

you have four numbers: a,b,c,d

Assume the produce cd is not listed.

That means you can say that 2*3*4*5*6 = 720 is the product of 2 cubes and 2 squares

Thus, (a^3)(b^3)(c^2)(d^2) = 720

There are no integer solutions to this problem, so that's one way of proving there are no integer solutions. --Nathan

I can confirm that Tiax is correct and that Mark's solution is unique. Once you have 12/5 as the final product you can determine what the value of each pair is. You can then use these numbers to find b, c, and d in terms of a. Multiply these 4 terms together and set it equal to 12. Solve for a, then solve for the rest of the numbers. - Hannibal

Let the Pair to be found be cd, an obvious statement to make is cd = (ac*bd)/ab by the same logic cd = (bc*ad)/ab. Equating these we obtain (ac*bd)/ab = (bc*ad)/ab this gives us that ac*bd = bc*ad the only solution to that from the numbers given is that this (3*4) = (6*2) =12 and ab = 5 thus giving cd = 12/5 -Donnie

I just wanted to add that using the approaches outlined above you actually do arrive at a (unique) solution for a<=b<=c<=d, which in my opinion is a=2*sqrt(2/5); b=sqrt(5/2); c=6/sqrt(10); d=sqrt(10). If you play around with them you should find that they work out nicely. -Firionel

[edit] The six poisoned wells

Is it possible to tell if you have been poisoned or cured? If the knight drinks from well 1 and the dragon gives him well 2, can the knight tell if he is still poisoned and should look for a cure, or is he uncertain until he dies? I'm assuming the latter case.

One way for the dragon to always survive is to drink nothing beforehand, but after drinking the knight's poison, drink twice from well 5 and then drink from well 6. If the knight offers any poison but well 5, it will cure it, and the second drink will be cured by well 6. If the knight offers well 5, the first 2 drinks will do nothing and well 6 will cure it. If the knight offers clean water, the drinks from wells 5 and 6 will cancel out. I'm not sure if there's a similar strategy for the knight, because he doesn't have the cure-all of well 6.

I don't believe it's possible to guarantee a win. Anything the other side offers can be canceled out by choosing some appropriate drinks either before or afterward. Therefore, if there was a winning choice of poison, one player would know that the other would always pick that strategy and would be able to pick the drinks before or afterward that would cure the winning strategy. --66.42.183.212 18:47, 18 February 2009 (UTC)

In a similar vein, the knight should show up sick with well 1. Then afterward drink twice from 4 and finally from 5. If the dragon gives him 2-6, then it will cure 1, knight will get sick with 4 and cured with 5. If the dragon fives him lake water, then 4 will cure 1, get sick with 4 again and cure with 5. It appears there is a fool proof strategy to live, but none to die.

• This solution assumes that if you drink two glasses of poison, one glass of antidote will save you (i.e. quantity does not matter). It should be made clear, whether or not this is the case.
  • If quantity doesn't matter, the puzzle is dumb, since both the dragon and the knight will conclude that they can not poison each other, and decide the duel in a game of backgammon instead.
  • If quantity does matter, the puzzle is dumb, since it is equivalent to rock-paper-scissors.
    • Anyway, the problem statement sucks, because the hint tells you the "solution" :(
      • I agree, it's the only thing counter-intuitive about the puzzle. Anyone care to remove it? --24.170.227.66 06:44, 20 February 2009 (UTC)
        • Strategically speaking showing up with water from the lake is the best option. It is not poisonous, yet as the dragon you'd go to well #6 to clear the poison, and die from the strongest poison.
          • No, it wouldn't. The dragon doesn't just go to well #6, he first drinks from well #5 twice, and then once from well #6, curing himself in any situation, as explained above. Also, I agree this is a vague puzzle.
            • Took the liberty to remove the hint and also redefine the question to "is it possible to survive this duel". -Quiss

The guaranteed winning sequence for either character is 1,X,1,5. -- Hairy Phil

Along the same lines, and to minimize ingested poison values, 1,x,1,2 does the job just as well. I would also call it t he guaranteed surviving sequence rather than winning.-JG

Not just so. The dragon can easily survive with X, 1, 6: he need not start by drinking a poisonous draught. -Jon Werts

If the knight gives the Dragon lake water- any well the dragon drinks from will poison him.

The dragon can guarantee the knight dies by giving him well 6 water. If the knight gives the dragon any well water it can cure it by drinking from well 6, but if it was lake water that would kill him unless he drinks from another well first. However the confusion comes from what happens if he drinks multiple poisons that do not cure each other first (what if someone was given well 5, but they first drink 2 before they drink 6?). Unless I'm misinterpreting the rules, than the second post is the correct solution.

• The dragon does not have that guarantee because the knight can drink from well 1 before the duel begins, in which case the well 6 water would cure him. The dragon can counter this by giving him fresh water or well 1 water, so the knight must add on the safeguard of drinking from well 1 and then well 2 after the match, which will nullify everything. (same works for the dragon, just imagine well 6 doesn't exist)

[edit] The 3 houses and 3 supply stations

I don't think this one is in the spirit of the other questions; a "trick" of some sort is required (e.g., running the gas lines through/under a house, etc). In the spirit of the question (at least for mathematicians!) the answer is that it is impossible the graph <math>K\sub{3,3}</math> is not planar, i.e., cannot be drawn on a plane with no intersecting lines. I vote for deletion or at least reworded to ask "Is it possible..." --JoelG 07:20, 20 February 2009 (UTC)

• I support this cause.--24.170.227.66 07:25, 20 February 2009 (UTC)
• Agree --Luke

reworded --author

The problem with the problem is that the definition for "crossing" is so vague. If the problem takes place on a plane, it seems logical that "crossing" must mean "intersecting" (unless one allows for solutions that involve circumscribing one wire within another wire, to wire the houses so that the three carry the powerplant's electricity as a series circuit, ones that seem kind of bs), whereas in the real world it's not as easy to define... namely since there are some three dimension figures for which I believe this would work. Assume that we can find some sort of naturally occuring torus on earth, such as a naturally formingland bridge (which certainly exist, and since we are given no restriction on the length of the wires/pipes we can certain get to from the house), is it considered "crossing" to, for instance lead one win through the arch of said land bridge, then lay the waterpipe through the bridge's opening (or whatever combination)?

In other words are we allowed to take the sheet of paper that we draw this problem on, attach some kind of tube thing at two separate points, forming an arch over the paper, through which a pipe may be fed through? It all depends on what it means for these gas/water/electricity lines to "cross"... they don't "intersect" per se, but if we send a paper airplane flying over a street, we do, in common parlance, say that it has "crossed" the road.- Rothul

[edit] Two Janitors, One snowstorm, two carts

Two snow-based factors influence the speed of the janitors. One is the contribution of lateral momentum to the snow which accumulates (even momentarily) on their carts. The other is the fact that their path is becoming covered in snow. The first does not cause any discrepancy in speed between the janitors, as both lose an identical quantity of speed in bestowing momentum to the snow. Therefore, the discrepancy (if any) lies in the second factor.

Which method better allows for retention of cart speed? The more massive cart will (generally speaking) be less effected by snow on the ground, as it will have retained its forward momentum; the less massive cart (where the janitor was removing snow) will have lost momentum in the snow scooped onto the side of the path.

Therefore, the lazy janitor is following the correct strategy.

One complication to this problem involves compaction of snow on the ground, an effect similar to that of friction. As the more massive cart will necessarily compact the snow to a greater degree than the less massive cart, it will experience more friction on the surface of its tires, as well as a greater amount of energy lost in the compaction of the snow. At a glance, this will have less effect on this speed of the carts than the earlier-described second factor, and so is ignored in this treatment.--Mark

-- I feel in the spirit of the question that the answer is "no difference". Once you start considering the effect of snow accumulating on the path, it's got to be inappropriate not to consider friction - both are "real world" phenomena, and without external knowledge it's not obvious to me that the friction effect will be smaller than the pushing-snow-on-the-path effect. JoelG 23:47, 22 February 2009 (UTC)

-- I'd like to offer another perspective. Assume that all snow falls vertically, so that if 1kg of snow falls on a cart of mass 10kg travelling at 10m/s (numbers chosen to exaggerate effect) then the final velocity would be 9.09m/s. The momentum of the system is still 100kgm/s. The tidy janitor removes the 1kg of snow quickly, keeping a velocity of 9.09m/s and reducing the mass of the system (the cart + janitor + any unremoved snow) back to 10kg and thus the momentum of the system to 90.9kgm/s. Another 1kg of snow falling on the cart would reduce its speed to 8.26m/s. The lazy janitor does not remove the snow, so that its mass is now 11kg and the system's momentum is 100kgm/s. Another 1kg of snow falling on the cart would only reduce its speed to 8.33m/s. Therefore the difference is that the tidy janitor discards accelerated snow, reducing the momentum of his system. By using the increasing weight of his system to his advantage, the lazy janitor will lose speed less rapidly. So sad to see hard work go to waste...--TKG 21:13, 23 February 2009 (UTC)

• Could a smart janitor speed himself up by sweeping snow backwards? Or would it be better to keep it onboard to take advantage of the extra weight?

• The lazy worker slows down first, assuming finite energy. {Neither, if we assume infinite energy.} In a frictionless system, momentum and ground conditions are meaningless, absent collision events. Assume 1k/s snowfall, 10kg starting weight, 10m/s starting velocity. 1 second passes. The lazy worker 50 joules to maintain velocity. The diligent worker spends 1 joule to move 1kg total of snow 1 meter to push it off the side of his cart. The diligent worker is constantly clearing the snow as it falls, thus spending 1 joule per second to keep his cart at its initial weight, thus requiring no additional energy to continue the forward motion (no friction = momentum conserved). The lazy worked must spend 50 joules per second to maintain momentum. Ta! Some random internet guy 22:46, 24 February 2009 (UTC)

[edit] A Very Good Predictor (Newcomb's Paradox)

The answer to this question remains disputed. One side argues that it is always logical to also open Envelope B, because your choice of action does not effect the contents of Envelope A. The other side argues that the type of person who would only open Envelope A will benefit athousandfold, and that it is categorically impossible to alter one's own tendencies while engaged in the game.

Essentially, this "puzzle" challenges peoples' notions of free will. I'm sorry if it is inappropriate for this page (not having a set-in-stone solution), but it provoked many a fun argument over breakfast. It's a paraphrased version of Newcomb's Paradox--Mark

I think it's fair to throw away any thoughts about free will (and many other things) when you see that the computer has predicted your every move over the five years. I'd feel very confident opening only Envelope A. By opening both I'd be essentially doubting the predicting ability of the computer by choosing to win the million only when the so far infallible computer is wrong, just to secure $1k. Apart from being stupid from an empirical sort-of viewpoint, I can't think of a single reason why this decision wouldn't be just as predictable as everything I have done up to this point, and therefore an almost certain return of only the $1k. Maybe I'm missing something or just stuck in one way of thinking? This doesn't feel like a paradox to me at all. -Nix

I'd open both. Then I get either $1,001,000 or $1,000 - win/win. Who gives a toss what the computer predicted?

The strategy that wins is to open only A. I'm not so attached to rationality that I would not abandon it when I'm in a case where it's a losing strategy. Then again, the outcome of this hypothetical (assuming an omniscient computer) is predetermined anyways, so I guess I'm lucky that I'm one of those that gets $1000000 :)

It's not a classic paradox, because it assumes that supposedly fundamental properties of the universe (that the future is not knowable, and/or that the present cannot affect the past) is false. In the hypothetical universe presented by this question, it seems that, for all practical purposes, what you do now can influence what the computer chose in the past, therefore, opening only envelope A ensures that the computer predicted you would do so, and therefore opening only the one envelope is correct.

What if the computer was only 99.99999% accurate? While it'd be difficult with present technology, it wouldn't necessarily contradict any universal laws.

Come on, this one is easy. I would first open only A. If and only if it contains $1,000,000 I would open B, and take the other $1000. The computer cannot make any mistakes. But in this case, if it had predicted I would open only A, because of that I would open both envelopes, but if it had predicted I would open both of them, I'd only open A. This would mean the computer cannot predict my actions, it would be a paradox for the computer, not for me, and the computer would go in an infinite loop or crash or something like that. This means that the contents of envelope A would be in superposition, or more probable: the game would never have been initiated and you wouldn't have to choose, so the paradox doesn't happen and well, then the game could be played so the paradox DOES happen and... this brings us into the realm of time and causality paradoxes.

Another weird thing: This paradox thing won't happen when, after you find out A contains the note, you get angry because you got $0 and angrily open B to get the other $1000...

As Cptn Janeway said: Time travel paradoxes - it all gives me a headache.

A valid point. Altering the question to prevent such gaming of the system...now! --Mark

So the way I look at this problem is that the predictor isn't perfect (it is stated in the origional description of the paradox that the predictor can make a mistake) then it has some accuracy (we may not know what it is, but it's something that could be measured) Take the following cases.

The very bad predictor: The contestant in the game doesn't know it, but we were on a budget and couldn't afford a future predicting super computer, so instead we flip a coin, heads we put the money in envelope A, if it's tails we don't. In this case your expected payout is 1000000 *.5 if you pick a or 500000 and 1001000 *.5 if you pick A and B or 500500. It's better to pick A and B.

The Not So Good predictor: The last game was kinda lame, because the predictor was always wrong, so picking both A and B was the best choice, but we still don't want to spend a lot of money, so before the contestant is posed the big question, I go online and look up all his comments in Newcomb's Paradox discussions, and use these to decide weather or not to put the money in the envelope (For the sake of argument the contestant is unaware of my method and can't use it to his advantage). It's not a great predictor (people rarely act the way they say they will) but it gives us a slight edge, and we can now predict with 60% accuracy. I don't think that such a predictor is unrealistic (team of FBI profilers or even avrage responce of 1000 people could probbly do this well) In this case the payout for picking A only is 1000000 *.6 or 600000, and the payout for picking both is 1001000 *.4 or 400400. Even with this fairly poor predictor, because the money in envelope B is so small, it works out to your advantage to pick just A.

Just my thoughts on the issue.

-Andy

I'd open only B. Predict that, Mr. Fancy-Pants Predictor! -Tiax

     You can't, the rules state it's either A or A and B, you can't pick B by itself. --69.243.52.144 08:15, 4 March 2009 (UTC)

If the Computer is 100% accurate, then the answer is that you can't choose one way or another. The problem assumes you don't have free will. If the computer is just 99% accurate, then there is assurance you have free will, and the computer is just really good at guessing. In that case you may as well take both envelopes, because the contents of envelope A aren't going to change after the fact. --- If you assume that 100% accurate prediction precludes free will then (I think) free will becomes impossible. Any decision either has a reason for it which you follow every time (making predictions possible to make at 100% accuracy, even if it is very difficult), or ones that are defined either arbitarily or which could go either way, perhaps due to competing influences. This is not easy to predict acurately, but makes your actions random chance. This reduces all actions to either certain or random (I would quite like someone to point out the flaw in this argument, it depresses me). If however, you accept that decisions can be both 100% predictable and done by choice, the problem disapears. Anyway, relating this to the puzzle, we know that the computer can predict in advance the outcome of anything random in advance, otherwise the computer fails as soon as your life is affected by anything random (or there is nothing entirely random in the universe, in which case none of your actions are truly random either, and you will always act the same way in the same situation). Therefore, if your uncle is telling the truth, which is entirely possible, you pick box A, and gain £1M. If he is not telling the truth, then either he put the money in box A, you pick A, you get 1M, or he didn't you pick A, and you can be insufferably smug towards your uncle about tricking the computer for a mere £1000 (serves him right). Therefore, as long as you value proving that the prediction was wrong at between £1000 and £1M, the correct nswer is always A. In my case, I do, so I would pick A.

The problem's assumptions about free will are tangential: its explicit concern is reverse causality. That is to say, the problem does not assert that the Predictor's prediction for this game must be correct, it merely asserts that all previous predictions made by the Predictor have turned out to be true. Therefore, there must be no reverse causality in play.
-If you're the type of person who would take both envelopes because the contents of Envelope A aren't going to change based upon this, you'll almost certainly find that the Predictor guessed as such, and you'll have to make do with $1,000.
-If you're the type of person who would take just the one envelope, you'll also almost certainly find that the Predictor guesses as such, and you'll have to make do with $1,000,000.
Now, that's not saying you have no free will: your free will is in the decision of what type of person you are. If you wish to apply this directly to the game, consider what would happen if you deliberately acted contrary to your normal belief structure, and try and bear in mind the difficulty of that task.
-You're a one-enveloper, but inside the room you find a way to spontaneously change your life philosophy. You question your deepest, darkest views of the nature of existence. You take both envelopes, and make out with $1,001,000. That's a net increase of .1% over your previous winnings. Not very rewarding, in the grand scheme of things.
-You're a two-enveloper, but inside the room you find a way to spontaneously change your life philosophy. You question your deepest, darkest views of the nature of existence. You take one envelope, and make out with $0. That's a thousand dollars you just lost, out-of-pocket. Not rewarding at all.
While you can exercise your touted free will in this game, please be aware that doing so won't be a rewarding endeavor. --Mark

I'm not that good at explaining things, and the philosophical nature of this discussion doesn't help, so I'll just say the same thing several times in different ways and hope you can understand it.

As an Eternalist I figure if you say that you might as well pick A and B because the computer's choice is already certain, then you might as well say that it doesn't matter, as how much money you get is already certain. Causation is a simplification. It's correlation that really matters. Before I make my choice, I don't know what the computer predicted. My choice gives evidence of what the computer predicted. As such, I should make the choice that gives the most evidence that the computer predicted that I'd only choose A.

You people seem to be acting like there are three states: Uncertain, Unknown, and Known. Anything Uncertain, you can change. Anything Unknown, you can't change, but you don't know. Known is self-explanatory. It makes no sense to me. There is only one future. It's every bit as real and unchangeable as the past. There is only Unknown and Known. When you make a decision, you learn what you decided. That information allows you to predict other things. If you decide to drop a ball, you know it will fall. If you decide against it, you know it won't. Make the decision that tells you what you want to know.

The probability that the computer predicted that you'd only choose A given that you only chose A is higher than the probability that it predicted that you'd only choose A given that you chose both, therefore, you should only choose A. --DanielLC

I have to throw a wrench into the works. This prediction would be different from all previous predictions for 2 reasons. 1. You have never previously known about the predictor, and the knowledge that your actions are being predicted may change your decision/your decision making process. 2. Even more, you are making a decision based on what is being predicted. Thus it is even more likely that either you or the predictor would come to a different decision/prediction. Now, the predictor may be able to cope - but we don't have evidence for that--the previous 100% accuracy does not tell us if the predictor will likely be accurate here. Even if the predictor is accurate under such circumstances, you might get into a decision making loop. Normally, you would choose only A (or A and B), but you know that the predictor knows that, so you can safely pick A and B. But you know that the predictor would know that you might change your might, so you'd better not. But you know it'd know (etc etc etc). And maybe you'd know when you'd stop the cycle, but maybe you ended up falling asleep and accidentally grabbing one or the other of the envelopes. - Stephen

[edit] Probability, and a barrel of balls

I posted this problem a couple of days ago... perhaps it doesn't flow with the mojo of this site... feel free to delete it. Although, since posting it, I've come up with (what I think is) a nifty recursive solution, but I can't quite see / explain the logic of it, yet. I'm antsy to see if someone can do better. If this problem still exists in another couple days, I'll post my weak-ish recursive solution.

I think I have a non-recursive (but with a summation) general solution for the probability of having seen exactly X balls after K takes. Obviously 0 if K < X or X > N, otherwise N! / (N-X)! / N^K × { sum A=1..X: [ (-1)^(X+A) × A^K / A! / (X-A)! ] }. For having seen all the balls, just replace X with N. That eliminates one term but I can't see an opportunity for any real simplification. I wrote an almost complete proof using induction as well as verified that the formula works in some basic cases, but I've been known to make mistakes... All that is too much to copy here and frankly, a mess. I'd love to see an elegant way of getting the solution (even just for X=N), or even how to simplify this one further.

Anyway, I'd consider removing this problem from here. I wouldn't call it a puzzle as much as a math problem, and quite heavy at that unless I missed a serious shortcut or one settles for the most basic recursive solution. Or maybe add a note in the problem description? --Nix

It seems to me like the problem shouldn't be too difficult, but I am having problems with it. The sample size has N^K permutations, for each pick there are N possibilities and this is repeated K times, but I now question my initial conclusion that it therefore has N^K / K! combinations, since that depends on how many of the balls you picked were the same and how many were different. The number of successful combinations is 0 for K < N (obviously), and I believe N^K-N otherwise. If this is true, my initial guess for combinations must be false, because the probability for K > N would be K! / N^N, which often gives results greater than one. Any ideas? 76.190.157.141 21:16, 12 March 2009 (UTC)

I think i've figured out, for K >= N fixed we have that the outcomes that doesn't shows all the symbols are N(N-1)^K (N times the outcomes that doesn't contain a fixed symbol) so the outcomes that contains all the symbols are N^K-N(N-1)^K and thus the probability is 1 - N((N-1)/N)^K (which goes to one as K goes to infinity which is good because on an infinite trial eventually the N balls will appear). Bunder 200.104.73.121 00:01, 14 April 2009 (UTC)

[edit] The bartender

The daughters are 2, 6, and 6. Knowing the product and sum of their ages doesn't solve the problem for the mathematician, which means that there must be at least two possible ways of distributing the factors of 72 which leads to identical sums. These are 3, 3, 8 and 2, 6, 6. The last bit of information tells you that there is a "youngest" daughter, which implies that the 3, 3, 8 combination can be ruled out. Of course, this is also debatable - even when twins are born, one is older, one younger. --Mark

That’s why I’ve written that age must be thought of as an integer in this problem. As some people pointed out to me, parents often make a clearer distinction about who’s older when they have twins, so this is a weak point of the problem. I still like it though. --OP

In the puzzle, which i've seen before, it says that the sum of their ages equals something. In this case it would be 14. But in this version of the puzzle posted on the page, there's no saying that it could be 14. Why can't their ages be 1 8 and 9? All the conditions are still met. Multiplying Gives 72, There is a youngest (Which in this case doesn't matter) and you can still add their ages up to an integer, which is the only restraint on the house number (i don't know of any negative house numbers). I'm pretty sure the puzzle is supposed to include the fact that the house number is 14. Does anybody see a problem with my logic? --Mat

Wrong talk section: fixed. *coughs* We assume the mathematician knows where the bartender lives. If the mathematician knew they lived in a house with house number 18, he would reach your same conclusion: that their ages are 1, 8 and 9. However, we know from the statement of the problem that the mathematician is unable to determine their ages from the house number and the product. This means that there must be at least two sets of three ages with sum to the same number "A" and multiply together to yield 72. The only number A which satisfies this condition is 14, and the two sets of three ages are 3, 3, 8 and 2, 6, 6. The bartender's last statement allows the mathematician to determine which of these is the correct set, based upon the existence of a "youngest child." --Mark

It's foolish to "assume" the the mathematician knows where the bartender lives. (If he knew that it's likely he'd already know that he had daughters and their ages) The Puzzle should mention that the bartender gives the mathematician his address, but that even with this information the mathematician can't figure it out. So the puzzle doesn't have to include the fact that the house number is 14, but it DOES need to include that the house number is known by the mathematician. Something like this should never just be left to assumption, especially since the puzzle involves two people who are apparently not very familiar with each other. --Kyle

I definitely agree with Kyle here. The missing statement that the mathemetician somehow knew the address of the bartender is the only thing that kept me from getting the answer. If it were worded "Then I should tell you that the sum of their ages is equal to the street number of this bar," then the mathemetician could step outside and observe the street number. This would allow an elegant way for the mathematician to learn the sum of the ages without the puzzle solver knowing. --Greg

I agree with Kyle & Greg. If there's one more person, I think he/she should delete these 3 comments and change it. --Michael

Actually I originally meant it the way Greg stated it, but somehow I made the assumption that the family lives in the house of the bar, which is not very likely if you think about it. I’ve changed the puzzle to the sentence Greg suggested. If someone feels like cleaning up this discussion section, he/she can delete these comments, as the problem should be solved now. --OP

Having solved this, I can't help but feel a little bit short-changed, because the final insight which allows the mathematician in the story to solve the problem (i.e. the existence of a 'youngest' daughter) is the same one that we use ourselves. This means that the final sentence "Now the mathematician knows their ages" is redundant, when it could potentially be used for an extra twist: if there had been more than one sum that had multiple solutions, but only one of those sums led to a unique solution on hearing that there is a youngest daughter, then the fact that the mathematician was able to solve it becomes critical information for us. So, here's a meta-puzzle for you (which I haven't solved): is there a way of re-posing the puzzle with a different product and/or number of daughters so that it satisfies this petty unreasonable whim of mine? 87.112.93.193 03:05, 16 August 2009 (UTC)

• How about this? The product of the three daughters' ages is 360. Then (assuming that my 3:30am pencil-and-paper calculations are correct) there are five pairs with equal sums: 36/5/2 and 30/12/1 (sum of 43), 20/6/3 and 15/12/2 (29), 15/6/4 and 12/10/3 (25), 12/6/5 and 10/9/4 (23), and 10/6/6 and 9/8/5 (22). The mathematician knows that the sum is in fact 22, so he deduces from the youngest daughter comment that the daughters are 9, 8, and 5 years old rather than 10, 6, and 6. None of the other pairs feature twin daughters, so this should be the unique solution. Ravi12346 08:43, 29 August 2009 (UTC)

[edit] The father

Assuming the typical human gestation period of nine months, and assuming that a fertilized embryo counts as a child (debatable), and assuming that age can be considered a negative quantity (debatable), and assuming that a genetic link is enough to establish "fatherhood," the father is standing naked in the restroom, wondering if he should tell the girl that his condom broke. --Mark

Since the daughter will be 5 years, 3 months in six years, the mother is just now starting her second trimester and is 20 years, 3 months old. So no, she was legal and (arguably, I suppose) not a "girl". And I think the problem should be rephrased to "In six years, A mother's age exactly five times the age of her child and she will be 21 years older than her child. Where is the father?" That phrasing will avoid the current problem where the daughter's age seems to be defined as negative, which isn't exactly an ordinary definition.

I don't understand the "Where is the father?" question, though. What is the implication here? 76.190.157.141 05:56, 14 March 2009 (UTC)

Either "having sex with the mother" because the child's age is -3/4 years (nine months), or "in prison" because the child's age is constant --J0eCool

Yeah, I somehow added wrong. That's the correct solution. 76.190.157.141 20:08, 14 March 2009 (UTC)

This puzzle is dumb.

I thought this was a fun detour from what you initially expect when you first read the question, regardless of some of the debatable discrepancies. --Greg

Just thought I'd point out that the question is flawed in that the fact that the daughter is being conceived does not imply any particular, nontrivial location for the father. --Ryan

Another problem: the 9 months is counted from when Mom had her last period, not from date of conception. Further, there is significant variation around the expected birth date: some kids come months early. I was 4 weeks late myself. => Dad could be anywhere. I would also quibble that if you're going to pretend we know the exact day from the answer, we ought to be informed that Mom is 21.00 years older. Boo. --DW

Gestation time is 40 weeks not nine months, so the father is at the pub, blissfully unaware that he knocked some chick up last week. Also, someone needs to look up what father means. --SirEel

Most recent information about County historical map missouri stone topographical and Paulding county here http://county.goodnano-av.com/

[edit] Two Dice

The answer is 1/11. The question can be formulated equivalently as follows: Two six-sided die are rolled. Given that at least one of them turns out to be six, what is the probability that both turn out to be sixes? There are exactly 11 equiprobable cases (rolls) that yield at least one six: (1,6),(2,6),(3,6),(4,6),(5,6) (6,1),(6,2),(6,3),(6,4),(6,5) (6,6) One of these yields two sixes. --Tennenrishin 15:33, 3 March 2009 (UTC)

P(A|B) = P(A&B)/P(B) = (1/36)/(11/36) = 1/11

This problem is not tricky in terms of the math but the wording appears to be intentionally misleading. I'm not sure that's fair. A better wording would be "I roll one dice and it is a 6, if I roll a second dice what is the probability that they are both six?" This isn't a hard puzzle but more of a math story problem. I could imagine someone reading this and thinking it was assumed that the first dice was a six and therefore did not need to be incorperated into the probability assessment. 02:04, 11 March 2009 (UTC)

I am not a grammar nazi, but please, the singular is "die" and the plural, "dice."

Actually, no. That would be an even worse wording. With your wording, the probability would actually be 1/6. The reason it is not 1/6 in the original wording is because EITHER of the dice can be a 6. If I roll one dice and it's already a 6, the second one has a 1/6 chance. (I'm tired of arguing so if you don't believe me run a simulation).

This is a slight variation of the Two Beagles problem. I suggest deleting it. -- DanielLC

[edit] A Single Toss

I made this one up myself - hope you like it. Let me know if you need any clarification. Harfatum 22:28, 4 March 2009 (UTC) (Luke is the first one to get the first part, nice job)

I made a few technical clarifications, and added the discrete question. You can solve the continuous question without integrals if you view it as a limit of discrete questions and use summation identities. Harfatum 19:33, 17 March 2009 (UTC)

It sounds like you are stating it is possible to transform an integral into the limit of a Riemann sum, which is hardly surprising. I still think something needs to be added stating some method of determining it's edge. I mean, is the edge normally distributed? I maintain that without further qualifications, I would not play for any amount of money because I would assume that with such a bent up coin the man is probably intentionally trying to rip me off. 76.190.157.141 19:39, 18 March 2009 (UTC)

What I am getting at is that if you write down the discrete probabilities, then you can get a rational polynomial function of n for the expected value (for discrete p-values in 0/n, 1/n ... n/n), which you can eyeball and say goes to 2/3 when n is large. The edge? What exactly do you mean? I changed this guy from shady to confused, to emphasize that we have no idea if he's trying to rip us off. I could reframe the problem if it's causing confusion. Harfatum 20:46, 18 March 2009 (UTC)

$0, of course. Call the likelihood of it landing on heads "1/N". Just because it landed on heads for me doesn't mean it didn't land on tails for the N-1 other people he has propositioned so far. Therefore, since N can be arbitrarily large, any amount paid to this person can result in an arbitrarily large net deficit. Therefore, this game is not worth playing for any price, other than "free," unless a cap is set on "N." This is true for any set of witnessed flips, even if it lands heads-up 100 times in a row (although such may lead you to expect "N" to be rather small). --Mark

I'm going to say 2/3 of a dollar: Attempt to find the probability that in any given toss the coin will land heads. Given that we know that after one trial it did land heads, I think it's fair to bend things a bit and assume that we're going to get a linear distribution - that is, the chances of it being a fair coin are double the chances of it being only 25% weighted towards heads, and half the chances of it being fixed for heads. Because all probabilities have to sum to one, we get a continuous probability distribution (of probabilities) f(x)=2x for 0<x<1, and so the expected value for the probability of heads coming up will be the integral of xf(x)dx between these limits, which is 2/3. If you get paid 1$ for each success, and the probability of success is 2/3, then the expected payoff will be $2/3. --Luke

Eh, that's a decent way of looking at it, except that it seems reasonable to claim the man is intentionally trying to rip you off. It really is more likely the coin is fixed for tails than fair.

And Mark is right to some extent in that without knowing the distribution, we can't answer this. We also don't know, for example, if the coin has a memory, which would really complicate things. Since it's so bent, it might even bend more each flip, completely randomizing things! Obviously in the real world, it is best never to bet on such a coin, since anybody trying to get you to bet on it is way too shady to trust. 76.190.157.141 06:09, 14 March 2009 (UTC)

Outside of theory, just some food for thought: |You Can Load a Die, But You Can’t Bias a Coin. -- Andrew

I've worked this out myself before. There is a slight error in the problem. If you can assume nothing about the coin, you cannot ever get a probability. What I did was assume the probability of the coin landing on heads had a constant probability distribution. -- Daniel Carrier

I agree. The problem seems to be asking us to choose an uninformative prior probability, but there seems to be disagreement about how to choose such distributions. (wikipedia link) It isn't obvious to me that the uniform distribution is especially reasonable. --Allen 02:54, 8 May 2009 (UTC)

[edit] Bananas and a Hungry Camel

Just found this problem today. Think I've got a good answer but not too sure about the proof. I'm thinking about running a genetic algorithm on it tomorrow to see if the computer finds anything better. --Luke

I got a result of 533 bananas. I'm pretty sure this is optimal but have no formal proof. While there are more than 2 000 bananas, it takes 5 trips to move all of them: move a full load, go back, move another full load, go back, move the rest. That's 5 bananas per mile, therefore 200 miles consume the first thousand bananas. It doesn't matter if this is done in steps of one mile, one banana (1/5 mi), or all 200 miles at once. From here on, only 3 trips are needed, therefore the farmer gets 333 miles (and one third) with the next thousand bananas and is at 533 miles with 1 000 bananas left. The rest goes with one trip which uses up 467 bananas, leaving 533 bananas to sell (534 if we count the fractional mile and the camel only needs to eat after moving).

The farmer is also left with one hungry camel with no food for the trip back home. If he would also like to get the camel back home, I think he'd need about 3 667 bananas to start with (leaving nothing to sell) or more. This is with leaving bananas along the way for the return trip, and is obviously cheaper than going 2 000 miles straight (which would take 7 673 bananas). --Nix

What are you all talking about? The puzzle says that the market is 1000 miles away. The camel can carry 1000 bananas at once and it eats one banana for each mile it walks. So at the end of the 1000 miles, there wouldn't be a single banana left, because the camel would have eaten them all. Therefore the answer is 0. --Brusko

You're depositing bananas out in the desert, Brusko. Via Nix's solution, which I agree is best, you take 1000 bananas out 200 miles, drop off 600 of them, head back 200 miles, reload, take 1000 bananas out 200 miles, drop off 600 of them, head back 200 miles, reload, take 1000 bananas out 200 miles, load 200 of the 1200 you've dropped there, etc., etc. --Mark

The problem as it is currently written doesn't say when the camel has to eat the bananas, only that it has to eat 1 per mile it goes. That means that I could get 1000 bananas to the market, return, and then feed the camel 2000 bananas when we get home. I assume that the question is mis-worded though, and that is should be fixed to read "but needs to eat a banana to refuel immediately after every mile he walks" or some such. --Stephen

[edit] Birthdays

This problem seems to be a special case of a related problem above.... "Probability, and a barrel of balls". A general solution, although unverified, has been offered.

The answer is 23. If you want to work it out the easiest way is to answer the reverse problem, ie what is the probability that out of a group of n people what is the probability that 2 people do not share the same birthday.

The calculation is (ignoring leap years) 1 * (364/365) * (363/365) * ... * (365-n/365). When n = 23 this number is less than 0.5, so there is less than 1/2 chance of 2 people NOT having the same birthday, or conversely there is a greater than 50% chance that 2 people WILL share the same birthday.

"How many people do we need to have a probability of 1/2 that each day of the year is a birthday ?" Can be solved using standart counting methods of combinatorics. We are distributing indistinguishable balls (people) among distinguishable urns (days), to get all the possibilities distributing people among the days in complete randomness. If we are dividing the number of possibilities doing this in a surjective (each day is hit AT LEAST once) way by the first number we get the probability (assuming humans are born equally often on all days of the year; also neglecting leap years). Let n be the number of people, then the whole equation will be Obviously there are no solutions if there are less then 365 people (which shouldn't surprise us, as you can't get 365 birthdays in the year with only 364 people).

((n-1) chose (365-1)) / ((365 + n - 1) chose n) >= 0.5

If you care, solve for n. If you could prove nominator growing slower than denominator for all n > 365, there were no solution. Else somebody could go ahead and write a program solving that thing ;)

update: after some fiddling with java I got a result that with 191677 people, we have a probability of over 50% that each day in the year is a birthday, which I find quite amusing.^^ -- Mel

Something is wrong with your formula. Using simple simulations of 1000 random trials each, I got the results that with 2500 people it's already 66%, with 3000 90% and with 2000 only 20%. Also, shouldn't the case of n=365 yield 365!/365³⁶⁵, which it doesn't?

To get an exact number I used my formula from "Probability, and a barrel of balls". Barring any problems from floating point arithmetic (I know, could be avoided), the exact point of 50% is between 2286 (49.941%) and 2287 (50.037%) people. I'm still interested to see that simpler formula for this. --Nix

yeah, I was wrong. I was assuming that putting all birthdays on one day has the same probability as for example putting half of them on day#1, and half of them on day#2, which is of course incorrect. After treating all the people as individuals I got the same number as you did, via using (365! * S_n,365)/365ⁿ, where S_n,k is the Stirling numbers of 2nd kind. --Mel

I think the problem can be more easily viewed as, 'what is the average number of times you must roll a 365 sided dice before you see all 365 numbers come up'. which is [sum from (i=0 to 364) of 365/(365-i))]= 2364.64 -Peter

Is this a leap-year? If so it would make the number of times significantly higher. -Ian

[edit] The Bee Problem

Easiest way to solve this is to recognize that the biker travels 2 m/s, for 20 m. Therefore, the cyclist arrives in 10 s. If the speed of the bee is 5 m/s, and it also travels for 10 s, then the bee travels 50 m, even though its total displacement remains 20 m. --Mark

Bee travels 2.5 times as fast as the bike, so for the bike to go 20m the bee goes 50. --Luke

I hope the person on the bike was wearing a helmet.

[edit] Math Puzzles

Would it be appropriate to create a new page or a new section of this page devoted to math puzzles, problems, and proofs, rather than logical ones? I think these don't really belong mixed in with the logic puzzles, but there are plenty of good ones, several of which I can think of off hand that are difficult at many levels of math. For example, can you find an exact value (in terms only of natural numbers, +, -, *, /, and ^) of the sine of one degree? What is this value? Can you prove it? 76.190.157.141 06:19, 14 March 2009 (UTC)

[edit] Cereal Box Game

Every time I see this game on the box I try to determine the probability of winning, and I just don't know how to approach it. Combinations and permutations are pretty easy, but the twist to this puzzle is that you may pick out a color more than once.

For example, on row 3, you need green, blue, and yellow to advance. You may pick a green, a blue, another green, another blue, yet another blue, and so on. You continue until you have at least one of each color shown, or you pick one of any color not shown. You could pick a hundred greens and blues, but a single red, orange, or purple ends the game.

I hope this is a worthy puzzle for the page. -Taren

I think the probability is 1/6 * 1/15 * 1/20 * 1/15 * 1/6 = 1/162000 , where each of the probabilities are the chance of winning each level. The probability of winning each level is equal to the probability that the allowed colors are the colors to appear first. These probabilities are of course the same for all combinations of colors and therefore the probability is 1 divided by the number of ways to select this many colors out of 6 possible colors. For example, for level 4 this would be the number of ways to select 2 out of 6 colors, which is equal to 15. This way you can safely ignore the twist of picking out the same color more than once. - K

Reverse the problem. For each stage, what is the chance of losing? You can guarantee that you have a 1/6 chance of picking any color at any time, so you don't have to keep track - therefore the probability of losing the first round is 1/6. Second round: 2/6. Winning the game = 1-(1/6 * 2/6 * 3/6 * 4/6 * 5/6)

I got 1/162000 as well. A simple mathematical explanation:

To pull the first color of the first row, you have a 5/6 chance to get it, and a 1/6 chance to lose. The next color has a 4/6 chance to get it, a 1/6 chance to ignore the draw (drawing the previous color), and a 1/6 chance to lose.. This can be simplified to a 4/5 chance. The next cerial is done the same way, but with a 2/6 chance to ignore the draw, and is simplified to 3/4. The pattern continues. The odds for the first row: 5/6 * 4/5 * 3/4 * 2/3 * 1/2 = 1/6.

The second row has a 4/6 chance to get the first cerial. 3/6 chance to get the second cerial, 1/6 chance to ignore the draw, and a 2/6 chance to lose. A similar pattern: 4/6 * 3/5 * 2/4 * 1/3 = 1/15

third row: 3/6 * 2/5 * 1/4 = 1/20

fourth: 2/6 * 1/5 = 1/15

fifth: 1/6

multiplied together = 1/162000

[edit] 0=6

(all trigonometric calculations are in radians)
0 = 0
cos(0) = 1
tan(cos(0)) ~= 1.5574....
sqrt(tan(cos(0))) ~= 1.2480...
tan(sqrt(tan(cos(0)))) ~= 2.9892...
sqrt(tan(sqrt(tan(cos(0))))) ~= 1.7290...
tan(sqrt(tan(sqrt(tan(cos(0)))))) ~= -6.2710...
abs(tan(sqrt(tan(sqrt(tan(cos(0))))))) ~= 6.2710...
floor(abs(tan(sqrt(tan(sqrt(tan(cos(0)))))))) = 6
--Nolan

Square roots sound like cheating to me, since you aren't allowed to use any twos. I guess I would feel a bit more comfortable with ln, though, since that can be defined by an integral rather than just meaning log_e. Regardless, I feel fairly certain the easiest way to solve this is indeed to start with cos 0 and work from there. 76.190.157.141 18:44, 17 March 2009 (UTC)

Another option is exp(cos(0))=2.7... , ceil(exp(cos(0)))=3 , ceil(exp(cos(0)))!=6. This avoids the square root, but uses the exponential function. I wonder whether there is a solution without resorting to the ceil() or floor() functions. - K

You can get any number of the form sqrt(p/q) just using, for example, sec, arccos, and arctan: let F(x) = sec(atan(x)), G(x) = sec(acos(x)). Then F(sqrt(x)) = sqrt(x+1), G(sqrt(x)) = sqrt(1/x). So if p/q has the continued fraction expansion [a_0; a_1, a_2, .., a_n], then sqrt(p/q) = F^(a_0) G F^(a_1) G ... G F^(a_n) (0). --Eigenray

I just realized that arcsin doesn't need to be restricted to its principle branch. One of the values of arcsin 0 is 2pi, so floor(arcsin 0) is a solution, kind of. I would also like to add that the problem needs more constraints on which functions are allowed. Obviously the easiest way to solve this as stated is simply to use the successor function six times. 76.190.157.141 19:51, 18 March 2009 (UTC)

If square roots are off the board, than the successor function is definitely off the board. Agreed that the set of available functions should be more clearly declared. I propose the set that cannot be trivially defined using the aforementioned forbidden numbers, such as sqrt(x) = x^(1/2), and S(x) = x + 1. On the other hand, someone here can probably drum up an infinite sum or integral definition of just about every function available that we normally don't think of as straight arithmetic.

Well, "the square root of x" is simply a notational alternative to "the second root of x," whereas "the successor of x" is completely different from "x + 1." Besides, you have it backwards; addition is defined recursively by the successor function, not the other way around. The successor function is far more fundamental. This is obvious when defining "one." One is typically defined as the successor of zero, not zero plus one, which would be totally circular. 76.190.157.141 03:36, 26 March 2009 (UTC)

Here's a roundabout solution involving only ceiling, trig, and ln: ceiling(ln(tan(tan(tan(tan(tan(tan(tan(tan(ln(arcsin(cos 0))))))))))))! That is, the factorial of the ceiling of the natural logarithm of the eight tangent (the tangent iterated eight times) of the natural logarithm of the arcsine of the cosine of zero equals six. I'm pretty sure there is a brief solution using a sum or integral from n=0 to infinity, but I haven't found a good function to use for that yet. 76.190.157.141 20:10, 18 March 2009 (UTC)

The Peano axiom successor function S

0=0
S(0)=1
S(S(0))=2
S(S(S(0)))=3
S(S(S(S(0))))=4
S(S(S(S(S(0)))))=5
S(S(S(S(S(S(0))))))=6

Nerd65536 02:03, 19 March 2009 (UTC)

Nerd, I already pointed that out. Clearly the implication is that the successor function is not allowed, although this isn't stated in the problem.

And by the way, that is actually the definition of six, interestingly enough. 6 := S(5), 5 := S(4), 4 := S(3), 3 := S(2), 2 := S(1), 1 := S(0). 76.190.157.141 19:38, 21 March 2009 (UTC)

---

(ceil(tan(tan(tan(cos(atan(cos(0))))))))!
without using anything that could be written in a form which would include numbers. I highly doubt that you can reach exactly 6 without using succ(x) or ceil(x) --Mel

Yeah, that's much nicer than the trig one I found: floor(tan(tan(arcsin(tan(sin(arctan(sin(arctan(ceiling(tan(cos0))))))))))))! = 6. Still, I'm not entirely satisfied using the ceiling function. While it can be defined as the least integer greater than the argument, I generally see it defined as the least integer (aka floor) function plus one. Either way, I still feel the ideal solution would be a sum from zero to infinity. 76.190.157.141 19:38, 21 March 2009 (UTC)

---

log*(x) indicates the iterated logarithm. log*(arccos(0)) does it nicely, as arccos(0) is a multi-valued function which evaluates to 2(pi)n + (pi)/2. For a large enough n (which my calculator can't calculate), log*(arccos(0)) = 6. --Mark

You're all trying way too hard on this one. You can solve it with pre-algebra. 0^0=1, right? So 0^0+0^0+0^0+0^0+0^0+0^0=6 --Greg

Greg, 0⁰ is generally undefined, not equal to one. But more importantly, you can only use a single zero, whereas you used six. Otherwise cos(0) + cos(0) + cos(0) + cos(0) + cos(0) + cos(0) = 6. 76.190.157.141 19:38, 21 March 2009 (UTC)

--- I think this is the shortest solution so far:

(floor(arccos(-cos(0))))!

using the main branch of the arccos [0,pi].

  - Yakov, Rehovot.

I disagree with the above solution since it uses an implied -1 multiplied to the cos(0). Here's a short one using just trig functions and a floor.

floor(sec(sec(arctan(cos(0))))).
--Kabo

I think this is the longest solution so far: sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan sec arctan (0). But at least it is exact :) --Eigenray

Eigenray, that is a peculiar result, but definitely my favorite so far. It seems that by iterating sec(artan(x)) you can obtain any integer. If we let f(x) = sec(arctan(x)), and let fⁿ(x) be a functional power (simply the function iterated n times), then f^n²(0) = n. I will try to keep this in mind.

Noting this, I propose we change the puzzle to "Using only trigonometric functions and a single instance of the number zero, derive a forumula to calculate any number n as a function of n. For added challenge, prove this by induction. 76.190.157.141 01:20, 23 March 2009 (UTC)

I really like the above solution because of the way it works:

sec arctan(0) = sqrt(1)

sec arctan sec arctan(0) = sqrt(2)

sec arctan sec arctan sec arctan(0) = sqrt(3)

Repeat this pattern to the 36th level and you get sqrt(36) or 6.

This can be defined simpler as a sequence:

a(0) = 0

a(N+1) = sec(arctan(a(N)))

Thus a(36) = 6.

This also implies you can get any positive integer from 0 using this sequence. Cool, huh?
--Kabo

19-NOV-2009

Kabo is back with your induction proof!

Given: a(0) = 0. a(n+1) = sec arctan(a(n)).

Prove: a(n) = sqrt(n).

Proof:

Case n = 0 :

a(1) = sec arctan(a(0)).

a(1) = sec arctan(0).

a(1) = sec arccos(1). *

a(1) = sec arcsec(1).

a(1) = 1

a(1) = sqrt(1).

Case n = x :

a(x) = sec arctan(a(x - 1)).

a(x) = sec arctan(sqrt(x - 1)) by induction.

a(x) = sec arccos(1/sqrt(x)). *

a(x) = sec arcsec(sqrt(x)).

a(x) = sqrt(x).

Thus a(n) = sqrt(n); QED.

* The jump from arctan to arccos (and arcsec) requires knowledge of their relationship to each other (rather than pressing that silly key on your calculator =P). If we have a right triangle ABC with sides (opposite angles) a, b, and c, the hypotenuse being c and the angle we care about is A. arctan will deal with the ratio a/b. If we let a = sqrt(x - 1), then b must be 1. Because a^2 + b^2 = c^2, it follows that c = sqrt(n). arccos deals with the ratio a/c (1/sqrt(x)); thus by definition arcsec deals with c/a (sqrt(x)/1).

Another way to think about it is to start with a right triangle with sides a, b, and c. a = 1, b = 1, c = sqrt(2). Then as the sequence progresses, c becomes the new a, b remains 1, c is sqrt(a^2 + b^2) over and over again. (You could start with a = 0, b = 1, and c = 1, but where's the fun in having a triangle with 0 as a side?)

The only problem I - personally - have with using sec, is that sec(x) basically just means 1/cos(x) --Mel

But the puzzle explicitly states that trigonometric functions are allowed. Strictly speaking, even cosine is defined using an infinite sum that involves several integers. Hell, even addition, multiplication, and exponentiation for natural numbers (which definitions are necessary to define the operators for rationals, and thence for reals) are defined recursively using a zero, which would break the "one zero" rule. Obviously at some point we have to ignore the "definition" of a function and focus on the actual notation. "sec x" is not shorthand for "¹/_{cos x}", it is simply (usually) defined as such. Furthermore, it is often defined separately as a quotient of side lengths of a right triangle or an infinite series, not based on cosine. 76.190.157.141 03:30, 26 March 2009 (UTC)

---

Hello! Maybe I get this wrong, but for me the simplest solution, which should work everywhere, is that everything with 0 in the exponent is 1, even 0:

0^0 + 0^0 + 0^0 + 0^0 + 0^0 + 0^0 = 6

^ means "exponent", not an C operator ;-)

--Stsz 11:12, 2 April 2009 (UTC)

There are two reasons this solution is invalid. The first is that 0⁰ is not generally defined as 1, as I stated above, although this is sometimes the case. Most of the time, 0⁰ is an indeterminate form since convincing arguments could be made for it to equal any real number, much like ⁰/₀. The second reason is far more important: The question asked for how to get 6 with only a single zero and no other numbers. You, however, used 12 zeroes. Otherwise, cos 0 + cos 0 + cos 0 + cos 0 + cos 0 + cos 0 = 6. 76.190.157.141 04:36, 3 April 2009 (UTC)

---

I'm just trying to think outside of the box here. log(x*x*x*x*x*x) base x for all x such that x>cos(0) is 6. It's almost cheating because of the x*x*x*x*x*x for x^6, the set notation, and the use of variables, but the directions were nowhere near explicit. Also, dx*x*x*x*x*x / dx evaluated at x=cos(0) would give 6. Once more, the use of a variable is probably prohibited. -Luonnos

The first one seems a bit iffy, only because you define x using a zero, then repeat x six times. I could simply instead say 6 = x + x + x + x + x + x, where x = cos(0).

I like the second one, though, because here x isn't simply a substitute for a number, it's actually a variable in a function. You only need one number at which to evaluate your whole derivative, so it seems a bit more legitimate. I personally prefer (sec(arctan(sec(arctan(sec(arctan(sec(arctan(sec(arctan(sec(arctan(sec(arctan(sec(arctan(sec(0))))))))))))))))))!, though. 76.190.157.141 21:58, 7 May 2009 (UTC)

Oh, and for clarity, your notation should look more like ^d/_dx|_{x = cos 0}(x * x * x * x * x * x). Right now it looks like ^dx/_dx|_{x = cos 0}(x * x * x * x * x),which isn't even a derivative and is equal to x⁵. 76.190.157.141 05:02, 14 May 2009 (UTC)

Cant we just add 0! (factorial) 6 times?

• sigh* Again, the point of the puzzle is to obtain a result of six using ONLY A SINGLE ZERO, and no other digits. 0! + 0! + 0! + 0! + 0! + 0! = 6 requires six zeroes, not one. 76.190.157.141 04:56, 14 May 2009 (UTC)

Let S be the set of complex numbers whose norm is 0!, and let L be this set's projection onto the reals. Then 6 = n!, where n is the (sigma) sum of natural numbers up to the Lebesgue measure of L.

If the sigma sum is not allowed (I use it because it is regarded symbolically as not requiring the intervening numbers even though they are implicitly computed), then factorial should not be either (for the same reason). On second thought, factorial can be regarded as independent of the computation n!=n(n-1)... and instead as the order of the permutation group on n letters, which liberates it of dependence on all the smaller numbers. If there is an equivalent characterization for a cumulative sum, then the above solution should suffice. Gosualite 17:17, 31 July 2009 (UTC)

Here's a solution without using a zero: Let A be the class of finite nonabelian groups, and let N be the set of all orders of elements (nonabelian groups) in A. Then 6 = inf N. Gosualite 06:01, 1 August 2009 (UTC)

If arbitrary undefined variables were allowed, a solution would be

   cos(0)/(n/(n+n+n+n+n+n))

Of course I'm guessing this is not the case.

212.242.194.69 22:30, 15 October 2009 (UTC)

I found this one which is as short as I think is possible without negatives and only trig+ln: ceil(cosh(sinh(acos(0))) Of course, depending on what you want to allow you can also get ceil(sinh(acos(0)))! I found the above with python+mpmath, using the following functions: sin, cos, tan, csc, sec, cot, asin, acos, atan, acsc, asec, acot sinh,cosh,tanh,csch,sech,coth,asinh,acosh,atanh,acsch,asech,acoth ln,floor,ceiling A couple others: 0 : 0
1 : cos(0)
2 : ceil(acos(0))
3 : ceil(sinh(acos(0)))
4 : ceil(sinh(sec(cos(0))))
5 : ceil(sinh(sinh(acos(0))))
6 : ceil(cosh(sinh(acos(0))))
7 : ceil(sinh(cosh(acos(0))))
8 : floor(tan(coth(sin(cos(0)))))
9 : ceil(tan(coth(sin(cos(0)))))
Given the operations above, these SHOULD be the most succinct possible, even including negating as a function.
~Geekthras

[edit] the hardest interview puzzle question ever

There is no actual problem statement. It just asks "What is the solution to this problem?" Without defining what is meant by "solution," there is no correct answer. 76.190.157.141 18:47, 17 March 2009 (UTC)

This seems to be a joke, so I'd recommend its deletion.

I don't this you should delete this puzzle. I think it's important for people to be able to identify that they don't actually have a problem that requires a solution. - Baz

Fair enough, but there are probably more clever examples than this one of questions with misleading preambles. This one recycles all the other problems on the page in such a way as to make it obvious it's not a 'real' problem. -P

Since the question is nonexistent, the answer defaults to 42. --80.202.41.223 18:17, 18 March 2009 (UTC)

Agreed, the answer is 42. --Greg

I suspect none of you know how to take a joke! I thought it was funny, and definitely worth keeping. And I'd have to agree - the solution has got to be 42. --T.

The answer is obviously 1 * Sh , where Sh is the Shimmler constant and equals the value one must multiply the found result with in order to have the correct result. Alternatively it can be the text string "This is the answer to that problem." -- Eroen

"What" is the solution. When the problem is read out loud, you can't tell if there's a question mark-so it's just a statement. --Satvik

How about this one: There are 99 prisoners in a prison, each wearing a red or white hat, and they can see all of the prisoner's hats except their own, and they each have 13 coins one of which is counterfeit and does not weigh the same. The duties of warden are shared between a chicken and fox who cannot be left alone with each other or the chicken will eat the fox, and a woman who does not know the color of her own eyes. One of them lies, one always tells the truth, and one alternates true and fox statements. If any prisoner knows the color of their own hat and which coin is counterfeit and if it is too heavy or too light they will be set free. The woman says the guard who alternates true and false statements is in charge of the prisoners with red hats, the fox tells the prisoners with white hats that he will allow them to use a balance scale on the coins three times each, but if they use it more times they will be put to death, then says that the woman will put to death any red hatted prisoner who uses it. The chicken says that every third time a prisoner uses the scale a new prisoner will be admitted and if the population reaches 200 they will all be put to death, then says that any prisoner who uses the scale without the permission of 40% of the other prisoners will be put to death. The woman then addresses one specific prisoner and says to him, in the hearing of the other prisoners "there are exactly 49 other prisoners wearing the same color hat as you." What is the solution to this puzzle?

Assuming that the pirates are at sea, the most prevalent solution in the problem is salt water. -- Alex

[edit] The Spinning Log

This answer is a bit lengthy, likely longer than necessary, but hopefully it's thorough enough and clear enough to understand. Here it goes, brace yourself.

Let us assume that the log is treated with some sort of perfectly effective water sealant, so it absorbs no water, and let us assume that there is no friction of any kind in this system. That means no friction between the the log and pins, pins and walls, log an seals, log and water, or log and air. This presents, as far as I can tell, an optimal version of this scenario.

For the sake of argument we'll forget that we already know perpetual motion machines are impossible because of the law of conservation of energy. We'll suspend our disbelief.

For this answer let us assume we are looking at the end of the log and that the from our position of observation, the right side is the side with the water, and the left side is the side without water.

The idea behind this perpetual motion machine is that the water will continuously push up on the right side of the log since it's lighter than the water and is trying to float thus causing the log to spin counterclockwise.

To understand why this would not work, we need to look at how buoyancy itself works. When a lighter than water object (lets say a hollow ball) is submerged it is pushed up by the water apparently in spite of gravity. In fact the opposite is true. It is gravity pulling down on the water that pushes the ball up. The kinetic energy to lift the ball comes from an equal volume of water falling to occupy the space where the ball just was. As the ball moves up, the evacuated area is filled with water from above it; therefore, this water is falling. When the water was above the ball it had potential energy that is exchanged for kinetic as it falls to fill the void left by the ball thus providing energy to lift the ball. The opposite is true for a heavier than water object (lets say a brick), but it's still the same principle. As the brick falls through the water, it is filling space that was once filled by water. As the brick falls, it is providing energy to lift the water to fill the space it just evacuated.

Now back to our spinning log example. If the log were to spin, it would not be evacuating any space for the water to fill. Even though a different part of the log would be filling that space, it would still be the same space it was filling before. There would be not downward movement (falling) of water to convert potential energy into kinetic, so there is no energy to cause the log to spin.

Unrelated Gee-Wiz Info: The water will be imparting a constant force to the log, but it will be pushing on the entire "wet" surface with equal force (a property of fluids), so the net force will be directly left, straight toward and through the pivot axis. It's not really relevant to this problem, but it might be interesting to note. --Greg (Written 2300 Tokyo Standard Time, 21MAR2009)

I may be wrong since I haven't done any serious physics in a while, but the water doesn't push the entire wet surface with equal force like you said. If it did, consider if the log was free in the water, what would push it up if not the water pressure? I'll avoid using conservation of energy at all and just look at the forces. The force from water pressure at each surface point points directly against the surface. For a cylinder, that is always towards the axis. That can't cause rotation, even if the magnitude of the force varies. The net force also has an upwards component, but the force is still through the axis. If the object wasn't a cylinder, the forces could actually spin it a little until it found a balanced position in which the net force is through the axis. Without friction or other extraction of energy it would still continue moving, but that's beside the point. Proving that energy couldn't be extracted from such a system continuously might be difficult using just the forces, but the case of the log is easy. --Nix

You're right about the difference of forces across the surface of the log. They all go through the axis, though, like you stated. That's what I meant to say, but it was late. Thanks for the correction. --Greg

[edit] Coaster Game

I suppose I could just place a coaster one coaster in the center of the table. Whereever you put a coaster, i have one answer spot, which lies directly opposite of the one you just placed. More work needs to be put in the question what is necessary for the table so that this solution works. (One or more symetry axxis? Square? Rectangle? What about a isosceles triangle?

I think that for this solution the table needs to have a point-symmetric shape. If you want to use a symmetry axis, you can’t cover it all with your first coaster, so your opponent has the possibility of placing a coaster on the axis, for which you have no answer spot. So I think square and rectangle would work, even an ellipsis should work, but the isosceles triangle probably wouldn’t work with this method.

[edit] Truth, lies and switching

The easiest solution i could find goes as following: I call the three men #1, #2 and #3. First I ask #1, what #2 would answer, if I asked him for the direction that #3 would give me, if I asked him for the way to my destination. (After sitting down at a table and scribbling on a piece of paper,) #1 will point in one direction, which is not depending on whom I asked (whomever I would ask I would always get that direction). The only thing it depends on is, whether the switcher starts with lying or telling the truth. (If he starts with lying the direction they gave me IS the path I want to chose, if he starts with telling the truth I should take the other route, if I plan on continuing my existance). To find that one out, I will now ask #2, what #3 would answer if I asked him, whether #1 was lying. If that answer is yes, I need to take the other path, if it is no, I am taking the path #1 told me to take.

Maybe question 2's wording isn't the best as English isn't my native tongue, but I think it's understandable? --Mel

I personally think it is somewhat easier if the questions are reversed:

1. Ask number one: "What would number two answer if I asked him whether number three were lying?"

2. Ask number three: "What would number one answer if I asked him what number two would answer if I asked him which path led to my destination?"

If the answer to the first question is "no," I should take the path indicated in the answer to the second question. Otherwise, I should take the other path. 76.190.157.141 04:23, 26 March 2009 (UTC)

I believe this can be done in only 1 question. As pointed out above, if you were to ask "Would you answer yes if asked 'is path A is my destination?'", truth and lies would both answer the same, revealing the destination: yes if path A is the destination, no if it is not. Switcher, would, of course be useless. So you add a conditional to the question "...answering with the same personality you are now". Since switcher assumes the personality of either truth or lies, if he were forced to act as if he always answered that way, he will either answer EXACTLY like truth or EXACTLY like lies. Hence, the question:

"Would you answer yes if asked, answering with the same personality you are now, 'is path A is my destination?'"

• It seems i was confused by how the switcher works, although it doesn't effect my answer. If he were to answer truthfully the first round, does that guarantee he answers false the second round? And do truth and lies know how he would answer on any given round?

• If the switcher answers randomly then you need two questions; if the switcher behaves randomly (as in the question) then yes, you only need one - either wrap the question with a future tense question as you've done, or go for "Is it the case that (this path is my destination) xor (you are lying)?".

If the switcher were to answer randomly regardless of question, you'd need an initial question to weed the switcher out before using the question above. Approach the first man, point to the second man, and ask "Is it the case that (he is the switcher) xor (you are the liar)?". If the answer is yes, the switcher must be either man 1 or man 2. If no, the switcher is either man 1 or man 3. Either way you identify someone who isn't the switcher. -- TLH

--- The simplest method I find is to ask one of the three "which path would at least one of the others suggest to you to take?", both the truth teller and liar would indicate the dangerous path, and the switcher would have to suggest either or neither I would think, as indicating one would be a part truth, so two questions, directed at to people should suffice, one if you're lucky. is this correct? cjm

[edit] More prisoners

My solution, as a series of steps:

1) Prisoner #1 opens boxes #2-#50, removes all of the scraps of paper, deposits them in the first box. 50% chance of living.

2) Prisoner #2 opens boxes #51-#99, removes all of the scraps of paper, deposits them in the first box. 99% chance of living.

3) Prisoner #3 opens box #100, removes the scrap of paper, deposits it in the first box. 100% chance of living.

4) Every successive prisoner opens box #1 with 100% chance of living.

Total survival likelihood: 49.5%, much greater than .5^100. --Mark

Oops, I wasn't clear enough: they aren't allowed to move the numbers around. I'll fix that. --eruonna

Well, it can increase easily to .5^50.

Prisoners #1-#50 open boxes #1-#50. Chance of surviving: .5^50.

Prisoners #51-#100 open boxes #51-#100. Because they know (because they survived) that Numbers #1-#50 are in boxes #1-#50, prisoners #51-#100 will find their numbers every time they try.

The survival likelihood can increase even further, I believe. --Mark

No, it's not as good as .5^50. Prisoner 1 has a 50% chance by opening 1-50. Given that they survive, prisoner 2 opening 1-50 has only a 49/99 chance because one of the boxes they're opening is definitely wrong. Prisoner 50 only has a 1/51 chance. The actual probability is (50!*50!)/100!

Odd prisoners select 1-50, even prisoners select 51-100 gives the same chance by a different route. I can't see a way to improve on (N!N!/2N!) for picking N of 2N boxes. -- cim

You can get a probability of at least 1 - log(2) == 31.6%. Each prisonner opens their own number, then the number they drew from that box, then the number they drew from that box and so on... Obviously if they reach an open box they have already drawn their own number. The probability of everyone surviving is exactly the probability that there is no cycle of length at least N+1 in the permutation of the 2N boxes. The number of of K cycles (K > N) is P(2N, K)/K, the total number of permutations with a K cycle is therefore P(2N, K) * (2N - K)!/K = (2N)!/K, the total number of permutations with a cycle of length at least N+1 is (2N)! * (1/(N+1) + 1/(N+2) + ... + 1/(2N)) = (2N)! * (H_(2N) - H_N). H_k are the harmonic numbers. The probability of success is therefore 1 - (H_(2N) - H_N). The limit of H_(2N) - H_N is quite easy to determine. Rewrite as sum{K=1...N, 1/(2K) + 1/(2K-1) - 1/K} = sum{K=1...N, 1/(2K-1) - 1/(2K)} = 1/1 - 1/2 + 1/3 - 1/4 + ... . Integrate 1/(1 - x) = 1 + x + x^2 + ... and substitute in -1 to get H_(2N) - H(N) --> log(2). Therefore the probability of everyone surviving tends (decreasingly) to 1 - log(2). -- Chard

--

If the prisoners know the order in which they will enter, then a very effective strategy would be to time the exit to match up with the location of the next prisoner's box, if discovered. For example, prisoner 1 goes in knowing he will search all the odd boxes, but rather than exiting upon finding paper 1 (if he doesn't nothing matters beyond this point anyway) he searches for paper 2. If he finds it, he times his exit to be on an odd numbered minute (if time pieces are unavailable, they can keep track of time and simultaneously remain synchronized by going through a song in their head, exiting at specific verses depending on the results of the search) and as such the following prisoner will know whether to search all the evens or all the odds, depending on whether the timing of the first prisoner's exit indicates success or failure. So long as the first prisoner finds his paper (a 50/50 chance) the rest are guaranteed to pass the test, and they all go free. of course, while this doesn't directly violate the no communication rule, as the next prisoner is simply observing the entrance and exit of the previous prisoner, as would happen anyway and would give at least some small amount of information with or without a planned system, it is certainly pushing it. And it is dependent on the prisoners being able to observe each other entering and exiting, as well as being given allowed at least some small amount of control over the time they have, and knowing the order in which they will be going

[edit] In three ways

[edit] Original rules

• Change "i--" to "n--" --Afarnen 18:00, 29 March 2009 (UTC)
• Change "i < n" to "-i < n" -- Chard (or "i < -n" -Personman)
• Change "i < n" to "i + n" -- Chard
• Change "20" to "-20" -- Personman

0 is > -20, it would never run. Same goes for i < -n. -Orc

Sure, it's a cop-out, but have you noticed that the program will print 20 dashes as-is? (It won't print exactly 20 dashes, but that wasn't specified. *g*)

I fixed this, as thinking of this almost caused me to check the answers before I had thought of the actual third solution. Personman 01:54, 13 July 2009 (UTC)

[edit] 21 Dashes

• Change "i < n" to "i & n" -- Chard

That doesn't work. 0 & 20 == 0 so it doesn't print anything. "~i < n" works on most platforms. --Nix

(Can you also change to "int i, n = -20;"?)

No; i has to be less than n for the loop to execute. Player 03 01:40, 8 April 2009 (UTC)

[edit] 1 Dash

To make a start, this could be done with 2 characters by changing 'for' to '//for'. This comments out the for loop and executes the bracketed code just once. Is there a 1-character way to skip this line? -- TLH

Here's a 1 character solution. Change the first line to "uint i, n = 20;" -Tom

Yes, if you define uint to mean unsigned int. Is there a compiler or standard header that does that automatically? The intended solution is probably putting a ; between the ) and {, although it's platform dependent as well. Even if int wraps from negative to positive like it does on common platforms, if int happens to be 64-bit it will take a long long (!) time to execute the loop. --Nix

[edit] Preceding code

These can be done by redefining operator--. Changing operator-- it to mimic operator++ will print 20 dashes, and changing operator-- to assign 20 will print one dash.

I believe one dash can be done rather easier by preceding the code with the single word unsigned; the i-- should then wrap i from 0 to 2^b-1 on a b-bit system. Since n=20 is possible, the system must have at least 6 bits (int is signed), so i should become at least 63 (when unsigned) and therefore break the loop after one execution.

-- TLH

printf("--------------------");exit(0); Personman 02:00, 13 July 2009 (UTC)

[edit] Pizza Paradox Puzzle

1/4, round isn't relevant. Where is the point of this riddle?

Assume all the coin tosses were done ahead of time - shouldn't matter right? Now choose the people corresponding to each round. More than half these people are in the final round. So if you are called there's more than 50% chance you're a winner. On the other hand let's say you find out what round you're in. Then the your odds of winning are (number in your round)/(expected number chosen). Since the expected number chosen is infinite, you have zero chance of winning.

I think:

1. "If you are selected but don’t win, you can’t be selected again"
2. "You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza?"

The games after this one don't matter, because if you won, you have your pizza and the game is over, if you didn't win, you can't be selected again. (#1)

The question doesn't ask for what the chance that you get a free pizza is without any assumption. The question asks, what the probability is that you win, given that you HAVE been told that you were chosen for THIS round. (#2)

--> chance is that THIS dice throw comes down as HH, not HT TH or TT, so chance is 1/4. (a little more elaborate than the first answer)

Okay if somebody calls me up, and I go to the mystery place of the game and watch two coins being tossed, the chance of winning is 1/4 irrespective of what has already happened, or what will happen in the future. The only reason the chance seems to be greater than 50% is because the game is designed to increase the number of people playing it after each round, whereas most probability problems generally have a defined number of players. It's a little bit like going to a casino and betting money in a 50/50 game of chance, then doubling your bet if you lose, and so on and so forth. Assuming an infinite amount of money, you will eventually win back the amount you first bet, but the chance of winning any particular round is still 50%.

I'm not clear on the rules here. If some but not all of the people in a round get two heads, do those people get pizzas even though the game goes on? Or does no one get a pizza until the final round, when everyone in the round gets pizza? 76.193.218.238 22:41, 19 April 2009 (UTC)

There is a single two-coin flip that decides for all people in a given round. Harfatum 09:22, 20 April 2009 (UTC)

As mentioned, the game is designed a lot like the Martingale betting system. It is guaranteed to produce more winners than losers (given an infinite population), which means that if you are called up after the game ends it would indeed be an over 50% chance that you are a winner. The chance of winnig a particular round is irrelevant. When called up mid-game it's all that matters. -- Fnursk

This is a MUCH more clever and difficult puzzle than it appears to be - it is similar to the coin toss problem. Imagine the question rephrased as follows: if you were to play one game in a random 'slot' in the game - what is the probability you win? Or, simpler, if there were an infinite number of games, what percentage of the players win? If you use an infinite series, you will get an answer of 66.6%.

How can this not be 25%? I can buy that 67% win and still say that you have a 25% probability of winning. You are faced with a single round in which there is a 25% probability of you getting pizza (along with everybody else in that round) and a 75% probability of losing and the round going to one with twice as many people.

That, on average, 2/3 of the people win is plausible, but that happens because in each successive round there are twice as many people, like doubling a bet. But also like doubling a bet, each individual bet is still the same probability as it always was. I am virtually certain 25% is the correct answer. 199.74.75.6 04:40, 26 April 2009 (UTC)

"You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza?"

Think about that question carefully.

I believe the answer is 25%, the same probability as a HH coin flip sequence. That's because the outcome of the game (i.e. which round will win) is unknown at the time you are selected, so the only relevant question is: "What is the chance of _MY_ round winning?" Even though you know that >50% of the entire pool of eventual players will get pizza, there's a 75% chance the winners will have played in subsequent (larger) rounds to your (known finite) round. On the other hand, if someone tells you: "The pizza game was played to its conclusion in a finite number of rounds; and you were somewhere on the list of players", then there is a >50% chance you were in the last round (because it was larger than all the others combined) and thus won a pizza. The confounding detail is that the expected number of participants in a single game is actually infinite.

This puzzle shares something in common with the Dirac Delta Function[4], in that one cannot simply "sweep under the rug" the scenario where the coins simply never come up heads-heads, because the unimaginably vast (infinite) number of players who are affected by that scenario. The product of the infinitesimal probability that the game never ends, with the infinite number of pizzaless players that will be affected by that case, actually yields the same percentage of players as all other cases combined. So if you have been notified only that you were part of the game, without the information that the game ended in a finite number of rounds, there's actually a 50/50 chance that you were part of the scenario that the free pizza was _never_ awarded. The other half the time, when the game ends in a finite number of rounds, your chances are 50%, which balances out to 25% overall, (not coincidentally) the same probability as flipping a fair coin heads-heads.

Not coincidentally is right... my method was a lot easier :P. I really like this explanation, although I disagree that it's all that much like the Dirac delta "function". While you don't actually need to consider the zero probability result which affects infinite people in your calculations, that such a result is possible is obviously important. People who think this system of choosing contestants improves an individual's probability of winning beyond 25% should by the same logic think a Martingale betting system improves your expected income in gambling.

As for the fraction of the people playing who won, I think the calculation is the weighted average of all possibilities, which is:

         1   n  3i       2i                      1    n    (3/4)i
 lim    --- sum --- * --------    =      lim  ------ sum  -------
n->inf  n+1 i=0 4i+1   2i+1 - 1         n->inf 4(n+1) i=0  2i+1 - 1

Which can't be right, because it seems to sum to 0. Well, I'll correct it later. Either way, the probability that YOU win is 25%, as stated. 76.190.157.141 04:08, 2 May 2009 (UTC) You should be multiplying outside of the sum by 1/4.Harfatum 07:00, 3 May 2009 (UTC)

I feel bad for all those people who don't get any pizza. 128.143.63.51 20:29, 10 July 2009 (UTC)

[edit] The Sam And Polly Problem

3 <= x <= y <= 97. Sam knows only x + y; Polly knows only x * y.

Sam (to Polly): "You can't know what x and y are."
Polly (to Sam): "That was true, but now I do."
Sam (to Polly): "Now I do too."

The problem can be narrowed down by logical steps, but I don't think it can be solved completely without some brute force. To get started, observe that if x and y were prime, Polly would be able to deduce x and y from their product. So the sum cannot be an even number. Similarly, the sum cannot exceed 99, because if y were 97, then Polly would be able to deduce x and y from the product. And so on.

I will post the final solution for x and y if enough people ask, but I'm curious how far you all will get with this.

I think I know how to work it out, but I don't have the time. Perhaps I'll work it out in a few days if nobody gets it in that time. --Michael

I realized that whatever the sum is, it cannot be 3,4, or 5 higher than any prime. A prime number + 5/4/3 means polly would be able to know the answer. So then i devised a simple brute force method: Choose a sum that is odd and meets the above criteria. Then look down the list of prime numbers that could add to it. Find the other factors for the product of those primes, which is easy - double the prime and half the associated even number. The sum of the other factors cannot meet the above criteria, or sams statement wouldn't have helped polly.

19 is the first sum that comes up. 13 plus 6 are the first numbers to check. The other factors for the product are 26 and 3 - but 29 meets same criteria as 19 and is not helpful. The next numbers to check are 11 and 8. 4 and 22 are the other factors, 26 is associated sum. Polly could know if 26 was the sum. 8 and 11 indeed seem to be the answers.

I'm afraid it isn't that simple, although we've been working along similar tracks. Counterexample: 14 + 5 = 19, 14 * 5 = 70, other factors are 7 & 10, which sum to 17...which does not meet your given criteria. Since the "solution" which allows Polly to know the numbers is not unique, Sam couldn't also figure out the numbers from her statement (as per Sam's second statement). --Mark

Incidentally, the first sum that matches your criteria is 13, not 19.

I got 13 too for that first bit. I thought I'd solved it then I realised how much more complicated it is... brute forcing such a big problem doesn't sound like much fun --Michael

(corrected and updated) With a little of brute force I found a possible solution by hand. First, to find the sums that don't lead to unique products:

- even numbers don't qualify as the sum of two primes

- a prime + 4 can also be removed

- any number from 53+3 to 53+97 can be removed as it could contain a term 53.

- any higher number can be removed as it could contain a term 97

- any product of three and a prime can also be removed as it could be the sum of a prime and the double of that prime

This leaves us with: 13, 19, 25, 29, 31, 37, 43, 49, 53, 55. We can assume that Sam and Polly both know this. For each of these, the number of sums is limited, and it is easiest to start with the smaller ones. If we can find two pairs with this sum and with a product that leads to no other of the sums listed above, then we can discard the sum as the source for a solution, because then Sam could not find the solution in the last step of the riddle.

For 13: 3*10=30 5*8=40 lead to no other of the sums above.

For 19: 5*14=70 6*13=78

For 25: 3*22=66 5*20=100

For 29: Amazingly, only 13*16=208=4*52=8*26 does not lead to any other of the sums above, the other 11 possible sums do, for example 3*26=78=6*13, 6+13=19, etc... This makes 13 and 16 a possible solution.

I am guessing 31 to 55 don't give more solutions, since the number of possible sums becomes larger for every sum.

I just wonder why the riddle is limited to x and y under 97. The analysis above holds at least also for x, y <= 105. An interesting question is whether any higher limit would yield more possible solutions. I doubt whether it would be possible to find other solutions (among all uneven numbers that are not a prime + 4). But proving it is another matter of course. But the problem would be even more impressive if it could be formulated as just x, y >= 3. -- K

Nice job, 13 and 16 is indeed the correct answer. I can't help but wonder how this puzzle originated in the first place!

Just a couple of additions to K's solution.

- I didn't understand the "prime times three" argument at first (and indeed I think it's wrong for 5 and 7). But for primes whose square is larger than 97 it is correct, so 39 actually does not belong to the list.

- I have found a fast way to rule out some of the elements on the list. If an element can be split in prime + 2^n (with n >= 3), together with Sam's first phrase this leads to a unique solution for Polly, i.e. prime * 2^n, because all other products are of the form (prime*2^m) * 2^(n-m) and their sum is even.

Any number that has two or more decompositions like that cannot be the solution.

This rules out:

- 19 (11 + 8 and 3 + 16)

- 37 (29 + 8 and 5 + 32)

- 49 (41 + 8 and 17 + 32)

- 55 (47 + 8 and 23 + 32)

and leaves six more number to be checked by brute force...

-- Roberto

Actualy you need an upper bound to get rid of even numbers, cause if there is no upper limit sam has to use the Goldbach conjecture! maybe they are perfect logicans and then know the answer to that conjecture, but maybe the answer is no :) so that's why you can't do x,y > 2  ! -- protos_drone

We wrote a computer program to go through all of the possible combinations automatically, and we indeed found 13 and 16 as a solution. However, to answer K's conjecture that it is the only solution for x, y >= 3, we were able to find no solutions for x, y <= 250, so so far the conjecture holds true. - James & Adam

[edit] 401 Circles

To fit 401 unit-diameter circles in a 2-by-200 rectangle, the construction is as follows: First set up the standard triangular packing with 399 circles: 200 along the bottom of the rectangle, and 199 resting in the gaps. Then, from the left, group the circles in sets of three. Observe that every second triad can be moved upward a small amount; go ahead and move each second triad upward until they just touch the top of the rectangle. This opens up small gaps between adjacent triads. Finally, compress all the triads horizontally to close these gaps. The compression is about 0.6%, which leaves just enough room at the edges of the rectangle to add circles 400 and 401. (The smallest rectangle for which this works is about 2 by 165, but the problem statement is cleaner with 2 by 200.)

[edit] The Hardest Logic Puzzle Ever

If you're stumped on the solution to this, Wikipedia has a page by the same name. This problem is different from the original in three ways:

• The gods were set in front of three paths and the objective was changed from determining the identity of the gods to the identity of one of the paths.
• Random behaves in such a way as to make one of the shortcut solutions invalid (This analysis exists on the Wikipedia page and the original, though).
• The Exploding heads was added as a variation for which only two questions are allowed (This analysis also exists on Wikipedia and in the original) 76.190.157.141 06:00, 27 April 2009 (UTC)

First you ask A "If I asked you if B was Random would you say ja?" Asking the question in this way, as per the Wikipedia article means that both true and false would answer it "ja" if B was random, or "da" if B is not Random. If he answers "ja" then either B is Random, or A is and happened to answer the wrong way. Either way you can be sure that C is not Random. Similarly if he answers "da" then you know that B is not Random. You then ask the one you know is not Random "is A the path to heaven?" If he answers "ja" then it is, if he answers "da" you ask the same question about path B. If he answers "ja" this time you take path B, otherwise the only choice left is C.

I agree with the first part of your explanation. However, once you figure out one god who is not random I think you should ask him "if I ask you if A is the path to heaven, would you say Ja?". If he says da you ask this question again about path B. This takes care of the possibility that "ja" means no.

[edit] Major Vandalism

A good 75% or more of the edits on this page are pure vandalism from apparently the same source. They just replace text with random characters, so it's probably a bot with a dynamic IP. Does anybody know of a good way of stopping this? 76.190.157.141 03:28, 8 June 2009 (UTC)

Lock page? --83.226.117.61 11:23, 19 June 2009 (UTC)

The page really should be semiprotected, if possible. I have no idea why the spambot is even here; it isn't advertising anything. 76.190.157.141 18:11, 21 June 2009 (UTC)

[edit] "Eckenbrechen"

I didn't find the winning strategy yet, but I can prove the first player has one: Let's assume the second player has a winning strategy, the first player can then take out the lower right box. No matter what the second player's move will be, it'll be like a first move (the lower right box would have been removed in his turn anyway) and now the first player can use the winning strategy and win, in contradiction to the fact the second player has a winning strategy. So we get the winning strategy must be the first's (there has to be a winning strategy, as there is no randomness so perfect players will always get the same result). --AtomicSheep 19:50, 16 June 2009 (UTC)

That is a pretty straightforward strategy-stealing argument, which works for all finite grids. For a finite-by-infinity grid, this no longer works, since there is no lower right square. In this case, whoever is first forced to turn it into an a X a box will lose, as per the argument above. But nobody will generally be FORCED to do so, so things might be more complicated. This is the same for an infinity-by-infinity grid. In the case of 1 X a grid, the first player will always win by leaving a single box for the second. This even holds true for a 1 X infinity grid. 76.190.157.141 18:18, 21 June 2009 (UTC)

at infinity*infinity the first player has wining strategy: if we mark the rows with 1,2,3,4 and columns with 1,2,3,4 the first step is (2,2). then if the opponent makes step (a,b ) you just make (b,a ). a or b will be 1 but this doesn't matter, after your turn the table goes simmetric, and after your secound step, the table goes finite, so after finitely many steps you win. for a*infinity i don't have the general solution, but the answer is: NO here is a (nontrivial) example: 2*infinity: with the same markings: a) If first player goes (1,x) the table is a finite rectangular table: 2nd have winning strategy. b) If first player goes (2,x) 2nd player will take (1,x+1) and so on: for every first player's step (a,b) 2nd player answers (a-1,b+1) or (a+1,b-1) [ only one of theese will exist in the table so that's a bijection for every field exept the (1,1) what is a loosing place ] - protos_drone 2:30, 01 Aug 2009

for a*infinity: a=1 -> first player has winning strategy. a=2 2nd player has winning strategy (like mentioned above) a>2 first player has winning strategy: he makes the field a 2*infinity , after that he wins with the above mentioned strategy.

tha answer to the 2nd question: YES! consider an infinity*infinity table but only the following places are free to choose: (1,1),(1,2),(2,1),(2,2) ( 2X2 rectangle ) and the places (1,n) and (n,n) Tha table has only 1 infinitely long row/column: the first row, and any place is a loosing position because you can win the game by replacing (a,b) places to (a,2) if b>1 so you get the 2*infinity table, where the 2nd have wining strategy, and every step has the same result at the 2*infinity table and at the first mentioned table.( actualy you couldn't make it from the infinity*infinity table with regular steps, but the question doesn't included that it used to be :D )

Sorry, but I don't understand the last part. What I meant in the second question was a "midgame" field, which started as an infinitly long rectangle, where exactly one row OR column (exclusive-or) is infinitely long.

What do you mean with this: "the following places are free to choose: ... ... and (n,n)"? If the place (n,n) can be deleted, then it must be a infinity*infinity field.

I ment that the question didn't allow only infinitely long ROWS/COLUMNS.Indeed the table has 1 infinitely long row and an infinitely long diagonal, but that fits the conditions.

On the other side: if u ment infinite*infinite table, and some people played on it, and now it has only 1 infinite row (WLOG) then the answer is NO.

Proof is indirect: let's assume that for every field in that row ( 1,2,3,4... ) the 2nd player has an answer when he allways wins. Because there are finitely many fields, excluded theese on the row ( 2nd player can't have "answering fields" on this row, cause they would be winning places for me ) 2nd player has the same "answering field" for a lot of fields in the infinitely long row ( pidgeon hole principle ) Now we will find the contradiction: let's start from the 1st field of the row, and check the opponent's "answering field" do this until 2 answering fields are the same.if that occurs at fields n and k ( n>k ), the 1st's winning strategy is: n, (opponend makes a decision), k, ... now the 1st player wins cause of we assumed that 2nd have a winning strategy everywhere: contradiction. - protos_drone

Wow! I wrote the puzzle but I didn't know the answer to the second question myself. I always wondered, thank you for showing me the answer.

[edit] 16 Cubes

I don't think this is possible. There are 32 possible states the cubes could have (any of the 16 cubes could be lighter or heavier), but you can only get 27 possible answers from the weighings (each of the 3 weighings could give one of 3 results). I have seen a version of this puzzle that is identical except it has 12 cubes; that version is doable and is indeed a very good puzzle. --Tektotherriggen

[edit] Four fours

65% DONE

I am going to assume we can use composition with any number as it was listed as an operation defined. Here's a few improvements and additions (by no means complete):

2 = 4-((4+4)/4), penalty 4
3 = (4+4+4)/4, penalty 4
4 = 4+((4-4)*4), penalty 4
5 = ((4*4)+4)/4, penalty 5
6 = ((4+4)/4)+4, penalty 4
8 = (4+4+4)-4, penalty 3
9 = 4+4+(4/4), penalty 4
10 = (44-4)/4, penalty 3
11 = (4/4)(4/4), penalty 4. This is (1 composition 1).
12 = (44+4)/4, penalty 1
14 = (4^(4-4))4, penalty 4 (1 compo 4)
15 = (44/4)+4, penalty 3
16 = 4+4+4+4, penalty 3
17 = (4/4)+(4*4), penalty 5
18 = (4/4)(4+4), penalty 3 (1 compo 8)
20 = 4*(4+(4/4)), penalty 5
21 = ((4+4)4)/4, penalty 3 (8 compo 4, divide by 4)
24 = ((4+4)/4)4, penalty 3 (2 compo 4)
28 = 44-(4*4), penalty 3
32 = (4*4)+(4*4), penalty 5
34 = (4-(4/4))4, penalty 3 (3 compo 4)
37 = (4(4/4))-4, penalty 3 (4 compo 1, subtract 4)
40 = 4((4-4)*4), penalty 3 (4 compo 0)
41 = ((4*4)4)/4, penalty 4 (16 compo 4, divide by 4)
42 = 4((4+4)/4), penalty 3 (4 compo 2)
48 = (4+4+4)*4, penalty 4
54 = ((4/4)+4)4, penalty 3 (5 compo 4)
56 = ((4/4)4)*4, penalty 4 (1 compo 4, multiply by 4)
60 = 44+(4*4), penalty 3
63 = ((4^4)-4)/4, penalty 6
64 = (4+4)*(4+4), penalty 4
65 = ((4^4)+4)/4, penalty 6
68 = 4+(4*4*4), penalty 5
80 = (4+4)(4-4), penalty 2 (8 compo 0. Can do without compo as [(4+(4*4))*4] with penalty 5 )
81 = (4+4)(4/4), penalty 3 (8 compo 1. Can do without compo as [(4-(4/4))^4] with penalty 6 )

Shove them in the official answer table if they're valid

-- TLH

checked all TLH's, added them to the table, and filled the rest of first column exept 33 + some others included 100 with penality 9

i'm not sure at 31 does the first "extra" operation do/capable of : 4 -> 0.4 ? -- protos_drone

With a bit of help of my computer I found the following:

13 is wrong. It should be

13 = (44)/4+sqrt(4)  : 6

Further I improved or found the following (I especially like 77):

20 = (44)-(sqrt(4)c4)  : 4
22 = sqrt((4c(4+4))c4)  : 4
26 = (44/(sqrt(4)))+4  : 6
30 = ((4+4)*4)-(sqrt(4))  : 7
31 = ((4/4)c(4!))/4  : 8
33 = ((4c(sqrt(4)))+(4!))/(sqrt(4))  : 13
39 = (4c(4/4))-(sqrt(4))  : 6
47 = 4c((4+(4!))/4)  : 7
49 = (4/4)+(4!)+(4!)  : 12
50 = (4c((sqrt(4))+4))+4  : 5
51 = (((4!)-4)c4)/4  : 7
53 = (4c(4!))/(4+4)  : 7
55 = (sqrt(4)c((4!)-4))/4  : 10
57 = (((4!)c4)/4)-4  : 7
58 = (4*4)+(4c(sqrt(4)))  : 6
59 = (((4!)c4)/4)-(sqrt(4))  : 10
61 = (sqrt(4)c44)/4  : 5
62 = ((4!)c(4+4))/4  : 7
66 = (sqrt(4)c(sqrt(4)))+(44)  : 7
67 = (((4!)c4)+(4!))/4  : 11
68 = (sqrt(4)c4)+(4c4)  : 4
70 = (4c((sqrt(4))+4))+(4!)  : 9
71 = ((4+(4!))c4)/4  : 7
72 = (4c(4+4))+(4!)  : 6
74 = ((4+(4!))/4)c4  : 7
76 = (((4!)-4)*4)-4  : 8
77 = (((4!)c(4!))/(4!))-(4!)  : 19
78 = ((4+4)c(sqrt(4)))-4  : 5
84 = ((4-(sqrt(4)))*4)c4  : 6
85 = (((4!)c4)/4)+(4!)  : 11
86 = (4c(sqrt(4)))+(4c4)  : 4
90 = ((4c4)*(sqrt(4)))+(sqrt(4))  : 9
92 = ((4c4)*(sqrt(4)))+4  : 6
94 = ((sqrt(4)c4)*4)-(sqrt(4))  : 9
96 = ((4-(sqrt(4)))c4)*4  : 6
98 = ((sqrt(4)c4)*4)+(sqrt(4))  : 9
99 = (((4!)c(4!))/(4!))-(sqrt(4))  : 18
100 = ((sqrt(4)c4)*4)+4  : 6

I didn't use the advanced operations, and I limited my search at penalty 20.
Further, if you are willing to accept that 0c4 = 4 you can easily improve more on 4 and 8.
We are still missing solutions for: 69, 73, 75, 79, 83, 87, 89, 91 and 93.

If we assume that they can not be reached by using just the basic functions (which seems very hard to prove to me), we could make these number as follows with the help of the ceiling and floor function:

69 = floor((sqrt(4c(4^4)))+4) : 13
73 = floor((sqrt(sqrt(4+4)))*(44)) : 15
75 = ceil((sqrt((4^4)c4))+(4!)) : 17
79 = ceil(sqrt(sqrt(((44)^4)c4))) : 15
83 = ceil((4+4)c(sqrt(4+4))) : 11
87 = ceil((4+4)c(sqrt(44))) : 10
89 = ceil((44)+(4c(sqrt(4!)))) : 14
91 = ceil(sqrt((4+4)c(4^4))) : 13
93 = floor((4c(sqrt(44)))*(sqrt(4))) : 14

With the ceiling and floor function we can also definitely improve 49, 67, 77 and 85, but I think the problem statement does not allow this since they can be made without also.

--K

[edit] 12 Cubes

label the cubes from 1 to 12. this'll be a little bit long, but i don't think that there exist a shorter solution so:

1st measurement: 1,2,3,4 | 5,6,7,8

Case I.: they are equal: then the secound measurement'll be

1,2,3 | 9,10,11 if that's also equal, only 12 can be the one with different waight, so 1 | 12 will give the answer: heavyer os lighter? if 1,2,3 | 9,10,11 aren't equal we'll know wether is the different cube lighter or heavyer, then we are lefti with 3 cubes and theinformation that one is (WLOG) Heavyer that's possible with 1 measurement ( for example 9 | 10 )

Case II: one side is heavyer, WLOG 1,2,3,4 > 5,6,7,8

then 2nd measurement will be: 1,5,9 | 2,6,7 if there is equality we get the answer with 3 | 4 cause we have the information that 3,4 + 2 neutral cubes are heavyer than 8 + 3 neutral cubes, so if 3>4 then 3 is the different cube, and it's heavyer, if 3<4 then 4 is the different and it's heavyer if 3=4 then 8 is thedifferent and it's lighter.

If 1,5,9 < 2,6,7 then we know that the different cube is 2 or 5 so with 1 measurement: 1|2 we get: 1=2 => 5 is different and lighter. If 1>2 => 2 is different and lighter If 1>2 => 2 is different and heavyer.

If 1,5,9 < 2,6,7 then we know that 5 and 2 are neutral because we swapped them, and the inequality still holds. so we got that: 1 + 3 neutral is lighter than 6,7 + 2 neutral cubes, so like above: 6|7 will solve the puzzle.

all cases are done. Q.E.D. - protos_drone

• An other solution would be to do the following measurements :

1 2 3 4 | 5 6 7 8

9 10 11 4 | 1 2 3 8

12 11 3 5 | 9 1 7 4

No need to make conditional measurements here, any valid combination (valid, because <<<, >>> and === are not possible) of results will allow to deduce which cube weigths different, and if it is lighter or heavier. For example, <=> means cube number 5 is heavier than the others.

[edit] Burried cable

I think the answer must depend on the number of wires, because: 1 trip separate the cables to 2 sections ( bulb is ON and it isn't ) so if i made n trips i could separate the cables into 2^n sections. if there were k ( >2^n ) cables i couldn't identify some of then cause of the pidgeon hole principle ( 2^n holes and k pidgeons. )

my solution gives [ log_{2} n ] trips where [.] denotes the Ceiling function.By induction: it goes recursively: if there are 2 cables 1 trip is enough and sufficent. If there are 3-4 cables 1 trip is not enough and i'll do it with 2: (assume there are 4 cables, with 3 it's easyer) twist the ends of 2 wires and attach to them the battery. now i have 2 sections both with 2 wires: i can do it with 1 measurement ( actualy if i had n marked sections with 2 wires in each i can make it with 1 trip ) If there are 5-8 cables (WLOG there are 8) twist the ends of 4 and i have 2 sections with 4-4 wires: i need 2 more trips. ... Assume we need n measurements for 2^n wires. If there are (2^n)+1 - 2^(n+1) wires(let them be 2^(n+1)) i twist the ends of 2^n and by induction i need only n measurements now, so had n+1 with this one. - protos_drone

Here's a hint to point you in the right direction. I'll post the full solution later if nobody gets it. Let's say the cable has 10 wires. You can do something much better than just divide them into two groups of 5 wires. You could take 2 wires and twist them together. Then you could take 3 more wires and twist them together. Then 4 wires. That would leave you with one unconnected wire, a group of 2 connected wires, a group of 3 wires, and a group of 4 wires. You could then take your battery and light bulb to the other side of the cable and determine which wire was not connected to any other wires. Which wires were in the group of 2. Which wires were in the group of 3. etc.

Ah, i thought i must attach the battery to some wires, then leave the battery and go to the other side to check everything with the lightbulb. (that would be logical i think) now i need the definition of a trip. you used a fixed twisting, and then battery-bulbed everything, but if the ends of cables are in different buildings you must make several trips to check wich cable is in a 2-group or 3-group etc. (Where my pidgeon hole principle proof still works) - protos_drone

If you twist all the ends on one side of the cable as I describe, then take your battery and light bulb to the other end of the cable, you can determine all the groupings without making multiple trips. Here's how you can test if two wires are connected on the other end of the cable. Connect one wire to the positive terminal on the battery. Connect one end of the light bulb to the negative terminal on the battery. Then connect the second wire to the other end of the light bulb. If the two wires you're testing are twisted together on the other end of the cable, the circuit will be completed and the bulb will light up. By repeating this processes for every combination of two wires, you can map out how all the wires on the other end of the cable are twisted together without physically walking over to the other building.

Let's say you had enough wires to make 99 groups (2 through 100) plus you left one wire unconnected. After your first trip to the other building, you would have one known wire -- the one that was not connected to any other wires. For your 2-group, connect the known wire to one wire and leave the other disconnected. For your 3-group, connect the known wire to one wire in the group and leave the others disconnected. For 4-group and higher, connect the known wire to one wire in the group, leave one wire disconnected, and twist the remaining wires together. By doing this, you will have two more known wires for every group except your 3-group. In the 3-group you will only have 1 known wire. So for this example, when you make your second trip you will have uniquely identified 198 wires. Since your largest group only contains 100 wires (98 of which are unknown), you only need 98 of your 198 known wires to identify all the remaining wires. Just connect the first known wire to the first unknown wire in each group, the second known wire to the second unknown wire in each group, etc. Using this strategy, you can always identify all the wires in no more than 3 trips (though you will need a 4th trip if you want to untwist all the wires on the other end).

Looking at the problem more generically, if you start with N groups of wires with only one left over as an unconnected wire, then after 2 trips you have uniquely identified 2*N wires and your largest group only has N-1 wires that are unidentified. However, sometimes it may not be possible to evenly divide your wires into N groups. In this case, you may need to duplicate one of your groups in order to be left with only one unconnected wire on the first trip. So in this worst-case scenario you will have identified 2*N-4 wires after your second trip, and your largest group will contain N-2 unidentified wires. Since 2*N-4 >= N-2 for any cable that can be divided into at least 3 groups (any cable with at least 8 wires -- 2,2,3 + 1 unconnected), this strategy is sure to work for any cable with at least 8 wires.

Now, for cables with a certain number of wires it is possible to use a variation of the above strategy to uniquely identify all wires in only 2 trips. A cable containing 1035 wires is one example where this is possible, but it's not the only one. See if you can figure out the strategy and what special property has to be true about the number of wires for the strategy to work.

Interestingly it can't be done at all for two wires. One is trivial and three is fine but two is not possible...

[edit] God of Math

We start with two tetrahedrons, joint at one triangle. We use up 9 matches and form 7 triangles. Then we bend both peaks in the sames direction in the forth dimension. All lines still have the same lenght but the endpoints are nearer than before. If we do it just right, we can form three new equilateral triangles with only one match.

Actualy what u made is the 4 dimensional analogue of the tetrahedron, it's called a 4-simplex.MAybe a little bit harder question is can you proove it that this is the only solution? - protos_drone

Yes I can. We can project a three-dimensional Objekt on a two-dimensionsional surface. We do this everyday. We must be able to do this with a four-dimeninsional object, too. So if our object has n vertices, our projected image will have n vertices, too. Now we need to find out if we can create 10 triangles with 10 lines, while using each vertex at least once. The lines do not necessarily have to be the same length but we must be aware that the lines do not actually cross each other. We can't do this with three or four vertices but there is one solution with 5 vertices. This doesn't automatically mean that this is an actual solution, but I have already shown that there is a solution with 5 vertices (the 4-simplex). When we try to use more than 5 vertices, we will end with less than 10 triangles. You get the highest triangles/lines ratio if you connect every vertex with each other vertex and with 5 vertices it only just worked. This isn't a proper prove, but you can verify it if you want to be sure, because there cannot be more than 10 vertices and there are only a finity number of possibilities for each number of vertices.

That's why there's no solution with more or less than 5 vertices and only one with 5.

I would start with laying a 'star of david'. This gives you 8 triangles with just 6 matches. After that it is easy to expand this to 10 stars with the remaining matches, for example by building triangles on two opposite sides of the star with two matches each. - K

i would say that u have only 2 triangles in the star of david-like construction, cause of the definition of the triangle, that's a 2 dimensional object!

Clever. I first thought that each triangle had to be the same size as every other triangle. I also assumed that the matchsticks had to match up to each others ends and not overlap. I also assumed that the triangles had to be made without anything in between the sides. (Ie: the triforce would only be 4 triangles). If I hadn't reached a 4-dimensional solution, I might've recognised how much I assumed without someone else pointing out my errors. :(

Wonder how many other people made as silly assumptions as I?

[edit] Diabetic Dilemma

You put the bottles in the pool, regular coke sinks while diet coke floats.

[edit] Sequence

A little hint: 1,1,2,720, ~6*10^23, ~6*10^198 the 12th element in the sequence has over 286 million decimal digits (Just to make it easy to interpolate xD ) What do you think about when u see 720? of course the factorial!

0!=1

1!=1

2!=2

6!=720

x!="next number"

So, i basically find next number in the following sequence: 0,1,2,6

(0!+1!)!=2

(1!+2!)!=6

(2!+6!)!=722!

the "next number" can be (722!)!, although it's larger than 6*10^23.

Not so bad but how would you deal with the previous element of the sequence?, let me help you a little bit: 6=3! - protos_drone

Then it looks like double-factorialed fibonacci sequence.

1,1,2,3,5,8...

(1!)!, (1!)!, (2!)!, (3!)!, (5!)!=120!

although 120! is again more than 6*10^23...

oh, i finally got it. it's not fibonacci, just double-factorialed integers.

(0!)!,(1!)!,(2!)!,(3!)!,(4!)!...

The second sequeence is pretty easy if you say it out loud and write it down veritcally

1) 1

2) 11

3) 21

4) 1211

5) 111221

Ignoring the starting 1, we'll start at 2). What is the first number in the previous line, and how many of them are in a row? The first number is 1, and there is 1 of them, so 2) = 11. Same thing for 3) The first number is 1, and there is two of them. therefore 3) = 21.

After 3, it's the same process, but the number you're checking changes. So usuing the same logic, wel'l get 4) = 12, but we still have to account for the next number in the sequence, i.e. the 1, and there is only one of them, so 4) = 1211. If you say it outloud it helps.

4) (referring to 3) There is one 2 and one 1. (1211)

5) (referring to 4) There is one 1, one 2, one 1 (111221)

6) (referring to 5) There are 3 1's, two 2's, and one 1 (312211)

Now a much harder question is, can you prove that no number in this sequence will have a digit greater then 3? (Add this to the puzzle if you want)