8
$\begingroup$

The cop tries to catch the robber. They both move on the plane and they alternate turns. The robber moves in any direction to a new point at distance exactly 2. The cop moves in any direction any distance at most 1. To give the cop a chance to catch the robber both of them are confined to a disk of diameter d >= 2 (boundary included). There is complete information, so cop and robber see each other at all times.

In the beginning, the cop chooses a position inside the disk. Then the robber chooses a position (taking into account where the cop is). Then the cop makes his move. Then the robber. And so on.

For which values of d can the cop catch the robber in a finite number of turns and how? For which values of d can the robber evade the cop indefinitely and how?

Improve this question
$\endgroup$
2
  • $\begingroup$ Must the robber move? (i.e. are they permitted to "pass", and remain stationary, on their turn?) $\endgroup$
    – Chronocidal
    Commented Aug 17 at 23:47
  • $\begingroup$ @Chronocidal Yes, the robber has to move. $\endgroup$
    – quarague
    Commented Aug 17 at 23:48

3 Answers 3

Reset to default
8
$\begingroup$

The cop wins up to and including diameter

$4/\sqrt 3$

which is the diameter of the circumcircle of a

regular triangle with side length 2.

If the diameter is larger the robber wins by

moving along the boundary of the circle. They will always have two sides to move to and the destination points will be too far apart for the cop to control them both. Because because of the choice of diameter the inscribed isosceles triangle with two sides of length 2 has third side longer than 2.

Conversely, if the diameter is equal or smaller

then all the robber's legal destinations lie on a circular arc with radius 2 such that its endpoints are less than 2 apart and their midpoint is cop reachable from the centre of the disc.

A recipe for the cop would be to start right in the

centre of the disc and after the robber is placed move away from the robber to the midpoint of the perpendicular chord of length 2. At the threshold this point coincides with the midpoint of the endpoints of the reachable arc and the cop will be just fast enough to reach either of them. Also, the disc with radius 1 around this point will fully cover a circular sector of the large disc of 120° or more.

Improve this answer
$\endgroup$
3
  • $\begingroup$ OK, the robber will always have a way out with that diameter. But is it minimal? If the diameter is smaller, will the cop always be able to control the smaller arc? $\endgroup$
    – Florian F
    Commented Aug 17 at 22:08
  • 1
    $\begingroup$ @FlorianF I've expanded the relevant section. Hope it's clearer now. $\endgroup$
    – Albert.Lang
    Commented Aug 17 at 23:04
  • $\begingroup$ Yes, now it is complete. $\endgroup$
    – Florian F
    Commented Aug 18 at 3:12
1
$\begingroup$

The cop can always catch the robber if $d=2$.

If two of the robber's possible destination points that are the farthest apart have a distance of more than 2, he can always evade because the cop can never cover both, meaning $d>4*sqrt(3)/3$ if so:

any larger circle prevents the cop from ever succeeding

If $d<=4*sqrt(3)/3$, the cop just goes to the center. No matter which point the robber picks initially, the cop can control the area by moving from $C_1$ to $C_2$:

C1 = the cop's starting point, R1 = the robbers, C2 = the cop's destination

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is correct but identical to the already accepted solution, it only adds some plots. $\endgroup$
    – quarague
    Commented Aug 19 at 13:48
-1
$\begingroup$

The answer is invalid because I read the question wrong:

While I saw that the cop can move at most 1, I didn't see that robber can move exactly 2.

For which values of d can the cop catch the robber in a finite number of turns and how?

d=2, since the cop can choose the center of the disk to start.

For which values of d can the robber evade the cop indefinitely and how?

d>2

Define

the cop to threaten the robber if the cop moves to distance at most 1 from the robber.

Consider the robber's move after

being threatened. Let D be the bounding disk. Let C be a circle of radius 1 around the cop. Let R be the position of the robber. To escape, the robber needs to find a point P on C such that 1) the distance from R to P is less than 2 and 2) P is neither outside D nor on the boundary of D.

But (1) is satisfied for all points on C except for the case of R being on C. Let S be the set of points satisfying (1), so S is either all of C or all but one point on C.

Since d>2, not all of S can violate (2).

Therefore there exists such a P, so the robber can move just beyond P and evade the cop.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ The cop can utilise rot13(mhtmjnat) though. For example, with d=2.1, all possible places the (unthreatened) robber can (and must) move to are easily reached by a well placed cop. $\endgroup$
    – Bass
    Commented Aug 17 at 19:35
  • 1
    $\begingroup$ This doesn't quite work. In a disk with radius only a little bigger tha 2 a clever cop can estimate where the robber will be after the robbers move and move in that direction instead of towards to the robber. $\endgroup$
    – quarague
    Commented Aug 17 at 23:47
  • 1
    $\begingroup$ Alright, I read the question incorrectly. While I saw that the cop can move at most 1, I didn't see that robber must move exactly 2. $\endgroup$
    – Benjamin Wang
    Commented Aug 18 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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