A duck, pursued by a fox, escapes to the center of a perfectly circular pond. The fox cannot swim, and the duck cannot take flight from the water. The fox is four times faster than the duck. Assuming the fox and duck pursue optimum strategies, is it possible for the duck to reach the edge of the pond and fly away without being eaten? If so, how?
[Math] The Fox And The Duck Puzzle
puzzle
Related Solutions
Wlog. $R=1$. If $C$ is an integer, no cuts are required. Otherwise let $c=C-\lfloor C\rfloor$, a real number between $0$ and $1$. Each rope must finally contain at least one cut end, thus the number of cuts is at least $\frac N2$ and it is easily solvable with $N$ cuts.
Indeed, $\lceil \frac N2 \rceil$ is enough if $c=\frac12$.
If $c=\frac23$, one can produce $\lceil \frac23 N\rceil$ pieces of $\frac23$ and combine the $\frac13$ rests for the remaining ropes, hence $\lceil \frac23 N\rceil$ cuts suffice.
If $c=\frac13$, then $\lceil \frac23 N\rceil$ cuts suffice again.
For $c=\frac34$ or $c=\frac14$, I can do it with $\lceil \frac34 N\rceil$ cuts, for $\frac k 5$ with $1\le k\le 4$, I can do it with $\lceil \frac45N\rceil$ cuts.
A pattern sems to emerge here, but I'm not sure if it is really optimal: $c=\frac pq$ requires $\lceil (1-\frac1q)N\rceil$ cuts. And if $c$is irrational, $N$ cuts are needed, I suppose.
Remark: If the final result is correct, there is no need to go for $c$, one can directly say that $\lceil (1-\frac1q)N\rceil$ cuts are needed if $\frac CR=\frac pq$.
Edit: (Revisited this answer after a few years in order to add proof)
Allowed solutions consist of an algorithm that describes a sequence of cuts and (at no cost) concatenation operations. I tis clear that any such solution can be brought into this standard form:
- Cut some of the unit length input ropes into pieces.
- Combine the pieces into the $N$ output ropes (plus possibly some waste)
It doesn't harm to allow the following more general form:
- Combine unit length input ropes into some integer length intermediate ropes.
- Cut the intermediate ropes into pieces
- Combine the pieces into the $N$ output ropes and combine the waste pieces (if there are any) into a "waste rope"
Our task is to find an algorithm that minimizes the cuts performed in step 2. To do so we consider all algorithms that achieve the minimal number of cuts, and among these consider the one that minimizes the number of intermediate ropes produced in step 1.
If two of the pieces an intermediate rope is cut into end up in the same output rope, we can rearrange the locations of the pieces on the uncut rope in such a manner that they are adjacent, which allows us to save a cut. By the minimality of our algorithm, this does not happen. That is: Each intermediate rope contains at most one contiguous piece from each output rope; note that this applies also to the waste rope.
Assume two distinct intermediate ropes each contain a piece of the same output rope, say one intermediate rope is cut into pieces of lengths $a_0, a_1,\ldots, a_r$ by $r$ cuts and the other is cut into pieces of lengths $b_0,b_1,\ldots,b_s$ by $s$ cuts and that the pieces of length $a_0,b_0$ both end up in the same output rope. Then we can instead combine these two intermediate ropes into one and cut it into $a_0+b_10, a_1,\ldots, a_r, b_1,\ldots,b_s$ with the same number $r+s$ of cuts, but with less intermediate ropes. By our choice of algorithm, this is impossible. Therefore: Each output rope is contained in exactly one intermediate rope; again, this also applies to the waste rope. In particular, there is at most one intermediate rope containing waste. We may additionally assume (by rearranging parts) that the waste part occurs at the end in its intermediate rope.
A wasteless intermediate rope as a positive length $\in \Bbb Z\cap C\Bbb Z$. If $C$ is irrational, this is not possible. Hence in this case there is only one intermediate rope and it requires $$N $$ cuts at positions $C, 2C, \ldots, NC$.
If $C=\frac pq$ with $\gcd(p,q)=1$ is rational, the length $\ell$ of a wasteless intermediate rope must be $\in \Bbb Z\cap C\Bbb Z=p\Bbb Z$ and it is cut at positions $C, 2C, 3C,\ldots$. If $\ell>p$, we could save a cut by replacing it with intermediate ropes of lengths $p$ and $\ell-p$. By minimality, this is not possible, hence each wasteless rope has length $p$ and needs $q-1$ cuts to produce $q$ output ropes of length $\frac pq$. By the same argument, the number of output ropes in the wasteful intermediate rope must be $<q$ and requires just as many cuts. We thus have described an algorithm that for $N=qM+R$, $ 0\le R<q$, requires $$(q-1)M+R =N-\left\lfloor\frac Nq\right\rfloor $$ cuts and is optimal.
The question stated that there were three more people than when the wagon started out in the morning, not three more than in the last breakdown.
Best Answer
Definitions
Let $R$ be the radius of the pond. Let the velocities be $v$ for the duck, and $4v$ for the fox (see diagram).
Phase 1 - The Headstart
As long as the duck stays with a circle of radius $\frac{R}{4}$, he can ensure that he keeps the fox as far away as possible (on a diametral line to himself) by turning in a spiral, where his maximum outward velocity is given by:
$\dot{r} = v\sqrt{1 - \dfrac{16r^2}{R^2}}$
Phase 2 - The Escape
Assume now that the duck has reached the point $D$ (as shown) at a radius $r$ from the center (with the fox at point $F$), and wants to begin phase 2. His fastest route to shore takes him to point $S$ and covers a distance of $R-r$, while the fox must cover arc length $R\pi$ to reach $S$. Hence, for the two times:
$t_D = \dfrac{R-r}{v}$ for the duck, and $t_F = \dfrac{R\pi}{4v}$ for the fox.
If the duck is to make safety we need
$\dfrac{R-r}{v} < \dfrac{R\pi}{4v}$ or $r > (1 - \dfrac{\pi}{4}) R \approx 0.2146 R$. Since this is within the spiral zone $(r < \dfrac{R}{4})$,
the duck will be able to safely reach the shore.