9
$\begingroup$

Let $C\subset \mathbb{R}^2$ be a smooth, simple closed curve. The thief is inside $C$. Before he starts to move, the police bureau of the $\mathbb{R}^2$ world can freely place countably infinite officers on $C$. We know that

  • The thief and the officers move simultaneously and continuously. Maximum speed is $1$ for everyone.
  • The officers are restricted to move on $C$. They can pass right through each other without collision.
  • The thief is caught if his coordinates coincide with those of an officer.

There're 3 possibilities:

  1. The thief always has a plan to get out of $C$.
  2. The officers always have a plan to prevent the thief from getting out.
  3. It depends on the shape of $C$.

Which one is true?


Response to comments:

  1. If $m(t)$ is a path of the thief, continuous movement means $\vert m(t)-m(s)\vert \leq \vert t-s\vert, \forall t,s$. In particular, we do not require the path to be differentiable. Similarly for an officer path $l(t)$.
  2. Let $Q(t)\subset C$ be the set of officers at time $t$. The thief escapes if $\ \exists_t\,m(t)\,\in\, C\setminus Q(t)$.
  3. The thief and the officers have perfect information about everybody's current position and move according to that information. For example, officer 1 may adopt a strategy like "if $\vert m_x-l_x\vert\gt 0$, move at maximum speed in the direction that decreases it, otherwise stay still".
$\endgroup$
17
  • 2
    $\begingroup$ “They move with equal speed”: what is exactly the regularity of their motion? $\endgroup$ Commented Oct 5, 2021 at 16:49
  • 1
    $\begingroup$ @BD107 No, because the police bureau can place the officers wherever they wish. If the thief could escape no matter the officer placements from some point $p$, they can escape from any point by first heading to $p$. $\endgroup$
    – dhy
    Commented Oct 5, 2021 at 17:27
  • 1
    $\begingroup$ What knowledge do the thief and officers have of the other's position? $\endgroup$ Commented Oct 5, 2021 at 18:08
  • 2
    $\begingroup$ I suppose both thief and police may adjust their movements, depending on the current configuration. But this seems hard to formalize. It would perhaps work better in a discrete model. $\endgroup$ Commented Oct 5, 2021 at 18:42
  • 2
    $\begingroup$ What about 1 cop (for short) trying to catch the thief crossing a segment? If the cop moves on the segment at top speed towards the thief (provided the thief starts far enough and the cop's reaction time is 0) then they should meet. Likewise a dense set of cops on a convex curve: if they run towards the thief only when the latter is much closer to them than, say, the minimum radius of curvature, while remaining dense all the time. On a non convex curve, the thief may try to trap them in a cul de sac, but that should be thwarted by the cops remaining dense always. So my guess is 2. $\endgroup$ Commented Oct 5, 2021 at 20:55

2 Answers 2

7
$\begingroup$

Claim. The thief $T$ can escape if $C$ is a circle, with a simple strategy of dribbling left and right each policeman at a time in such a way that he is left out of reach of the thief no matter what the future dribbles will be.

Proof. The key insight is due to Pietro Majer: the thief can approach $C$ in such a way that its shadow $S$ (closest point) on $C$ always moves at speed faster than $1$.

Assume $C$ has radius $1$ and pick a number $r$ once and for all, with $1/2<r<1$.

At any time there are exactly two circles $C_1$, $C_2$ of radius $r$, tangent to $C$ and contaning $T$. The strategy of the the thief is to always run at speed $1$, alternating between these two ways:

$-$ either move right on $C_1$ towards $A$ (dragging $C_2$ and $B$ along)

$-$ or move left on $C_2$ towards $B$ (dragging $C_1$ and $A$ along).

circle

No matter how $T$ zigzags left and right, the symmetry between $C_1$ and $C_2$ with respect to $T$ guarantees that the path followed by $T$ has the same total length $\overset{\frown}{TA}=\overset{\frown}{TB}$. Therefore $T$ will land on $C$ in finite time.

As for the shadow $S$, $r>1/2$ implies that it always moves at speed $>1$, i.e. the (infinitesimal) arc length inequality $\delta_1<\delta_2$ always holds (see figure). This is a tedious but elementary trigonometric inequality, better left to the reader.

Before detailing how the thief's zigzags are decided, we need to notice that any policeman to the right of $A$, or to the left of $B$, by strictly more than $\overset{\frown}{SA}$, is inactive, in other words he can never catch $T$, even if $T$ runs towards him all the way to $C$.

Finally, enumerate all the policemen $P_1, P_2, P_3 \dots$

Take the first active policeman on the list, say $P_{i_1}$. If $P_{i_1}$ is to the left of $S$ (or on $S$) $T$ chooses to run right towards $A$ at speed $1$. (Similarly if $P$ were to the right, $T$ would choose to run left towards $B$.) Because $S$ moves at speed $>1$ at some point $P_{i_1}$ permanently falls behind $S$ by some amount $\epsilon_1$ (it doesn't matter how small). However $P_{i_1}$ may still be within the active range, so $T$ keeps running towards $A$ until $\overset{\frown}{SA}<\epsilon_1/3$. Since $\overset{\frown}{SB}=\overset{\frown}{SA}$, now $P_{i_1}$ is behind $B$ by strictly more than $\epsilon_1/3$. This renders $P_{i_1}$ permanently inactive!

Similarly, take the next active policeman $P_{i_2}$ on the list. Again $T$ runs in the direction away from him, until $P_{i_2}$ is inactive too. There at most countably many active policemen and one by one they all become inactive, guaranteeing that $T$ lands on a police-free point of $C$.$\quad \blacksquare$

This proof should easily extend to any curve $C$, since $T$ can first move close to a point of positive curvature, where locally the curve can be approximated well by a circle.

$\endgroup$
8
  • $\begingroup$ @ChristianRemling. The definition of "inactive" uses a strict inequality (the word "more"), so for each policeman $P_i$ there a margin of $\epsilon_i$ that can never be closed no matter what $T$ does. Since $T$ (and $S$) clearly converge, each $P_i$ is at least $\epsilon_i$ away from their limit. Should I edit the answer to make that more clear? $\endgroup$ Commented Oct 9, 2021 at 17:04
  • $\begingroup$ Thanks for clarifying, it's clear to me now. I probably didn't read it carefully enough. But maybe it would help to say explicitly that the structure of the argument is that you approach a point $p$ along a path that is divided into segments, and what we do on the $n$th segment will make sure that $d(P_n,P)\ge \epsilon_n$. $\endgroup$ Commented Oct 9, 2021 at 18:00
  • 1
    $\begingroup$ @ChristianRemling Thank you for the thoughtful feedback. I'll edit the answer. Regarding internal segments, the problem is that their points with the property of the shadows moving faster, form subsegments that don't reach the circle. So one would need some messy pasting of infinitely many different segments and it may no longer be so easy to prove that they add up to an infinite path. The beauty of the 2 tangent circles is that because of the symmetry between left and right, the total length of the path is unaffected by the zigzagging. $\endgroup$ Commented Oct 9, 2021 at 19:52
  • 1
    $\begingroup$ How different the situation if the curve isn't smooth! For a example a thief at the center of a square enclosure is always caught by 4 cops starting at the centers of the edges, but can escape 4 cops starting at the corners. $\endgroup$ Commented Oct 10, 2021 at 4:54
  • 1
    $\begingroup$ @Eric Yes and no, respectively. It seems that a stretch of the curve with negative or $0$ curvature (plus finitely many singularities) can be guarded by a finite number of policemen, while any stretch with positive curvature (bounded below) cannot be guarded by even a dense, countable set. The concave square would be even easier to guard than the regular flat square. $\endgroup$ Commented Oct 10, 2021 at 10:51
0
$\begingroup$

The cops should always win. Here is a sketch of a proof.

  1. One cop (for short) trying to catch the thief crossing a segment: the cop can run on the segment at top speed towards the thief (provided the thief starts far enough and the cop's reaction time is 0). Clearly they will meet.

  2. Likewise a dense set of cops on a convex curve $C$: they can run towards the thief only when the latter is "close" to them, while keeping dense all the time. To make this precise: let $r$ be the minimum radius of curvature, which exists because $C$ is smooth and compact; whenever the thief is closer to $C$ than $r$ there is a unique point $P\in C$ to which the thief is closest, with distance $d_P<r$; if $d\ge d_P$ is the distance of a cop from the thief, that cop should run towards $P$ at speed $\text{max}(1-d/r,0)$. This strategy is continuous on $C$ and guarantees that the cops will stay a dense set, and also approaches the strategy in 1) as the thief gets closer to $C$, guaranteeing an eventual catch.

  3. This works on a non convex curve too. On a curve with a singularity the thief can try to split the cops and trap them in a cul de sac, but on a smooth curve that is thwarted by the cops remaining dense always.

Update. See comments for where this argument goes wrong.

$\endgroup$
17
  • 4
    $\begingroup$ But does this guarantee that one cop catches the thief? The shadow on $P$ of the thief on $C$ has possibly velocity $>1$, while each cop running after it has speed $\le1$. Can’t the thief move so smartly that he reaches $C$ at time $T$, but and at time $T-1/n$ The point $P$ has dribbled or escaped eventually Cop_n ? $\endgroup$ Commented Oct 6, 2021 at 7:34
  • 2
    $\begingroup$ Suppose the police bureau can freely place countably infinite officers on the x-axis, but each officer's speed is at most $1-\epsilon$. Can the thief cross over the line from one side to the other? I think he can, but I can't prove. $\endgroup$
    – Eric
    Commented Oct 6, 2021 at 7:51
  • 1
    $\begingroup$ Maybe one can modify your strategy this way. Two cops start moving as soon the thief is has distance $r$ to the curve $C$, say $C$ is parametrised in arc length, and they are in positions $A<P<B$ with $B-A \approx r$. Then they take care not to be passed by $P$, so that $A<P<B$ holds for all times (this means running after P when he moves away, and moving away when he gets closer). Even if $P$ can move faster, I think $A$ and $B$ can make their distance vanish in finite time. (So at the end the principle should be, of course, the 2 policemen’s theorem) $\endgroup$ Commented Oct 6, 2021 at 8:09
  • 1
    $\begingroup$ Ok, I see that there are more subtleties than I thought. But my feeling is that quantifiers should be better specified in the problem statement. One possibility is: everyone has perfect and instantaneous information about the others. The officers place themselves after knowing the starting point of the thief and then they must follow a countable list of strategies decided in advance and such that their motion will only depend on current position and velocity of the thief; on the other hand, the thief knows in advance all the countable strategies that officers adopt. Is this the setting? $\endgroup$ Commented Oct 6, 2021 at 13:07
  • 1
    $\begingroup$ @YaakovBaruch Please can you specify whether your strategy 2 falls within my proposed setting of the problem? As for 1, I'm a bit lost, as I don't really understand what you mean by "random point which has probability 1 of being cop-free". Even if the thief moves randomly (whatever it means), the cops are not, since they will know exactly where the thief is, so how this exactly applies? $\endgroup$ Commented Oct 7, 2021 at 7:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .