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 ...
Milo Brandt's user avatar
  • 7,881
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 ...
DJClayworth's user avatar
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 ...
ffao's user avatar
  • 21.8k
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 ...
obscurans's user avatar
  • 505
16 votes
Accepted

Angels & Demons (Open question)

noedne's user avatar
  • 15.4k
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.
Glorfindel's user avatar
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
Ivo's user avatar
  • 11.2k
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 ...
isaacg's user avatar
  • 6,944
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 ...
Rand al'Thor's user avatar
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 ...
10010100102ohno's user avatar
10 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 ...
IvanSanchez's user avatar
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 ...
D Krueger's user avatar
  • 798
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 ...
Kyle Parsons's user avatar
8 votes

Spiders on a cube

An upper bound for the 3 spider case:
StephenTG's user avatar
  • 3,575
7 votes
Accepted

Hiding Cat Puzzle on a Grid

You can succeed when n = Here's how: Thoughts on proof of optimality:
Mike Earnest's user avatar
  • 32.4k
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
loopy walt's user avatar
  • 21.2k
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 . . .
humn's user avatar
  • 21.9k
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'...
aschepler's user avatar
  • 1,485
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 ...
Pepper's user avatar
  • 337
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 ...
Florian F's user avatar
  • 29.8k
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,
ApexPolenta's user avatar
  • 2,690
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
JHR's user avatar
  • 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 ...
gtwebb's user avatar
  • 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$. ...
ralphmerridew's user avatar
5 votes
Accepted

Caught in the storage maze

Is there a strategy? Why/how?
fljx's user avatar
  • 15.9k
4 votes

Can the cop catch the thief?

So it looks like the answer is Reasoning
SteveV's user avatar
  • 15.9k
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 (...
usul's user avatar
  • 209
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 ...
Mark Bailey's user avatar
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 ...
Shufflepants's user avatar
4 votes

Catch the invisible and omniscient thief

Fun fact (partially related to the puzzle). What if the thief has infinite speed, but there is more than one cop (cops communicate with each other and work together)?
Tomasz23's user avatar
  • 141

Only top scored, non community-wiki answers of a minimum length are eligible