18
$\begingroup$

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.

Case n=4
(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.

$\endgroup$
  • 2
    $\begingroup$ Given the recent meta post about too hard puzzles and the many-eyes effect, I took out the circular version for now. No worries, circle fans: I'll post that once people solve this square version. $\endgroup$ – Lopsy Apr 24 '15 at 10:18
  • $\begingroup$ Do the ships keep moving? How close to the mutineer do the ships need to be to starve her out? Can you clarify the victory condition for the ships, please? $\endgroup$ – Ian MacDonald Apr 24 '15 at 11:25
  • 1
    $\begingroup$ I really like this puzzle, which is why I up-voted it. But a couple things: 1. The puzzle requires exact calculations, but a ship cannot really sail right on the edge of where the land meets the water, and technically that line is constantly moving with waves and the tide, so, it added some ambiguity for me. 2. an initial starting position of the mutineer seems needed (such as, she is in the center of the island) $\endgroup$ – JLee Apr 24 '15 at 18:31
  • 1
    $\begingroup$ In addition to animals, there is one with drones. $\endgroup$ – Mike Earnest Apr 24 '15 at 20:52
  • 1
    $\begingroup$ @smci Sure, I'll totally accept that this is a variant. I was only objecting to "it's just a variant." That phrasing sounded kinda condescending. Probably a result of text not being able to translate tone of voice. $\endgroup$ – Lopsy Apr 24 '15 at 22:05
4
$\begingroup$

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.
$\endgroup$
7
$\begingroup$

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".

$\endgroup$
3
$\begingroup$

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.

enter image description here

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.

enter image description here

$\endgroup$
  • $\begingroup$ Actually, this is conclusion is not NECESSARILY correct, since the diagonal moves mean the mutineer is moving faster, but I suspect that the middle escape path (uses just 1 diagonal move) would still be possible...Checking into that now. $\endgroup$ – JLee Apr 24 '15 at 13:12
  • 1
    $\begingroup$ If you count diagonals as 1.5 instead of 1, you get a pretty clean approximation of diagonal movement. $\endgroup$ – Bobson Apr 24 '15 at 13:14
  • $\begingroup$ @Bobson A diagonal is technically sqrt 2, but I just realized that the mutineer could make a bee-line for that point on the coast which is the middle Escape in the picture, and she could never be stopped, so, 3 is not enough. I will post a second illustration for this. $\endgroup$ – JLee Apr 24 '15 at 13:16
  • 1
    $\begingroup$ @leoll2 Good point, but even if they were moved 2 squares over, they still couldn't cover all of the red hole. You agree? $\endgroup$ – JLee Apr 24 '15 at 13:30
  • 1
    $\begingroup$ @leoll2 You may want to keep it. I've been wrong many times before! But, I just realized, that even if the ships hug the coastline to the point where they are in 1 inch of water, they still couldn't catch her. $\endgroup$ – JLee Apr 24 '15 at 13:40
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your first part seems correct, but I think the issue in your second part is that ships have an option to Move in 2 directions, but they can't Cover 2 directions. (As shown by JLee, 3 ships isn't enough) $\endgroup$ – Mark N Apr 24 '15 at 14:49
  • $\begingroup$ About the circular version, I'll post that later today since people seem to be catching on to this one. All I can say is... be very careful >:) $\endgroup$ – Lopsy Apr 24 '15 at 16:19
  • $\begingroup$ Yes, you're correct that none of my pics were perfectly accurate in where the ships were placed, but that is reflected in the comments below my "answer" and even when I adjusted them, I couldn't catch the mutineer, even when the ships could sail in only 1 inch of water, which is what it seems everyone is assuming anyway. $\endgroup$ – JLee Apr 24 '15 at 18:24
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ WLOG might as well assume the square has unit length. $\endgroup$ – smci Apr 25 '15 at 2:43
0
$\begingroup$

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.

$\endgroup$

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.