10
$\begingroup$

Last Space Police question...

Sly Cooper has landed on a deserted planet with 2 policemen. He is moving around the planet, painting a line along his path, claiming any land which is surrounded by paint (the smaller area of the two resulting parts). The policemen are trying to restrict the land Sly Cooper claims as much as possible. If they encounter him, they arrest him and take him away. Can you prove that the policemen have a strategy, which prevents Sly Cooper from claiming more than 25% of the surface of the planet?

Remark: We assume that Sly Cooper and the policemen are moving with the same speed, take decisions in real time and are fully aware of everybody's locations.

P.S. Don't care much about reputation points, so decided to spread some around...

Hint 1:

To get some institution about the problem, try to prove that one policeman alone is enough to restrict the area to 50%. Even though identical strategy may not work for the case of two policemen, it still may give some good ideas.

HINT 2:

The solution (at least mine) does not require considering different cases. It is just a universal strategy, working no matter what the initial locations are.

$\endgroup$
  • 1
    $\begingroup$ how does Sly Cooper move? Does he always move in a direction furthest away from the police? or just general evasion? what defines an encounter? $\endgroup$ – dfperry Jul 17 '15 at 16:07
  • 3
    $\begingroup$ 1 is very obvious. Even with 0 policemen, by definition he takes the smaller portion and is thus always less than or equal to 50% of the surface $\endgroup$ – qwertylpc Jul 17 '15 at 16:09
  • 2
    $\begingroup$ General evasion. You can assume that SC and the SP are points, so encounter means that the points coincide. SC can surround several pieces of land with paint, so even though each of theirs' surfaces is less than 50%, their total surface can be more than that. $\endgroup$ – Puzzle Prime Jul 17 '15 at 16:10
  • 1
    $\begingroup$ Removed the 1 policeman part, it was already proved by @Javier in the previous question, so no need to repeat it. $\endgroup$ – Puzzle Prime Jul 17 '15 at 16:16
  • 3
    $\begingroup$ can he sneak silently behind them, then silently do a triangle-square combo on them? $\endgroup$ – Nyk 232 Jul 17 '15 at 19:47
6
+50
$\begingroup$

Assume the police are at points P1 and P2 and Sly Cooper are at point SC. Draw a circle through the three starting points. This circle will lie on the sphere. Draw the three lines that pass through each point and is perpendicular to the circle. The lines will intersect at two points: call them the poles. Call all lines parallel to the circle horizontal, and all lines that go from pole to pole vertical.

SC is always between the lines passing through P1 and P2.

The police need to make sure that SC stays between the lines passing through P1 and P2 while narrowing down the distance between the two lines. The strategy goes as follows:

  1. If SC moves along his line (moves vertically), the policemen move along their respective lines the same distance.

Movement 1

  1. If SC does not move along his line (moves horizontally partially), the policeman he is moving away from will move in exactly the same way and the policeman he is moving towards will move in the mirror image.

Movement 2

Based on this strategy, the police will always be on the same horizontal line as SC and will reduce the possible horizontal movement by one unit for each horizontal unit SC moves.

To claim the largest amount of land, SC must keep his horizontal movement to a minimum.

The worst case would be when the police are right next to each other and are on the diametric opposite of SC on the original circle.

  1. SC moves up and down to draw his vertical line. Then he moves to a pole1.

Movement

  1. He walks a quarter of the way across the planet. At this time, P1 is half of the planet behind of him, and P2 is right in front of him.

Movement

  1. SC moves to the other pole1.

Movement

  1. He then walks back to his starting point1. At this time, P1 is right in front of him and P2 is right behind him, so he cannot claim any more land.

So in the worst case, SC claims a quarter of the planet.


1 Well, an insignificant distance from it. If he moves exactly onto that spot, the police would catch him.

$\endgroup$
  • $\begingroup$ That's the strategy! Will give you the bounty right away:) If you can, explain a bit more rigorously why SC can't claim more than 25% though. If the two policemen are just close to each other on the initial circle, it is still 25%. The classic puzzle with the two cars and the fly between them may help. $\endgroup$ – Puzzle Prime Jul 22 '15 at 14:35
  • $\begingroup$ As long as the two policemen are close to each other and are on the diametrically opposite side of the original circle, the scenario I presented would work. It doesn't matter which horizontal line they start from. So I'm not sure what you want me to do? $\endgroup$ – mmking Jul 22 '15 at 14:40
  • $\begingroup$ I meant that they can start not at the diametrically opposite point on the initial circle (just close to each other) and the final area claimed will be still 25%. $\endgroup$ – Puzzle Prime Jul 22 '15 at 14:47
  • $\begingroup$ However much SC moves horizontally, the horizontal gap between the policemen narrows by twice as much. The gap starts at 360 degrees and SC is caught if it reaches 0 degrees, so SC can move at most 180 degrees horizontally. Since SC must return to the starting position, every horizontal change must be made in both directions, so SC can only cover 90 degrees (one quarter) of the sphere. $\endgroup$ – f'' Jul 22 '15 at 14:48
  • $\begingroup$ Yeah, that's pretty much what I wanted to add:) $\endgroup$ – Puzzle Prime Jul 22 '15 at 14:52
0
$\begingroup$

Lets consider the initial conditions: Anything. As such we need to account for all possible relative orientations. The likely limiting case would be both cops are on the opposite pole from master cooper. As such they are $r\pi$ away from him. To win the sly fellow needs to acquire $\pi r^2 area$ the smallest such area would be a circle of radius r. Unfortunately, we are on a sphere so non-euclidean geometry applies... drats. This path would take walking $2\pi r$ distance to create with an initial $r$ to get out to the circle (or maybe just starting a circle from the pole). (so maybe the actual worst case is they are both opposite the pole cooper is $r$ distance from. If he goes for the simple circle (which by the way circle is most efficient perimeter to area ratio) they could meet him when he is a little less than half way around. ($(\pi -1)r$ around precisely for the r away from pole initial condition). So this doesn't seem like Sly's optimal strategy as he is less than half way to having his area.
This was just a thought experiment hope it helps someone out, I think I will update in the future but I imagine it will come down to circles and possibly angular velocity.

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