Duck In A Wolf

Seems like its time to solve the advanced Wolf and Duck problem now. First, we should set up some coordinates (because I don't want to go through the trouble of making pictures on blogger). We will set up polar coordinates in the pond, with R going from 0 to 1 (1 being the edge of the pond), and θ going from 0 to 2π. We know the duck can manage to get to a radius 1/v and be on the opposite side of the pond from the wolf (using previous strategies). Let us set up coordinates so the puzzle starts with the duck at θ=0, R=1/v and the wolf is at θ=π at R=1, of course.

Now, the duck will travel a small distance epsilon out to the edge of the pond, and the wolf must choose to go in the direction of increasing θ or decreasing θ. Let us assume the wolf goes in the direction of increasing θ. The duck will now head for the point of escape (assuming there is one) at R=1, θ=φ. There is little point in the wolf changing directions now, as the duck will have gained a small distance epsilon toward the edge again before the wolf just gets back to its original location. There is also little point in the duck taking any path more complicated than a straight line, as wherever the escape point is, the duck might as well go straight there.

The wolf must get to the position φ before the duck can. The wolf must travel a distance φ+π. The duck must travel the distance D, given by the cosine law as:

D² = 1+1/v²-2/v cos(φ)

Now, let f(φ) be the function representing the amount of time between when the duck gets to the escape point and the wolf gets to the escape point. Specifically, f(φ) = D-φ+π)/v. Maximizing f(φ) gives one:

sin(φ) = D

So this means that the duck will travel tangental to the circle of radius 1/v. When sin(φ)=D we know cos(φ)=1/v, if this isn't obvious, you should probably be drawing a picture to follow along, I certainly needed to.

The value of f(φ) when sin(φ)=D (and thus cos(φ)=1/v) can be given as sin(φ)-(φ+π)cos(φ). If we set that to zero (to find the situation when the duck no longer beats the wolf to the edge) we find that:

tan(φ)= φ+π

Which has a solution at φ≈1.35 . Thus, v=1/cos(φ)≈4.6 is when this strategy will fail for the duck.

As far as I can tell, when the wolf speed is greater than this value, the duck can do nothing to escape, but I have found no proof of this.

Wolf Near A Pond

Alright, the comments section seems to imply that at least one person has solved my Wolf and Duck problem, so I suppose I'll post the solution now:

The duck moves out to a circle 1/4 the radius of the full pond. At this radius, the duck has a faster angular velocity of the wolf, so the duck can go in a circle until the wolf is on the far side of the pond from the duck. At the point, the duck goes straight to the edge, as the duck can traverse the distance of 3/4 before the wolf can traverse the distance π .

Just a note because we don't all use the same browsers, π is supposed to render as pi. In Safari it looks really weird.

Alright, what is the maximum wolf speed for which this works? In general, if the wolf has speed v, the duck can go out the a distance 1/v and still have a greater angular velocity. The duck must then travel a distance 1-1/v before the wolf can travel a distance π . So, the duck requires that:

1-1/v < π/ v v < π+1

Thus, this strategy works until the wolf has speed π+1.

Next question:

Suppose we increase the speed of the wolf to 4.3 times the ducks speed, can the duck do any better? What is the maximum wolf speed for this new strategy?

I'll concede this isn't really a new question, but really it feels like one. The better strategy is alot harder to find and requires some more complicated math to prove it works and is optimal. However, I still promise that all shapes involved are simple geometrical shapes, lines and arcs of circles basically.

Duck In A Pond

Alright, been a full two weeks since I posted. I seem to be on the "new puzzle" part of my cycle, so I suppose I'll do one of those. This one looks a bit less mathy than my usual puzzles, but it really isn't. I first learned this one from Bart:

A duck is at the center of a circular pond with radius 1. A wolf is at the edge of the pond and is able to move around the circumference. The duck wins if it is able to get to the edge of the pond with no wolf there. Find a strategy that can guarantee the duck can escape to the circumference assuming that the wolf moves 3.5 times as fast as the duck.

For clarity, you can assume the duck is pointlike and the wolf has a small size epsilon (the wolfs size is needed to dodge weird solutions involving the duck touching an irrational point on the circumference and the wolf cannot access him). To qualify as a solution, it must work for some epsilon greater than zero. I will say that the proper solution involves no weird spirals or things, all shapes are simple geometrical objects that you can calculate lengths of easily.

There are a few follow-up questions to this one, I'll post one of them later, but for now:

What is the maximum speed of the wolf for which this strategy still works?

Hamming Hats

So, I hope everybody is ready for the solution to the hat problem from last time. Its a pretty good one, and combines a bunch of ideas I have set forward in previous puzzles.

First, one would like to solve a few cases with small N. The N=1 case is trivial, of course, you can't get better than 1/2 chance of success. Sadly, the two person case is similar, you cannot do anything better than 1/2 again. In the three person case however, we can do better with the following strategy:

For each person, guess black if both hats you see are white, guess white if both hats you see are black, and pass otherwise.

So, if the hats are white, white, black, then the black hat guy will guess correctly and the other two will pass. If the hats are white, white, white, then everybody will guess black and be wrong.

This is good, because we know that in a puzzle where one person being right is sufficient, then we don't want two people to be right at the same time. Also, in a puzzle where one person being wrong makes it all fail, we know that we should try to make it that everybody is wrong at the same time. Our solution will work unless everybody has the same hat colour, so the chance of success is 3/4.

So, in the case of general N now. We want that in any given situation, one person will guess correctly, or everybody will guess and be wrong. I honestly can't remember the logic I followed to get to the solution in the general case, but here is the solution in the N=7 case:

Treat a distribution of hats as a binary sequence of 7 digits, call it X. Each person knows all the bits except their own. Construct the Hamming set S of binary sequences of length 7. Each person is to look at the hats around, and if it is possible (based on the one missing bit) that X is an element of S, then make a guess assuming that X is not an element of S. If it is not possible X is an element of S, then pass.

If you have forgotten about Hamming codes, take a look at the sam and ray solution. So, since each string of length N is within one bitflip of an element of S, then unless X is an element of S, exactly one person will guess and they will be correct. If X is an element of S then everybody will guess and be wrong. The probability of failure is 2⁴/2⁷ which is 1/8.

If you have 10 people, say, then you just split 7 of them off and have them use that solution, have the other 3 always pass. In general with N people, split off M people so that they construct the largest Hamming set you can (it will be when M+1 is a power of 2) and have the remaining N-M people pass. The M people have a 1/(M+1) chance of failure, which will go to zero as M goes to infinity (and M goes to infinity as N goes to infinity, just taking a different path).