12
$\begingroup$

(This is the sequel to this puzzle. It has a similar setup, but believe me, the solution is very different. Be careful! The answer is counterintuitive. It shocked me at first.)

You are a pirate. Previously, you captured a rogue mutineer. She begged for a second chance on the crew, in exchange for the location of her criminal headquarters: Marauders' Circular Cove.

In promise of great treasure, you raided the cove at night. But it was a trap! Now smugglers are coming out of the forest, more than you can count.

enter image description here
(Pictured: there are WAY MORE than this)

Your ship moves at the same speed as the smugglers. The smugglers cannot swim. If you manage to take even one step onto the shore, then you can instantly beach the ship and escape into the cover of darkness.

Right now (and only right now, i.e. not after the chase starts), you can bribe some of the smugglers to leave, so that you only have to evade $n$ of them. Your goal is to reach the shore without getting caught. The smugglers' goal is to catch you when you reach the shore, or starve you out on the lake forever.

How many smugglers can you evade, if the cove is shaped like a perfect circle?

The ship and smugglers are all points of zero radius. Everyone can always see everyone else's position. This is not a loophole-finding contest: there are no issues with reaction time, scurvy, et cetera.

$\endgroup$
  • $\begingroup$ Where'd you get the smuggler sprite? It's cute. $\endgroup$ – Joe Z. Apr 24 '15 at 18:34
  • $\begingroup$ Well, this is a loophole, but if you specifically say that everyone is a zero radius point, you can evade an infinite number of them, can't you? They can't possibly get close enough together so that you couldn't find a path to slip between them. And since you travel at the same speed, and you are closer to the center of the lake than they are, you can traverse the circumference quicker than they can, so they can't just mirror you to block you. $\endgroup$ – Eric Apr 24 '15 at 18:36
  • 9
    $\begingroup$ ...How did you get your ship in there in the first place!? $\endgroup$ – Engineer Toast Apr 24 '15 at 18:38
  • $\begingroup$ I am of the belief that you can evade an infinite number of smugglers but I can't wrap my head around how to prove it mathematically. $\endgroup$ – Engineer Toast Apr 24 '15 at 18:54
  • $\begingroup$ I'm not sure I get the point of the bribery... doesn't that make it so you can evade infinitely many smugglers by bribing the finite subset of them that are on the shore when you reach it? $\endgroup$ – Ian MacDonald Apr 24 '15 at 18:55
4
$\begingroup$

It is possible to escape from

any finite number of smugglers.

Say the lake has unit radius. Label the boundary of the lake with angles $\theta$, measured in radians. We will begin by heading to a point near the boundary of the lake, by angle $\theta=0$. For the moment, pretend we actually reach the boundary but cannot escape due to a smuggler (moving inward just a bit will not change the answer).

Suppose we choose a point $0<\theta<\pi$ on the boundary and head straight there. The distance to this point is $2\sin(\theta/2)$, so to keep us from escaping, there must be a smuggler somewhere in the arc $$A_\theta:=\big[\theta-2\sin(\theta/2),\,\theta+2\sin(\theta/2)\big].$$ We will find an infinite sequence $\theta_1,\theta_2,\ldots$ of angles such that the arcs $A_{\theta_1},A_{\theta_2},\ldots$ are disjoint. This means that for any positioning of a finite number of smugglers, there will be some $\theta_i$ that we can reach before any of them.

We define the $\theta_i$ recursively. Start with $\theta_1=\pi$. For $i\geq 2$, define $$\theta_i=\frac{\theta_{i-1}-2\sin(\theta_{i-1}/2)}{2}.$$ Observe that $0<2\sin(\theta/2)<\theta$ for every $0<\theta<\pi$, so that $\theta_1>\theta_2>\ldots>0$. The arcs $A_{\theta_i}$ are disjoint because $\theta_{i-1}-2\sin(\theta_{i-1}/2)>\theta_i+2\sin(\theta_i/2)$, which comes from the definition of $\theta_i$ and the inequality $\theta_i+2\sin(\theta_i/2)<2\theta_i$.

If there are $N$ smugglers, the arcs $A_{\theta_1},\ldots,A_{\theta_{N+1}}$ are disjoint, so there must be one of these arc $A_{\theta_i}$ containing no smugglers. We then head directly toward the point $\theta=\theta_i$, and no smuggler can keep us from escaping.

Finally, suppose that instead of starting on the boundary of the lake, we instead start $\epsilon>0$ units in from the boundary. For each $0<\theta<\pi$, we define $A^\epsilon_\theta$ to be the arc of points on the boundary of the lake from which a smuggler could reach the point $\theta$ as quickly as we can. The arcs $A_{\theta_1},\ldots,A_{\theta_{N+1}}$ are disjoint, so for $\epsilon$ sufficiently small, $A_{\theta_1}^\epsilon,\ldots,A_{\theta_{N+1}}^\epsilon$ will also be disjoint. This means we can still find $i\in\{1,\ldots,N+1\}$ such that we can reach $\theta=\theta_i$ before any of the smugglers.

$\endgroup$
  • $\begingroup$ Yes! A solution with mathematical rigor! $\endgroup$ – user2357112 Apr 26 '15 at 0:22
  • $\begingroup$ +1 for the proof, good job! I noticed that your series converges to zero very quickly. Which means that if the ship had a nonzero size of say a 1e-6 radius circle, you could only find less than 10 disjoint arcs before the arcs became smaller than the ship. I wonder what would be the solution in that case (whether there could be a movement strategy that could evade more than 10 smugglers). Maybe that could be pursuit problem #3? $\endgroup$ – JS1 Apr 26 '15 at 4:54
  • 2
    $\begingroup$ Good job on the rigor. Here was my strategy: run along a series of rapidly-shortening chords. With the first chord, ensure that you leave the first smuggler far behind. With the second, leave the second smuggler far behind. Et cetera... In fact, you can even dodge countably infinitely many smugglers with this strategy. This means that, even if a smuggler starts at every rational point around the shore, you can still win(!!!) $\endgroup$ – Lopsy Apr 29 '15 at 15:26
6
$\begingroup$

Surprisingly,

the marauder can always escape!

enter image description here Suppose you have a very very high number of smugglers. The strategy to escape is approaching the coast as much as possible (the more the smugglers, the closest you have to be), then follow a straight line (a chord) which is always shorter than the smugglers' path to reach you.
Check the picture: when you come very very close to the coast, the other smugglers won't be able to stay near enough, so you can easily pass between them!

$\endgroup$
  • $\begingroup$ it is a pirate vs smugglers this time. This is the same as JonTheMon's answer, isn't it? $\endgroup$ – JLee Apr 24 '15 at 19:11
  • $\begingroup$ @JLee the final answer is the same, but I didn't fully understand his explanation; that's why I've decided to post a (hopefully) clearer answer. $\endgroup$ – leoll2 Apr 24 '15 at 19:19
  • $\begingroup$ i do like your illustrations. it makes it that much easier to visualize. +1 $\endgroup$ – JLee Apr 24 '15 at 19:19
  • 4
    $\begingroup$ But what if instead of maintaining an even distance with each other, the two closest smugglers formed a trap. In other words, as you approach point X on the edge, one smuggler stays on each side of X, close enough to intercept if you keep heading to X but no closer. Then you can't run on a chord and escape. The other smugglers would also approach closer, the closer you got to the edge of the circle. $\endgroup$ – JS1 Apr 25 '15 at 1:38
  • $\begingroup$ Btw I still think the answer is infinite, it's just that the proof needs to be more extensive. $\endgroup$ – JS1 Apr 25 '15 at 2:19
2
$\begingroup$

I think you can evade:

an infinite number of smugglers

Say you are 10 feet from the edge of the cove. A smuggler would have to be within 10 feet of the closest point on shore or you'll escape. If smugglers are spaced every 20 feet, with one on the shore closest to you, you can circle the ship until you are between 2 smugglers, then make a break for it.

Now take it further. Say you're 1 foot away. Now smugglers would have to be spaced every 2 feet. 1 inch leads to 2 inch spacing. Eventually you can get close enough to handle any gap between smugglers.

$\endgroup$
  • $\begingroup$ This makes sense to me. It also makes me wish that the ships and smugglers had some radius, to make the answer more definite, and smaller. Maybe you should mention that the pirate travels the circumference faster than the smugglers. $\endgroup$ – JLee Apr 24 '15 at 19:02
  • $\begingroup$ This is the logic I was using and makes sense to me when treating everything as points of zero radius. Not 100% convinced but seems right. $\endgroup$ – Mark Balhoff Apr 24 '15 at 19:02
  • $\begingroup$ @JLee I think the fact that the circle can be infinite in size, even if you gave them a radius, the size of the circle could just scale larger to make the radius of the smugglers insignificant $\endgroup$ – Mark N Apr 24 '15 at 19:07
  • 2
    $\begingroup$ Why would the smugglers maintain a fixed spacing while they watch you approach? $\endgroup$ – user2357112 Apr 25 '15 at 1:59
  • 1
    $\begingroup$ @JonTheMon I don't think it's true that you can always get in between two smugglers. Just consider two of them trapping you from each side. They can always maintain the required spacing if you just head toward the edge. $\endgroup$ – JS1 Apr 25 '15 at 7:22
0
$\begingroup$

Since the answer has already been stated, I thought would provide another view as to why it takes

infinite smugglers.

enter image description here

Here the red dot is our boat, and the green dot is a smuggler. Since the shortest path our boat can take to shore (safely) is X length, and the green dot must move at least (sqrt)(x²+y²), X will always be shorter. If you were to add another smuggler onto the curve, the boat simply needs to move close enough to the shore such that only one dot is remaining (like the picture). [Think of it as you are trying to race your friend to a finishing point and only have to travel in a straight line (shortest possible distance) and your friend is trying to beat you to the finish line, but has to travel along a curve]

$\endgroup$
  • $\begingroup$ What happens if you run tangent to the edge of the lake, like in the lake monster question? $\endgroup$ – Joe Z. Apr 24 '15 at 18:42
  • $\begingroup$ For reference, @JoeZ. is talking about this question and, in particular, this answer $\endgroup$ – Engineer Toast Apr 24 '15 at 18:44
  • $\begingroup$ I don't understand what you mean. I thought you were in the circle trying to escape? How can to move tangent to the edge from inside? $\endgroup$ – Mark N Apr 24 '15 at 18:44
  • $\begingroup$ @JoeZ. Are you referring to small chords or just making a circle with slightly smaller radius? As Mark N said, tangent doesn't seem to make much sense. $\endgroup$ – Mark Balhoff Apr 24 '15 at 18:46
  • 1
    $\begingroup$ Can you prove that you can always go close enough to the shore so that only one dot remains? What if two or more smugglers tried to always be "in the picture"? $\endgroup$ – JS1 Apr 25 '15 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.