25
$\begingroup$

The cop and the thief, both mathematical points, live in an open interval $(0,1)\subset \mathbb{R}$. That is, their universe is a line segment of length 1 without the 2 endpoints. We know that both move simultaneously and continuously at a maximum speed of 1. Both react instantaneously according to their respective positions. At time 0, the thief and the cop are at positions 1/3 and 2/3 respectively. The cop catches the thief if cop position=thief position.

Here's arguments from both sides, can you decide who's right?

Thief: Hmmm, let me see, at time t the cop is at position $C_t$, but I'm always able to keep my position at $\frac{C_t}{2}$, therefore my position never coincide with that of the cop, therefore he can never catch me :)

Cop: That's nonsense! All I need to do is keep moving towards 0 at full speed until my position coincide with the thief's, and this will happen very soon :)

Note that a "strategy" for both cop and thief must be defined as a function of x over time.

$\endgroup$
18
  • 12
    $\begingroup$ Reminds me of Zeno's paradoxes. I find the thief's argument unconvincing but can't quite formalize why. $\endgroup$ Oct 30, 2021 at 4:56
  • 3
    $\begingroup$ Does this puzzle have an answer? $\endgroup$
    – Helena
    Oct 30, 2021 at 22:32
  • 2
    $\begingroup$ @FirstNameLastName If you don't think it's undefined, explain to me exactly what happens at t=2/3? $\endgroup$ Oct 31, 2021 at 20:31
  • 2
    $\begingroup$ @FirstNameLastName "Either party can claim whatever is necessarily not valid at t=2/3" What does that mean? What happens at t=2/3? $\endgroup$ Nov 1, 2021 at 13:13
  • 3
    $\begingroup$ After all this work, I can now say with confidence, "This is not a puzzle. What happens on encountering the edge of the universe is missing vital information." $\endgroup$
    – Joshua
    Nov 2, 2021 at 0:01

12 Answers 12

16
$\begingroup$

Fundamentally, the issue is that

  1. For every fixed cop strategy, there exists a thief strategy that beats it.
  2. For every fixed thief strategy, there exists a cop strategy that beats it.

For an easier picture, this is effectively what the game looks like:

  1. Cop chooses a real number $C\in(0,1)$ (basically $\liminf_{t\in\mathbb{R}^+} C(t)$ of their position)
  2. Thief chooses a real number $T\in(0,1)$
  3. Cop wins if $C\leq T$

Who wins? Neither side has a winning strategy. Games without a value are not controversial, and can occur whenever players have infinite strategy spaces.

Here, this is because the space is not complete, so neither can pick "$0$", the limiting strategy, which isn't a strategy at all. Having a limit which does not exist in the original space is not controversial. "What's the smallest strictly positive real number?" has no answer at all.

Both sides may, of course, pick a strategy that goes to $0$ in the limit $t\rightarrow\infty$. This doesn't change the issue, of course: the players duel on how fast they approach 0, and any fixed choice by either one can always be beat by the other.

When considered as one side having to move first, that player loses.


Previous longer answer

Question is undefined for another reason: this whole "react instantaneously to the other" condition causes mutual self-reference, and we all know just how many problems come from this.

The space is not complete, and therefore, so is the space of strategies. It shouldn't be surprising that a definable strategy which definitively wins the game simply does not exist. The proof ends up as:

  1. For every fixed cop strategy, there exists a thief strategy that beats it.
  2. For every fixed thief strategy, there exists a cop strategy that beats it.

Therefore, strategy mutual induction goes nuclear, that is, the limit does not exist and no unbeatable strategy exists for either side. The answer critically depends on who has to blink first, i.e. determine their strategy at time $t=2/3$ first. They lose.


Unimportant complications: If both are allowed to basically "update" their strategy upon seeing the other's current choice, they both never end, in Zeno's paradox. Therefore this process generates no answer at all, i.e. the problem is undefined.

Loosening this a little, suppose $C(t)$ is the cop's (possibly to-be-determined) strategy, and $T(t)$ is the thief's. Letting them "react" presumably means that $C(t+\epsilon)$ can depend on $T(t)$ and vice versa.

Essentially, once the cop sees the thief at time $t$, they decide their strategy for the next $\epsilon$ time, without seeing the thief between $t$ and $t+\epsilon$. Or, the thief has to decide first for time $(t,t+\epsilon]$ without seeing the cop.

At some point, one of the sides has to blink and decide their position at $t=2/3$, if $\epsilon$ cannot be arbitrarily small. They are forced to turn back (or stop moving) and lose.

The other choice, that both sides may end up publishing arbitrarily small further strategy choices, leads to Zeno's paradox in that you can't validly obtain any result that extends to or past $t=2/3$, as both keep playing chicken and nobody states their position at $t=2/3$ exactly.

Proof the cop wins if the thief is the one forced to hit $t=2/3$:

  1. Cop keeps moving at full speed before $t=2/3$.
  2. At some finite step $t_n<2/3$, the thief has to choose through $T(t_{n+1})$ for $t_{n+1}\geq2/3$.
  3. They can't pick $T(t)$ to keep moving forwards, that is, $$\liminf_{t\rightarrow t_{n+1}}T(t)=L>0$$
  4. Cop overtakes $L$ and wins.

Proof the thief wins if the cop is the one forced to hit $t=2/3$:

  1. Same as above, cop has to turn back at some point, so $$\liminf_{t\rightarrow t_{n+1}}C(t)=L>0$$
  2. Thief forever stays just in front of the cop, one particular strategy is $T(t)=C(t)/2$.

The above presumes the cop or the thief is the one that is always forced to choose first, at least around time $t=2/3$.

The actual condition is: if the thief is forced to choose first for any strictly positive amount of time at or after $t=2/3$, they lose. The cop arranges things so that in that specific time interval they are stopped by the universe boundaries, again having to turn back at a finite point.

$\endgroup$
8
  • 1
    $\begingroup$ To make the answer stronger: For every pair of current positions $0 < T(t_0) < C(t_0) < 1$, any strategy continuing from that position can be beat by some strategy of the other player. This shows that they don't need knowledge of the other's future actions. $\endgroup$
    – aschepler
    Nov 1, 2021 at 10:52
  • 1
    $\begingroup$ And in the early simplification, we could have $\liminf_{t \in \mathbb{R}^+} C(t) = 0$. Rather than try to rationalize that case separately, we do have $\inf_{t \in [0,2/3]} C(t) > 0$, or on any fixed interval $[0,T]$ where $T \geq \frac{2}{3}$. $\endgroup$
    – aschepler
    Nov 1, 2021 at 10:58
  • 2
    $\begingroup$ Who said the cop or thief have to "choose a real number"? They can both just "move left at full speed". I don't have to choose a real number to start walking. Assuming they have to choose a destination first and letting their movement be constrained by that choice is to inherently assume the absurd conclusion of Zeno's paradox. $\endgroup$ Nov 1, 2021 at 13:54
  • 1
    $\begingroup$ @Shufflepants It can be revised to see that they are not choosing positions, but choosing a continuous function that maps from time [0,inf) to a position (0,1) (that agrees with the past movements, etc etc). You can view it as keep changing function if you like, but the resulting trajectory is still a function at the end. $\endgroup$
    – justhalf
    Nov 2, 2021 at 4:46
  • 1
    $\begingroup$ @justhalf That's not how moving with a constant velocity works. One's "strategy" can just be "move left at speed 1" without any necessity to specify a mapping from t:[0,inf) to d:(0,1). If "move left at speed 1" leads to a discontinuity at t=1/3, then it's up to the OP to decide what happens in that case or to conclude that the cop cannot catch the thief because at t=1/3, the physics stop being well defined. It's just like what happens when something falls into a black hole and hits the singularity. It's perfectly valid to just fall in, but our current model breaks at that point. $\endgroup$ Nov 4, 2021 at 4:58
21
$\begingroup$

It's undefined although a slight tightening up of the question would make it defined.

What the question lacks is a specification of what happens when a player reaches the limit of the universe. To be more specific:

Suppose each player executes their optimum strategy of moving at maximum speed in the negative direction. What exactly happens at $t=1/3$ when the thief reaches the end of the universe1?

Note that you can't avoid the question. $t=1/3$ will happen, typically 1/3 of a time unit after the start. If you try to pretend it won't then you do end up with Zeno's paradox.

The simplest answer is "they are then outside the boundaries of the universe". Nothing wrong with that. It happens on Star Trek most weeks.

Then the question is answerable with a simple change, which is to make the question "Can the cop catch the thief within the boundaries of the universe?" and of course the answer is

No, thanks to the above optimal strategies. They move in the negative direction at the same speed and never intersect. You can also use the strategies described in several other answers, in which the thief moves at half the speed of the cop, and means they arrive at the boundary of the universe at the same time. The answer is still that the cop catches the thief, but cannot do so inside the limits of the universe. Note that with this condition the thief has not need of a 'complex' strategy like moving at half the speed of the cop. The thief can simply move at full speed in the negative direction, exit the universe, and be immune from capture.

If you want any other answer to the question, you need to say what happens at $t=1/3$ in some other way. Specifically what position does the thief occupy at $t=1/3$ if they move at speed -1 for all that time? Do they stop before the edge? If so how far before the edge? In physics terms you have to say what happens "close to" the edge of the universe. Real life "unreachable points" all exist because the behaviour near those points prevents them from being reached, not because they are arbitrarily "forbidden"2.

One of the arguments used elsewhere it "the thief (and/or cop) must slow down before he reaches the edge of the universe". Really? Who says? It's not in the question statement. And if they have to slow down, how long before? What happens if they don't? Is there a cop who comes after them and...oh, wait. Answering those questions would make the question determinate.

To make it more mathematically clear that neither cop nor thief "need to slow down" before $x=0$: for all $x$ where $x>0$ there is an $x_1$ which is less than $x$ but also greater than zero. Therefore at any position $x>0$ both cop and thief can move closer to zero. If they can move closer then they can do it at full speed (it just takes less time to get there than if they do it slowly). Hence neither cop nor thief need to slow down before the end of the universe.

The confusion is that the question uses the word "universe" which we take to mean "everything". If we used a word like "valid range" or "domain", it would be much easier to make the statement that

the cop

cannot

catch the thief within the valid range".

Some comments on other answers Some answers are saying that the problem is undefined because the strategies of the two players depend on them simultaneously reacting to each other, or to each other's predicted moves. This is not the case. The optimal strategy for the cop is to move towards x=0 at full speed. It doesn't matter what the thief does, there is no better strategy for the cop. (The thief can make things easier by choosing a worse strategy, but however much worse the thief plays the cop cannot improve on this strategy). Likewise the thief can avoid capture up until $t=2/3$ by moving at half speed towards $x=0$, no matter what the cop does. If the cop plays worse the thief can delay the "point of uncertainty" (the time they reach the end of the universe) by always moving at $p_t/p_c$ towards zero, where $p_t$ is his own position and $p_c$ is the cop's position. No ability to predict the others moves is necessary, and there is no self-reference. It is specifically stated in the question that both players have the ability to instantaneously act out a strategy based on their own and the opponents position.

Some answers assume that the strategy for each player involves choosing a position that they move to. I don't believe that is the case, and nothing is said in the question that requires it. Also strategies are instantaneous. You only have to choose a strategy at a specific point in time. So a valid strategy might be "always choose to move left at full speed". There is nothing in the question that makes that an invalid strategy. It's true that if you forbid $x=0$ to the players you can't make that choice at $x=0$, but they can make it at every other point. And the players cannot exist at $x=0$, so it's irrelevant what strategy they are allowed to choose there.

If the players were forced to choose a "stop distance", they still reach that at a finite time, and there is nothing to stop them choosing "another" stop point immediately after that. Say the cop chooses to stop at $x=0.1$ and the thief at $x=0.05$. Can the cop not choose then to move to $x-0.01$? And then even closer the next time?

Footnotes

  1. Apart of course from him eating a fine meal at Milliways.
  2. Alternative answers taken from scientific and scifi literature might include the player re-entering the universe at the same point from the other direction, or re-entering it from the other end in the same direction. Although strictly nether of those answer the question of what happens at exactly $t=1/3$.
$\endgroup$
19
  • 2
    $\begingroup$ Good one, although I disagree with it being based on trying to exit the universe; it's based on attempting to define what "reacting to each other" means by $t=2/3$. $\endgroup$
    – obscurans
    Oct 31, 2021 at 3:59
  • 1
    $\begingroup$ I don't think interacting makes much difference. The cop has an optimal strategy to move towards the thief at full speed. The thief has an optimal strategy to move away from the cop at something between full speed and half speed. Neither depends on what the other does. $\endgroup$ Oct 31, 2021 at 16:47
  • 2
    $\begingroup$ Also the problem says "continuously", which has a specific mathematical meaning where the stated or implied codomain or "universe" is part of the meaning. And here "moving at constant speed as long as possible" is not continuous movement. $\endgroup$
    – aschepler
    Nov 1, 2021 at 15:52
  • 2
    $\begingroup$ I guess you might say "defining/selecting a strategy" is strange. Most of us take it to mean a function from time to position with bounded speeds. From that point of view, moving at constant velocity for a long time is just not a possibility, since there is no such function. In a regular unbounded $\mathbb{R}^n$-like universe, any continuous (or continuous almost everywhere) velocity function gives a valid position function $\vec x(t) = \vec x(0) + \int_0^t v(\tau)\, d\tau$. But in the interval universe, that same formula is not integrable.... $\endgroup$
    – aschepler
    Nov 1, 2021 at 16:01
  • 3
    $\begingroup$ I agree that if choosing a strategy requires choosing a point to move to then you might end up with an endless series of steps where the thief manages to stay ahead of the cop. But nothing in the question says you have to choose a destination point. And even if you could, a strategy that continuously chooses a point within the universe and closer to x=0 than you are results in smaller and smaller timesteps, which converge before x=2/3. That infinite sequence of timesteps does not change the fact that the time t=2/3 will in fact arrive, nor settle the question of what happens when it does. $\endgroup$ Nov 1, 2021 at 16:49
11
$\begingroup$

Cleaned up answer:

The problem is not well defined.

To make things concrete, let's say that the cop's strategy is represented as a function c(t), which is dependent on the thief's trajectory w(t), and vice-versa.

The cop's strategy is c(t) = max(2/3-t, w(t)). The thief's strategy is w(t) = c(t)/2.

Now we can observe for the cop's strategy that

c(t) will be continuous if w(t) is continuous, because the maximum of two continuous trajectories is continuous.

We can also observe for the thief's strategy that

w(t) will be continuous if c(t) is continuous, because half of a continuous trajectory is continuous.

But there's a problem:

The only mutually consistent pair of trajectories for those two strategies over the interval [0, 2/3) is c(t)=2/3-t, w(t)=1/3-t/2. Each of these trajectories cannot be extended to continuous trajectories over the interval [0, 2/3].

So what we have discovered is that

The requirements "c(t) is continuous if w(t) is continuous" and "w(t) is continuous if c(t) is continuous" are not sufficient to make c(t) and w(t) actually continuous and well-defined. So the problem is not well-defined as a whole.

Is one player right and one player wrong?

No, I don't think so. I don't think there's a reasonable rule that says that one of these strategies is illegal and the other is legal. They're quite symmetrical. This has revealed that "players react instantaneously to each other" doesn't work well on this sort of universe - a pair of strategies can seem valid, but produce non-well-defined results. As a result, I think the problem itself is not well-defined.


Earlier thoughts

One answer is that

The cop is wrong.

But why is this player's argument wrong?

The cop's answer is wrong because the cop's proposed movement of "Keep moving towards 0 at full speed" is only well-defined on the interval of time $t \in [0, 2/3)$.

On and after time 2/3,

the cop has not yet specified how they will move, but it can't simply be "Move at full speed towards 0", or else the cop will leave their universe at time 2/3, which is not allowed.

That being said, there's a bigger problem.

The cop's movement is required to be continuous. If on the interval of time [0, 2/3), the cop moves at maximum speed towards 0, the cop's movement cannot be continuous over a longer time interval, such as [0, 2/3]. This is impossible because the limit point of the cop's movement over the interval [0, 2/3) is 0, which is not in the universe.

Therefore, we may conclude that

In order for the cop's movement to be continuous, they cannot move towards 0 at maximum rate until they catch the thief. That does not generate a legal trajectory for the cop, under the thief's proposed response.

But does this problem apply both ways?

If the cop takes this "inevitably discontinuous trajectory" of moving towards 0 at maximum rate, then the thief will also take an "inevitably discontinuous trajectory", also moving towards 0 with constant rate. The cop could argue that they aren't moving towards 0 forever, merely until the thief diverges from its trajectory, and the thief is required to diverge from that trajectory to maintain continuity.

In the end I think the problem is

Not well defined, because of the interaction between "continuous movement" and "react instantaneously". In particular, both points can be thought of as moving in a fashion that would react according to a continuous trajectory, given any continuous trajectory of the other point. This is not sufficient to produce continuous trajectories, as we see here. It's not clear how to give a tighter requirement on how a point must react to the other point's movement, which would eliminate this possibility.

One way to try to fix this would be to require that

If one point moves continuously over some interval [0, a), then the other point must react in such a way that guarantees continuity over the interval [0, a].

In this case,

Both proposed reactive trajectories are illegal, so both arguments are wrong. I do not know who actually wins in this case.

$\endgroup$
11
  • 1
    $\begingroup$ Oh 0 is just a marker here. The cop might have said "keeping moving leftward" until he catches the thief. This can easily be made rigorous: formally, let w(t) be the thief's trajectory, then the cop's strategy is c(t)=max(2/3-t, w(t)). $\endgroup$
    – Eric
    Oct 30, 2021 at 10:07
  • 1
    $\begingroup$ Movements are required to be continuous. Where does discontinuity come from? $\endgroup$
    – Eric
    Oct 30, 2021 at 11:02
  • 1
    $\begingroup$ The thief can move at half the speed of any actual cop movement. It doesn't matter that the cop initially has a plan which isn't possible to execute. $\endgroup$
    – aschepler
    Oct 30, 2021 at 14:01
  • 3
    $\begingroup$ @Eric For any thief's trajectory w(t) that is continuous, the cop's strategy c(t)=max(2/3-t, w(t)) will also be continuous. For any cop trajectory c(t) that is continuous, the thief's strategy w(t)=c(t)/2 will also be continuous. But the only mutually consistent pair of trajectories for those two strategies over the interval [0, 2/3) is c(t)=2/3-t, w(t)=1/3-t/2. Each of these trajectories cannot be extended to continuous trajectories over the interval [0, 2/3]. I don't think there's a reasonable rule that says that one of these strategies is illegal and the other is legal. $\endgroup$
    – isaacg
    Oct 30, 2021 at 18:18
  • 1
    $\begingroup$ So the proposed strategies can't both be true over the time interval [0,2/3), and we can't determine which one isn't. I completely agree. I think this basically concludes the problem. $\endgroup$
    – Eric
    Oct 31, 2021 at 3:06
11
$\begingroup$

The thief

is right, basically because

the endpoints are not included.

The problem with one of the two suggested approaches is that

the cop predicts a definite point of convergence, since the thief has a finite amount of space in which to manoeuvre, but what if the predicted convergence is at the endpoint $0$ or beyond? That means it will actually never be reached. The cop cannot continue moving at speed one for time $2/3$ or longer.

The space in which they're moving is sort of like a 1-dimensional hyperbolic space: they can get infinitesimally close to the boundary but they can never actually reach it.

TL;DR: it seems that, on an open line segment, Zeno's paradox is actually true.

$\endgroup$
16
  • 4
    $\begingroup$ Great point, Rand al'Thor, about Zeno's paradox being true in certain circumstances. I've been casually laughing it off for millennia. And nice twist, @Eric, to have the interval open. $\endgroup$
    – humn
    Oct 30, 2021 at 6:28
  • 2
    $\begingroup$ It's true the cop cannot continue moving at speed one for time 2/3 or longer. But it's also true that the thief cannot continue moving at speed 1/2 for time 2/3 or longer. Yet the world doesn't end at time 2/3. Where's the thief at time 2/3? Where is he at time 100? $\endgroup$
    – Eric
    Oct 30, 2021 at 8:02
  • 7
    $\begingroup$ Really? The cop has no reason to slow down before he catches the thief. $\endgroup$
    – Eric
    Oct 30, 2021 at 8:17
  • 4
    $\begingroup$ @SteveV And the cop has no reason to slow down before he catches the thief. $\endgroup$
    – Eric
    Oct 30, 2021 at 8:35
  • 3
    $\begingroup$ It isn't really defined what would happen if the cop tried to move past the edge of the universe. Since there's no minimal position, they can't just run into a wall that would stop their motion there. Normally they would be stopped at some finite distance from the wall because they have size, but here they are just points. If they both die when going off the edge, then the cop could force a mutual death upon them. $\endgroup$
    – nog642
    Oct 30, 2021 at 18:42
6
$\begingroup$

EDIT: I don't know!

The thief can evade the cop.

Let's call the thief's position as a function of time $\Theta(t)$, and the cop's position as a function of time $C(t)$. We know each function is continuous. We don't know if they're differentiable, but based on the maximum speed restriction we can say $|\Theta(b)-\Theta(a)| < b-a$ and $|C(b)-C(a)| < b-a$ for any two times $a<b$.

One important thing to note: The point-people are described as able to react instantly according to their "positions". But because of that same instant reaction, neither can assume any knowledge about how the other will move in the future.

The cop's strategy of "move at full speed until our positions coincide" ($C(t) = \max(\frac{2}{3}-t, \Theta(t))$) is not a valid strategy because it depends on the movement of the thief in the future. The cop can't move left at full speed until an unknown time any more than move left at full speed for a full second.

Also, a thief's strategy of "move at half the speed of the cop" ($\Theta'(t) = C'(t)$) is not valid, since speed is a derivative involving a prediction into the future and is not really based on the cop's current position.

But the thief does still have a valid strategy using only current positions as input: Label the "Zeno points" $Z_n = 2^{-n}: \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \ldots.$ Whenever the thief is between Zeno points, the thief will move left at speed 1 until the next Zeno point. When a thief is at a Zeno point $Z_n$ and the cop is to the right of $Z_{n-1}$, the thief stands still. When the thief is at a Zeno point $Z_n$ and the cop is at or to the left of Zeno point $Z_{n-1}$, the thief moves left at speed 1. That is,

$$ \Theta'(t) = \begin{cases} 0 & \exists n: \Theta(t)=2^{-n} \mathrm{\ and\ } C(t)>2^{1-n} \\ -1 & \mathrm{otherwise} \end{cases} $$

This is a valid strategy only if for every $T \geq 0$, $$\Theta(0) + \int_0^T \Theta'(t)\, dt \in (0,1)$$

(including the requirement that $\Theta'$ is integrable in the first place.)

Given any continuous $C(t): [0, \infty) \to (0,1)$, we can show by induction that when the cop arrives at any Zeno point for the first time, the thief's strategy so far is valid, the thief is currently at the next Zeno point, and the thief has not yet been caught.

The initial thief movement, after integration, is $\Theta(t) = \frac{1}{3} - t$ for $0 \leq t \leq \frac{1}{12}$ to reach $\Theta(t) = Z_2 = \frac{1}{4}$ at time $\frac{1}{12}$. When $t < \frac{1}{12}$, $C(t) > C(0) - \frac{1}{12} = \frac{7}{12} > Z_1$. Since $\Theta(t) < \frac{1}{3} < Z_1$ during this entire time, the thief was not caught during the first $\frac{1}{12}$ second. So if the cop reaches $Z_1$ for the first time (if ever) at time $t_1$, $t_1 > \frac{1}{12}$, the thief is already at $\Theta(t_1) = Z_2$ and has still not been caught.

Now suppose the induction hypothesis that $C(t_n) = Z_n$, and for all $0 \leq t < t_n$ we have $C(t) > Z_n$, and the thief's strategy has produced valid movement up to $\Theta(t_n) = Z_{n+1}$. The thief will now move to the next Zeno point: if $t_n \leq t \leq t_n + 2^{-n-2}$ then $\Theta(t) = Z_{n+1} - (t-t_n)$, ending with $\Theta(t_n + 2^{-n-2}) = Z_{n+2}$. In this same time interval, $C(t) \geq Z_n - (t-t_n) \geq 2^{-n} - 2{-n-2} > 2^{-n-1} = Z_{n+1}$, so the thief is not caught during that time. Then if there is then a time $t_{n+1}$ such that $C(t_{n+1}) = Z_{n+1}$, $t_{n+1} > t_n$ and $|C(t_{n+1})-C(t_n)| \leq t_{n+1}-t_n$ implies $t_{n+1} \geq t_n + Z_n - Z_{n+1} = t_n + 2^{-n-1} > t_n + 2^{-n-2}$, so the thief is already at $\Theta(t_{n+1}) = Z_{n+2}$ and has not been caught before time $t_{n+1}$.

So if the cop visits only a finite number of Zeno points, the thief reaches the first unvisited Zeno point without being caught, moves to the second unvisited Zeno point without being caught, and safely stays there forever. If the cop visits all the Zeno points, the thief can stay "a step ahead" and avoid capture forever.

Supposing there could be a point $t_e$ where $C(t_e) = \Theta(t_e)$ leads to a contradiction: On the closed interval $t \in [0, t_e]$, a continuous function $C$ must attain its minimum: there is at least one time $t_m \leq t_e$ with $C(t) \geq C(t_m)$ whenever $0 \leq t \leq t_e$. Let $Z_n$ be the last Zeno point with $Z_n \geq C(t_m)$. ($n = \lceil - \log_2 C(t_m) \rceil$.) The thief has position $\Theta(t) \leq Z_{n+1}$ whenever $t \geq t_m$. But since $t_e \geq t_m$, this means $\Theta(t_e) \leq Z_{n+1} < C(t_m) \leq C(t_e)$; contradiction.

These Zeno points also hint at an understanding of the problem with the cop's strategy. Claiming "I will certainly catch the thief before time $\frac{2}{3}$" is somewhat like claiming "I can visit all the Zeno points before time $\frac{2}{3}$". But the cop needs to be somewhere at the actual time $t=\frac{2}{3}$, besides the times before that. And a continuous function from closed interval $[0,\frac{2}{3}]$ to a universe $(0,1)$ must attain a minimum within that universe, and so can only visit a finite number of Zeno points. The cop can visit an unlimited number of Zeno points in less than $\frac{2}{3}$ seconds, but can never visit all of them in any duration of time.

$\endgroup$
12
  • 1
    $\begingroup$ Cop step1: if c(t)≠w(t), move at full speed to the point w(t)/2. Cop step2: Repeat step1. Where's your thief at time 2/3? $\endgroup$
    – Eric
    Oct 31, 2021 at 2:31
  • 1
    $\begingroup$ @Eric Where is the cop at t = 2/3? $\endgroup$
    – Alex Jones
    Oct 31, 2021 at 4:20
  • 1
    $\begingroup$ This argument proves that "the cop can't win" (by catching the thief under the stated conditions), which is true. The thing is, a symmetric argument proves that "the thief can't win" (by evading forever under the conditions). $\endgroup$
    – obscurans
    Oct 31, 2021 at 22:11
  • 1
    $\begingroup$ If $T$ is any positive real number and $C : [0, T] \to (0,1)$ is any continuous function, then the algorithm I gave describes a continuous function $\Theta : [0,T] \to (0,1)$. Your cop algorithm never describes a continuous function $C : [0, T] \to (0,1)$ if $T \geq \frac{2}{3}$, no matter what $\Theta(t)$ is. So I'd say the thief algorithm is an actual algorithm, and the cop's isn't a complete actionable algorithm. $\endgroup$
    – aschepler
    Nov 1, 2021 at 0:06
  • 1
    $\begingroup$ @DJClayworth Except I can't accept simply "move to the left at full/half speed" as even being a strategy, since it doesn't result in a description of position as a function of time. $\endgroup$
    – aschepler
    Nov 1, 2021 at 22:47
6
$\begingroup$

The number line’s origin’s being excluded means that . . .

. . . the thief will elude the cop.

It also means that the maximum speeds of both cop and thief . . .

. . . are immaterial after almost the first 1/3 unit of time when the thief can be infinitesimally close to the origin. Upon that, the thief can relax in place until the cop reaches twice as far from the origin. After that, the thief may indeed forever attain positions halfway between the origin and the cop by merely approaching the origin at half of whatever speed the cop assumes.

$\endgroup$
5
  • 1
    $\begingroup$ Ho humn, fancy meeting you here :-) $\endgroup$ Oct 30, 2021 at 6:08
  • 3
    $\begingroup$ No, the thief cannot remain forever at halfway between the cop and the origin. They can remain at halfway between the cop and the origin for whatever position the cop occupies, but that isn't forever. $\endgroup$ Oct 31, 2021 at 21:04
  • $\begingroup$ Dear @DJClayworth, my solution pleads a diagram. As mentioned in other solutions, forever is the only option as neither cop nor thief can maintain full speed to their destinations. $\endgroup$
    – humn
    Nov 1, 2021 at 13:54
  • 1
    $\begingroup$ @humn No. If you say the thief occupies a position halfway between the end of the universe and the cop "forever", then please tell me where that position is at t=2/3? t=2/3 is a valid time that will happen. You must be able to define their positions at that time, or you cannot say they will be like that "forever". $\endgroup$ Nov 1, 2021 at 14:01
  • $\begingroup$ @DJClayworth , i seriously take feedback and will review all solutions, especially yours, and edit my post. Please stay tuned. $\endgroup$
    – humn
    Nov 1, 2021 at 14:06
4
$\begingroup$

So it looks like the answer is

The police catches the thief in some time < 2/3

Reasoning

The thief must slow down because otherwise it would reach 0. The cop continues at speed one and before 2/3, when he would reach 0, he must overtake the thief as the paradox resolves itself.

$\endgroup$
6
  • 3
    $\begingroup$ This argument doesn't work: the thief can continue at speed 1/2 for all the time <2/3, following his own strategy if the cop is moving at speed 1, and the cop won't catch him in that time. $\endgroup$ Oct 30, 2021 at 10:42
  • 3
    $\begingroup$ @Randal'Thor but time marches on and at time 2/3, the cop cant be at 0, so must have stopped at the thief's location. $\endgroup$
    – SteveV
    Oct 30, 2021 at 13:23
  • 5
    $\begingroup$ Why must he have stopped at the thief's location? The thief can always stay closer to 0 than the cop, Zeno-like, following the strategy outlined in the OP. $\endgroup$ Oct 30, 2021 at 14:04
  • $\begingroup$ At what time must the thief slow down? $\endgroup$
    – user253751
    Nov 1, 2021 at 14:44
  • $\begingroup$ @user253751 the thief is constantly slowing down, approaching 0 speed. the cop isn't $\endgroup$
    – SteveV
    Nov 1, 2021 at 20:03
4
$\begingroup$

Expanding on obscuran's answer: https://puzzling.stackexchange.com/a/112389/11569

There is no answer because the game has no equilibrium, as obscuran explains.

Claim 1. For every fixed thief strategy (i.e. continuous path $f(t)$), there exists a cop strategy that beats it.

Claim 2. For every fixed cop strategy (i.e. continuous path $g(t)$), there exists a thief strategy that beats it.

Proof of Claim 1: Let $f(t)$ be the thief's strategy. At time $t=2/3$ the thief is at some location $x = f(2/3)$ in $(0,1)$. A winning cop strategy is to travel directly to $x$ by time $t=2/3$, then stay there. The cop can accomplish this continuously at a maximum speed of $1$, and catches the thief at time $t=2/3$ at the latest.

Proof of Claim 2: Let $g(t)$ be the cop's strategy. At each time $t$, the thief moves to location $g(t)/2$. This is continuous, moves at speed at most $1$ (actually $1/2$), and stays in $(0,1)$ because $g$ does. At all times there is a gap of size $g(t)/2$ between the two, so the thief wins.

Thanks to obscurans for improving and simplifying both arguments.

$\endgroup$
6
  • 1
    $\begingroup$ +1. I think the thief strategy is easier: just use $f(t)=g(t)/2$. $f$ inherits everything from $g$: continuity, domain, max speed 1. The cop also guarantees catching the thief by $t=2/3$ by moving to $f(2/3)$, which takes at most $2/3$ time. $\endgroup$
    – obscurans
    Nov 1, 2021 at 2:34
  • $\begingroup$ Thanks @obscurans, both good improvements! $\endgroup$
    – usul
    Nov 1, 2021 at 3:30
  • $\begingroup$ Except the cop's strategy as described depends on knowing a future property of the thief's movement, which we can't allow. There are ways to fix this, though. $\endgroup$
    – aschepler
    Nov 1, 2021 at 10:43
  • $\begingroup$ @aschepler is right. It can be fixed by following the cop's strategy as in the OP: simply travel towards the origin at unit speed. Instead of "catching", just think of whether the cop has passed the thief or not. Let $x > 0$ be the least value of the position of the thief in the time interval $[0,2/3]$ (which exists since it's a closed interval and position is a continuous function). Then, at time $2/3 - x/2$, the cop is at position $0 < x/2 < x$. $\endgroup$
    – Namaskaram
    Nov 1, 2021 at 12:41
  • $\begingroup$ But then, by the intermediate value theorem, the cop should have already crossed the thief at some point in time $< 2/3 - x/2$. Hence, the cop's strategy works against any "fixed" thief strategy. $\endgroup$
    – Namaskaram
    Nov 1, 2021 at 12:41
2
$\begingroup$

We don't know because the problem is not well defined. We know the cop moves with velocity $-1$ on the time interval $[0,\frac 23)$. We know the thief moves with velocity $-\frac 12$ on the same interval. Before $t=\frac 23$ the cop has not caught the thief. We don't know what to do at the limit because neither one is allowed to move to $0$. The stated velocities must break down before $t=\frac 23$ but we don't know when or how.

$\endgroup$
6
  • 4
    $\begingroup$ The problem is perfectly well defined. $\endgroup$
    – Eric
    Oct 30, 2021 at 5:37
  • $\begingroup$ It's the cop's proposed strategy that isn't well defined. $\endgroup$ Oct 30, 2021 at 20:35
  • $\begingroup$ Hmm, I think you've got a point. Neither the thief or the cop has any reason to change their strategy on the time interval [0,2/3), but their claims can't both be true on that time interval, otherwise we can't consistently claim where they will be at time 2/3. So something must be wrong. $\endgroup$
    – Eric
    Oct 31, 2021 at 2:36
  • $\begingroup$ I agree with this answer. The question doesn't specify what happens at time 1/3 if the thief walk left at speed 1 all the time. $\endgroup$
    – justhalf
    Oct 31, 2021 at 5:16
  • $\begingroup$ @Eric, perhaps defining a strategy formally as "a function of time which maps [0,inf) representing time to (0,1) representing position" will make it well defined? $\endgroup$
    – justhalf
    Nov 2, 2021 at 3:48
2
$\begingroup$

The thief cannot be caught.

The optimal strategy for both the cop and the thief is to move in the negative direction at full speed. For these strategies, we have functions that describe the position of the thief and cop for time t:

$ d_t(t) = 1/3 - t $

$ d_c(t) = 2/3 - t $

However, $d_t(t)$ is not defined for $t>=1/3$. For all $t<1/3$ (the range over which the problem is defined) $d_t(t) < d_c(t)$. Therefore, the cop cannot catch the thief.

Trying to say that the thief cannot continue to execute their strategy of moving in the negative direction at speed 1 would require supposing additional physics not specified in the problem. The situation is comparable to behavior around black holes. From the perspective of an infalling observer, the physics cease being defined beyond the time where the observer would reach the singularity. The situation is the same here. Given the allowed motion and constraints on the physical space, it also serves to constrain the time domain under certain motions.

$\endgroup$
2
  • $\begingroup$ I think this is the same as my answer. $\endgroup$ Nov 1, 2021 at 14:26
  • $\begingroup$ @DJClayworth The same conclusion, yeah. I upvoted your answer, I just thought I'd give explicit equations of motion and direct example of something in real life physics that behaves like this (at least in the math). $\endgroup$ Nov 1, 2021 at 15:57
2
$\begingroup$

I'm going to do something rather weird here, and create a second answer. That's because I want to answer a slightly different variant of the question, and propose a controversial result.

My other answer considers the formulation of the question, and also addresses the case where the endpoints of the universe are "allowed" but are outside the universe. This one specifically considers the case where the endpoints of the universe ($x=0$ and $x=1$) are forbidden to both players.

In that case I believe (controversially)

The cop will catch the thief.

How do I arrive at this? By simply noting that every point in the universe can be visited by the cop in a finite time $t<2/3$. It doesn't matter that there are an infinite number of points to visit, the cop can still visit them all. Just like they can visit all the points between $x=0.6$ and $x=0.5$ in a tenth of a time unit, even though that is an infinite number of points. (I've neglected the parts of the universe on the right of the cop, where $x>2/3$. We know that the thief can never reach that part of the universe without being caught, because movement is continuous so they would have pass through the cop to reach it, meaning they are caught.)

If every point that the thief might exist at can be visited in finite time by the cop, the thief will be caught.

But what about the strategies that seem in indicating the thief eternally evading the cop? They are subject to the same fallacies that Zeno's paradox falls to. Zeno says that Achilles cannot catch the tortoise because there is an infinite sequence of steps for him to so so. Likewise the "thief escapes" solution says there are an infinite sequence of steps for the cop to catch the thief. Zeno is wrong because the infinite sequence of steps finishes in a finite time. These strategies are wrong for the same reason. The thief can avoid the cop for an infinite number of steps, but that does not mean he can avoid the cop for an infinite amount of time.

In my other answer I ask what happens at $t=2/3$ (with the thief following his "optimum" strategy). If we impose the restriction that no player may be at $x=0$ then the answer is unknown, but whatever answer it is it doesn't matter. The thief must be at some position $x>0$ but also with a lower x than the cop's starting point (otherwise they are caught), and the cop (as we said) can visit all those positions before $t=2/3$. If the cop can visit all the possible locations of the thief in finite time then the thief must be caught.

$\endgroup$
24
  • $\begingroup$ I guess the real question to make this answer has weight is: what is a function that visits all location x>0 in finite time? $\endgroup$
    – justhalf
    Nov 2, 2021 at 1:29
  • $\begingroup$ But thanks to this second answer of yours, I think I realize the actual question by OP boils down to: is there a bijective function from a closed domain to an open codomain? And the answer is no. So the cop cannot reach all positions x>0 in finite time. Based on this, if we define cop (and thief) possible strategy as all continuous functions such that f(x)>0 for all x, then the cop cannot catch the thief. $\endgroup$
    – justhalf
    Nov 2, 2021 at 1:38
  • 1
    $\begingroup$ Um, didn't I just define a strategy as a function from [0,inf) to (0,1)? I meant that as a function of time. So with strategy f, at time x, the position would be at f(x). (perhaps my typo of x=2/3 instead of t=2/3 misled you, my bad). To clarify, when I said mapping from a closed interval, I meant it as an interval of time, since we are discussing about finite time. In all of my correspondences above, I never talk about mapping from a position to a next position, always from time to position. $\endgroup$
    – justhalf
    Nov 2, 2021 at 3:46
  • 2
    $\begingroup$ No - for those specific two functions, find the exact time the cop catches the thief by being at the same position. There isn't one. $\endgroup$
    – aschepler
    Nov 2, 2021 at 22:06
  • 2
    $\begingroup$ Any attempt to extend that cop's function to time $t=\frac{2}{3}$, not to mention beyond, will violate the word "continuously" in the original statement. $\endgroup$
    – aschepler
    Nov 2, 2021 at 22:12
2
$\begingroup$

The thief will be caught.

The cop simply moves at his maximum speed towards 0 until he catches the thief.

The thief is constantly going to retreat, certainly, and has an infinite number of positions to move to before 0 - but sometime prior to, and almost exactly, t=2/3, the cop will have checked every infinitely possible position and has to have found the thief by the time t=2/3 - but will not catch the thief in any specifiable time frame prior to t=2/3

$\endgroup$

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.