Solutions to Classic Mathematical puzzles

Can the Duck escape from the Bear?

I've seen many discussions of this problem, and very bright puzzle solvers have gotten caught up in fallacies. I hope to present a clear argument and address some of the fallacies.

Let the radius of lake and the speed of the bear both be R in arbitrary units, and the speed of the duck 1. When the duck is less than one unit from the pond's center, his angular speed will be greater than the bear's angular speed so he will be able to locate himself opposite the bear, and at distance R+1 from him. We might call this radius-1 circle the duck's "comfort circle." (This already leads to an improvement over the 3.14159 bear speed, but we can do better still.)

If you Google to find this problem, e.g. "fox duck Microsoft interview" you'll find the R = 4.14159 solution just implied. This suggests how difficult the real problem is. Most of the on-line "solutions" are satisfied to get this far, and ignore that the duck can succeed against significantly faster bears.

If the duck should make a mistake in executing the following, he can return to the comfort circle and start over.

After leaving the comfort circle the duck continues to swim away from the bear a short distance, looks over his shoulder, and sees which way the bear is running. The bear has committed himself. Duck can proceed on the assumption that bear will continue in the direction he selected.

Many object to this: Why can't the bear somehow trick the duck and reverse course? Answer: The duck will look over his shoulder from time to time to make sure no such ploy is attempted, so it will be wrong for bear to attempt it. At any point the bear's optimal strategy, knowing duck isn't an idiot, will obviously be to proceed in the direction which forms an acute angle, rather than obtuse, with the duck's position. If the duck crosses into the opposite semicircle relative to the bear, duck has misplayed.

(BTW, the "short distance" the duck travels away from his comfort circle will not affect the analysis. This short distance can be treated as an infinitesimal and ignored in the calculations, with the bear's deduced maximum speed infinitesimally smaller. This may also be a point which causes confusion.)

Now what should the duck do after bear commits? He should make a beeline for some point on shore, specifically the point that would be rendezvous point if the bear has the smallest deadly speed. That the correct path is a straight line should be clear: it's the fastest way for duck to get to that rendezvous! (This is another place where solvers often go wrong. Many expect the solution to be some sort of spiral. ... But the shortest distance between two points is a straight line!)

So where is the "rendezvous" or, equivalently, which way should the duck turn when the bear commits? He cannot let the turning angle be acute (i.e. return to the comfort circle); the bear would reverse himself and the process would start over. So the maximum angle is perpendicular, the line tangent to the comfort circle. It reminds only to demonstrate that that leads to optimality, and we're done.

The duck's distance to the rendezvous is sqrt(RR-1) and the bear's distance is R * (1.5 π - arcsin (1/R)). The duck will succeed if the bear's speed is less than the ratio, or
    R   <   R * (1.5 π - arcsin (1/R)) / sqrt(RR-1)

The solution to this seems almost magical! The warden's shuffling creates a permutation defined by the drawer number to slip number function, and each prisoner number will occur in a cycle. For example, if prisoner #13 starts by looking in drawer #13, finds slip #6, looks in drawer #6 to find #9, looks in #9 to find #11, and so on, he will eventually find slip #13 (unless he exhausts his fifty chances first).

If there's a cycle of length 51, then all 51 prisoners in that cycle will fail. But if all cycles are length 50 or less, then all prisoners will succeed.

Assuming you can guess nothing about the distribution of dowry sizes, your only plausible plan is to reject a fixed portion (a) of the girls and then pick the next dowry which is the highest seen so far. We'll simplify the analysis by assuming there are infinitely many girls, assigned to the real segment [0,1].

If the high-dowry is at position t, the chance you'll pick her is 0 if t < a and a/t otherwise. This second expression is the chance that the highest-dowry before t is in the rejected set. (If not already rejected, you'd pick her and lose.) Thus your average chance of success, depending on your choice of parameter a is
     S(a) = ∫_a¹   a dt / t

The anti-derivative of a/t is a ln t, so the definite integral evaluates to S(a) = - a ln a. To find the optimal a we set d S(a) / da = 0; -1 - ln a = 0; a = 1/e. The chance of success is S(1/e) = 1/e.

So your plan is simple. Reject 36.8% (1/e) of the girls, then pick the next girl whose dowry exceeds all the rejected dowries. She'll exist and have the highest dowry 36.8% of the time.

Pick one of the two largest Dowries

For the case where you also win with the 2nd-highest dowry, you'll have a two-parameter strategy. Reject portion a as before, then look for a maximum but, if you're still looking after total portion b then accept a 2nd-highest dowry. To evaluate your chance, start by listing the five cases where you win. Let w denote the position of the globally highest dowry, v the position of the 2nd-highest, x the largest dowry seen prior to your target (w or v) and y the 2nd-largest seen prior to your target.

Cases:

1. x < a < w < b
2. x < a < b < w AND y < b
3. x < a < v < b,w
4. x < a < b < v < w AND y < b
5. w < a < b < v AND y < b

These cases are mutually exclusive, so we need simply sum their chances which are (t denoting w in the first two cases, v in the others)

1. ∫_a^b   a dt / t     =     a ln b - a ln a
2. ∫_b¹   ab dt / t²     =     -ab + a
3. ∫_a^b   a(1-t) dt / t     =     a ln b - a ln a - ab + aa
4. ∫_b¹   ab(1-t) dt / t²     =     -ab + a + ab ln b
5. ∫_b¹   ab dt / t     =     - ab ln b

The sum of these five expressions is our success chance
    S(a,b) = a² + 2a - 3ab + 2a ln b - 2a ln a

d S(a,b) / db = -3a + 2a/b, so the optimal b is given by -3a + 2a/b = 0 and is b = 2/3 independent of a. Substituting this value of b, we get
    S(a) = S(a,0.66667) = a² - 2a ln (3a/2)
    d S(a) / da = 2a -2 ln (3a/2) - 2

The optimal a is given by d S(a) / da = 0, which yields a - ln a = 1 + ln (1.5). This is solved numerically by a ~= .34698160971.
S(a) ~= .57356698194.

I'm sure there's a simple elegant argument explaining why the optimal paramter b is 0.6666667 exactly. Maybe I'll figure it out when my brain clears. Let it be a challenge for any reader. But meanwhile, here's a somewhat tedious derivation:

We need only prove that that b=.66666667 is the break-even point for switching strategies. We write that the probability that the unique dowry at position b=.6666667 is the 2nd largest is p, the probability it's 3rd-largest is p, 4th largest p, and so on. This is clearly true for some p; we needn't even solve for p. We know that in the relevant case, the element at b=.66666667 is the 2nd-largest seen up until then; that is, among the k elements larger than it, 1 occurs before b, and (k-1) occur after b. If we skip b, we win with probability 0 when k = 1, and win with probability 2/k when k > 1. If we accept b, we win with probability 1 when k = 1, but with 0 when k > 1. Thus the acceptance probability is (2p/3) -- the probability that one element is in the first 2/3 of the interval. We seek to prove that this is equal to the sum of the skipping win probabilities.

The skipping win probability for any k is (2pk*2/k(3^k) = (4p/3^k). (In the denominator the k counts the choices for first of the k large elements; the 2/k gives the chance that next big encountered after the skip will be a winner.)

So the sum of the skipping win probabilities is 4p/9 + 4p/27 + 4p/81 + ... = 2p/3. Q.E.D.

If we extend the problem to achieve victory on any of the N best dowries, we get an N-parameter strategy, with the final parameter (z) being the easiest to calculate. I get that the optimal z is the solution of
    1 = N * sum for k=0 to infinity (C(N+k, N-1) * (1-z)^(k+1) / (N+k)).
For N=3, z = sqrt(.6) ~= .7746

Among the five, there will be at least two of the same suit. The difference, modulo 13 of those two cards, in some order, will be 1, 2, 3, 4, 5, or 6. Secrete the higher of the two, expose the other in first position, choose one of 3! permutations of the other three cards according as that difference was 1, 2, 3, 4, 5 or 6.