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
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.
No comments:
Post a Comment