46
votes
Accepted
Can the Policeman catch the Thief?
Yes, the policeman can catch the thief, although it may take a very long time. In particular, the following strategy works: The policeman starts in the center. First, he makes a counterclockwise loop ...
- 7,871
21
votes
Can the cop catch the thief?
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 ...
- 426
18
votes
Accepted
Hunter chasing a fox on a graph
Number the nodes as follows:
A valid solution is to check:
To see that this works, first note that the fox can only go from a hole in an even-numbered level of the tree to a hole in an odd-numbered ...
- 21.6k
16
votes
Accepted
Can the cop catch the thief?
Fundamentally, the issue is that
For every fixed cop strategy, there exists a thief strategy that beats it.
For every fixed thief strategy, there exists a cop strategy that beats it.
For an easier ...
- 505
16
votes
Accepted
13
votes
Spiders on a cube
Not a definite answer but I narrowed it down to 2 possibilities.
It's either
In this case
or the second possible answer is
Because
- 11.2k
13
votes
Angels & Demons (Open question)
I just came back home and was about to draw a diagram illustrating this, but I can't do any better than @noedne already did.
- 27.9k
11
votes
Can the cop catch the thief?
Cleaned up answer:
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 ...
- 5,236
11
votes
Can the cop catch the thief?
is right, basically because
The problem with one of the two suggested approaches is that
The space in which they're moving is sort of like a 1-dimensional hyperbolic space: they can get ...
- 116k
11
votes
Can you stop copy Alice?
Edit
2012rcampion observed that we also need to multiply by 2 the distances on the plane
Not an answer with a strict proof of the final behavior, but instead a simulation with code that show a ...
- 738
9
votes
Lions and Zebras on a Chess Board
Note: The following full answer expands on the previous partial answer, which has been retained below.
Full answer
To analyze all the possible states, the algorithm Ken Thompson described in his ...
- 788
9
votes
Accepted
Spiders on a cube
For two spiders, one of the spiders has to be at least as fast as the ant in order for the spiders to catch the ant.
There are 3 situations:
Both spiders are slower than the ant: The ant can avoid ...
- 206
9
votes
Accepted
How long can you survive at the devil's playground?
You're screwed in constant time, no matter your speed, since the devil has a good strategy.
I cannot claim to having found the devil's optimal strategy, but I do claim that there is an upper bound to ...
- 451
8
votes
7
votes
Accepted
Hiding Cat Puzzle on a Grid
You can succeed when n =
Here's how:
Thoughts on proof of optimality:
- 32.1k
7
votes
Accepted
1 lion, with a zebra and a fixed enclosure
Let's focus on the
A few observations:
Conversely:
This already resolves C as
To avoid tedious edge cases I'll assume that the enclosure is a rectangle with one side completely open.
B
A
- 19.1k
6
votes
Can the cop catch the thief?
The number line’s origin’s being excluded means that . . .
It also means that the maximum speeds of both cop and thief . . .
- 21.8k
6
votes
Can the cop catch the thief?
EDIT: I don't know!
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'...
- 1,475
6
votes
Spiders on a cube
I feel like 1/2+ε is enough for the 3 spider case. The spiders can start (or take their sweet time to get) in this configuration:
And then the two slow spiders can follow the red arrows to ensure the ...
- 337
6
votes
Accepted
Precision Tag - can the lion win?
Edited because for some reason everything below gets flagged as spam in a de novo post, but not in edits made to an existing post!
The answer is that
A discussion (below) of the generality and ...
- 175
6
votes
Catch the invisible and omniscient thief
I have to remove my post about the idea of escaping the cop by hanging around an intesection. Despite concluding that it is in fact not valid, people still refer to it as valid
Instead, as explained ...
- 26.7k
6
votes
Can you stop copy Alice?
Partial answer to prove that
For convenience, define the player chasing Alice to be Bob.
Alice's strategy:
This results in the following figure for one of Alice's clones:
In other words,
- 2,166
6
votes
Can you stop copy Alice?
A partial answer/a few observations:
The final step I am missing to turn this into a full answer is
- 406
5
votes
Accepted
Can the policeman actually catch the thief, instead of shooting?
I tried using spoilers for the tables but couldn't figure it out sorry.
I believe the cop could catch the thief in a city that is
Once the cop is within 2 blocks of the thief and knows where he is ...
- 3,626
5
votes
Catch the invisible and omniscient thief
Just to show that dodging around the intersection isn't enough, consider the simpler city when there is just one intersection, four roads that go a unit distance away from it, and $S_c > 7*S_t$.
...
- 3,323
5
votes
Accepted
4
votes
Spiders on a cube
For my analysis, I will assume that all we get to specify is the sum of the speeds of the spiders and that the sum we specify must work for any possible assignment of that total speed to the spiders ...
- 691
4
votes
Can the Policeman catch the Thief?
Well, first of all, I don't know what the thief has stolen, but unless it is a weapon of mass destruction or something that the thief intends to use to kill, it's pretty hard to justify valuing the ...
- 141
4
votes
4
votes
Can the cop catch the thief?
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 (...
- 141
Only top scored, non community-wiki answers of a minimum length are eligible