Alex Lvovsky

Alexander Lvovsky is an experimental physicist. After graduating from University of Moscow and getting a PhD from Columbia University, he became a Professor at University of Calgary in 2014, and later at Oxford University in 2018.

Alex Lvovsky

Website

The streets of the city are a square grid that extends infinitely in all directions. One of the streets has a police officer stationed every 100 blocks and there is a robber is somewhere in the city.

Can you devise a strategy that guarantees the robber will be spotted by a police officer at some point, no matter how he tries to avoid them?

Note: The officers can see infinitely far, but their running speeds are lower than the speed of the robber.

SOLUTION

Let the police officers are located at points with coordinates (100N, 0) for N = 0, ±1, ±2… First, we fix the positions of all officers stationed at points (±200N, 0), then repeatedly perform the following procedure, step by step:

On step M, we let the non-fixed officers who are closest to the center move to the free points with coordinates (K, 0) and (0, K) for K = 0, ±1, ±2, … ±M. Then we fix their positions.

Since there are fixed officers at points (200N, 0) at all times, the robber is contained within some vertical strip the entire time. Therefore, at some point there will be two fixed officers that will restrict the robber within a horizontal segment of size 1, at coordinates (x, T) for x ∈ (S, S+1) and some T. Finally, at some point an officer will move to the point (0, T) and will spot the robber.