Pursuit Problem: Mutineer trapped on an island

Question

You are a pirate. One of your crew ran off in the night, swam to your secret island, and dug up your life's treasure. You need to capture her.

You may deploy $n$ pirate ships to patrol the boundary of the island.

(pictured: $n=4$)

Each pirate ship moves exactly as fast as the mutineer. If the mutineer takes even a single safe step into the ocean, then she will escape using her stolen SCUBA kit. Your goal is to capture the criminal scum at the border, or starve her out on the island forever.

How many pirate ships do you need to deploy, if the island is shaped like a square?

The mutineer and pirate ships are all points of zero radius. The mutineer starts in the center of the island, and you may start your ships wherever you want. 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.

Answer 1

This proves lower bound of four ships. Considering that ships move in the ocean and mutineer walks in island. Also, as per victory condition mutineer cannot be caught in ocean. (This is dicey part, since it is said safe step in ocean, but in subsequent comment it was clarified as to mutineer being adjacent to ship.)

Four ship solution is given by @Gully.

Consider a 3x3 island with mutineer at center. Let x and y series for island range from 1
to 3. Then mutineer initially is at (2, 2).

I am proving three ships wouldn't be sufficient.

Consider this diagram:

  _ A_ _
 |      |
B|      | C
 |      |
  _ D_ _

Case I:  None of ships are at corner, i.e. (x, y) for all ships range from (1, 3).
    In this case, at least one border (A-D) would be unguarded, and mutineer can simply
    go through that border.

Case II: One ship is at corner i.e. they can have value of (0, 0) (0, 3), (3, 0) or (3, 3)
    To guard all borders, two ships would guard adjacent border with third ship on
    diagonal opposite. For example, A, B and (3, 3).
    Again, Mutineer can go through either C and D middle strip and escape. 

Cases involving more than one ship at a border are easily explained in the same way.

Answer 2

For the square island, you need

four ships. Let us assume the island has x and y coordinates, all between 0 and 1. Two ships are patrolling the x=0 and x=1 coast. Tell them to ignore the x coordinate of the mutineer's position and just keep up with the y coordinate. The same (with x and y swapped) applies to the other two ships.

Not sure if I can provide an escape strategy for one less ship patrolling. Should be something like "approach one corner, lure the ships towards it, and then diagonally cross the island".

Answer 3

This is not an answer.

No need to up-vote or down-vote. It is just a counter-example to the 3-ships idea.

I think it has to be at least 4. Check out the following pic.

UPDATE: Even more accurate is this approximation. Any straight path through the red area is an escape! The reflection of these red areas (up and to the left) works just the same.

Answer 4

I actually think the circular version may be easier. In theory, the mutineer can never be closer to any point on the shore than any boat. In the circular example, assuming he starts in the center, the distance to the shore is r. The perimeter of the island is 2*r*pi. each ship covers 2r of the perimeter (since they can go either direction around the island as fast as the mutineer moves. Presuming no loss in time for turning around.) As such, you would need pi ships, or since we can only work with whole ships, 4.

For the square, the shortest distance to an edge is l/2, and the longest (to a corner) is (lsqrt(2)) / 2. Dealing with the shortest case scenario again, you have to start with a ship within l/2 of each side. This could be accomplished with 2 ships, just to cover the edges, but this omits the other two corners being covered. For the corners, you need to have a ship within (lsqrt(2)) / 2 of each corner. Double this as each ship can cover 2 different directions. We're left with 4l / ((l*sqrt(2)) = 4/sqrt(2) = 2.82. Again, dealing with whole ships, you'd need 3. This should be enough to fully cover the perimeter.

Edit: (Update after comment w/regard to JLee's answer) JLee's distribution is pretty skewed, the two in the lower left are much closer together than they need to be, leaving the right and top side open. That said, in rethinking this, in order to cover the midpoint of two sides a ship must be at a corner. You need all 4 midpoints covered, so in the 3 boat scenario at least one ship must be at a corner. Let's stick with the upper right as JLee illustrated. Anything outside that quadrant the mutineer would outpace him to. In order to cover the other halves of the top and right edge, another ship would have to be right at, or very close to the top left, and lower right corner. This would leave the lower left corner uncovered. Even if the ship on the left, and bottom started l*sqrt(2) from the lower left corner in order to get there in time, the area's JLee highlighted would still be vulnerable. So ultimately even though I don't think the illustration properly represented a best case for 3 ships, I think 3 is still not feasible.

Answer 5

An interesting note: assuming the 4 ships are positioned at the corners, they are just able to reach the target if she travels straight NSEW, with no overlap. However, if the 4 ships are positioned in the middle of each side, they have overlapping coverage areas at the corners. Unfortunately, this doesn't help. Assume a 20x20 square, with the mutineer at the center. She can leave the island by walking 10 steps NSEW. The ships can also travel 10 steps in that time. This means that the only way for a ship to cover more than one middle of a side is to be positioned at a corner, in which case ships at adjacent corners are needed to prevent gaps in coverage.

Another way to look at it: assuming a 20x20 square, and a ship positioned at the middle of the North side. It covers the North 2.5 units of the East and West sides. (It takes the target 12.5 steps to reach this point, and the ship can reach it in 12.5 steps.) This is the maximum coverage a single ship can provide. The West and East ships can therefore be positioned 12.5+2.5=15 units from the North to prevent any overlap. However, at this point, the mutineer can travel straight South, reaching the ocean in 10 steps, while the ships will take 15 steps to reach her.

Another way to position ships (again, on a 20x20 island) would be to place the first ship on the North coast, 13.45 units from the NW corner. Place the 2nd on the West coast, 13.45 units from the NW corner. At this point, there's no overlap at that point, and there's coverage over 6.95 units of the East and South coasts. However, now we need to cover everything else with one ship, and that's not possible. Placing it on the SE corner will allow the mutineer to escape by traveling E by NE or S by SW, as there's a gap on both sides of the final ship.

Answer 6

Here is a generalization of this (also covers the Fox and Duck puzzle). Formalizing what JLee and user3757614 wrote:

Let the square have unit side, and take coords with x,y between (0,1). Evader E starts at (1/2,1/2) and distance to boundary points is between 1/2 (to midside) and 1/√2 (to corner). Specifically there are four escape paths of length 1/2.

Consider the perimeter. More specifically, since the n pursuers (P's) and evader (E) move at the same speeds (although the P are constrained to move orthogonally), then the generalized condition for trapping would be that the (straight-line distance from E to the nearest point X on boundary) >= (orthogonal distance along perimeter from nearest P to X)

Can we guarantee escape for n = 3?

WLOG say E goes towards the SW corner.

Whenever E is in one of the four quadrants, at some general point (x,y), this commits two of the pursuers to shadow it on each of the closest sides: say P1 (x,0) and P2 (0,y). Letting E(x,y) go sufficiently close to the corner, we can essentially force P1 and P2 onto nearly the same point.

This leaves P3 to cover all the remaining perimeter of length 2. P3 can't stay at the opposite corner; E plays the phase-lag trick by moving in circles of expanding radius so that E develops a phase-lag wrt P3.

Now applying the Pigeonhole Principle, we guaranteed there exists a set of escape points {X} on the boundary which are straight-line closer to E than P3.

I'll try to make this cleaner; taking polar coordinates wrt O(0.5,0.5) might do it.