Princess on a train

Suppose the princess has escaped the confines of a graph (See here and here). She is now on a train and prince must once again come up with a strategy to capture her.

I was first told about this puzzle by a fellow postgrad student who was asked this during a job interview (but with no princesses involved).

The problem is as follows:

Suppose there exists an infinitely long railroad track with a train running along it at some unknown nonzero integer speed of metres per second in some unknown direction. To avoid silly cases the train is atleast 1m long.

Along the track there are detection points placed one metre apart along the entirety of the track. Every second the prince activates a detection point and captures the princess if the train is in contact with that point at anytime during that second.

The question is "Can the prince come up with a sequence of detection point activations in order to catch the princess?".

For a very long time I beleived that no sequence existed. I did solve a couple of simple of easier cases but not the bigger one. The main idea of the solution I am about to write is due to Alistair Bird. This was at the second conference we had both attended, the first was when I was first told about princess in a castle. Many many more possible candidates for princess puzzles were discussed but none really worked such as princess on a boat, princess on a Banach space, princess being chased by a bomber plane, the acrobatical princesses on the unit interval and so on.

SOLUTION

Before I state the solution I ask anyone reading this to attempt the puzzle themselves. It is a very fun anf frustrating puzzle to attempt.

Let the train track be $\mathbb{R}$ and all possible start points for the train be $\mathbb{N}$. Instead of taking a natural number for the speed let us take direction into acount and we can see that $\mathbb{Z}$ is all possible velocities of the train. The key to the solution is now noting that $\mathbb{N}\times\mathbb{Z}$ is countable. Let $(x_{n},v_{n})$ be an enumeration of $\mathbb{N}\times\mathbb{Z}$. Since $\mathbb{N}\times\mathbb{Z}$ is the collection of all states the train we simply have to check each possible state at some time. For this we use the following rule:

We check point $x_{t}+t\cdot v_{t}$ at time $t$.

This strategy works since suppose that a train starts at position $x$ with velocity $v$. Then there exists a $n$ such that $(x,v)=(x_{n},v_{n}).$ After $n$ seconds we see that the train will be at $x_{n}+nv_{n}$ which is exactly the point we will be checking at that time.

I hopefully did not make that more complicated than it is.

As a last note this problem can still be solved if a real speed is assumed.