Infinite Version of Fox in a Hole

 The fox-in-a hole is a classic puzzle where there is a fox in one of 5 holes along the x-axis. Every morning you can check a hole for the fox. If you find it, you win. Otherwise that evening the fox moves to an adjacent hole. You can check any hole the next morning and so on. The goal is to catch the fox, irrespective of where it starts from.

An infinite version is as follows.

There are holes along the x-axis on the points $1,2, \dots$ i.e the positive integers. There is a fox in some hole somewhere. Your goal is to catch it. 

Everyday you can check any hole in the morning. If you miss, that evening the fox moves to an adjacent hole (the only hole adjacent to hole 1 is hole 2). You check again the next morning and if you miss the fox moves in the evening and so on.

Can you eventually catch the fox?

Scroll down for a solution.

.

.

.

.

.

Solution:

It is enough if we can solve a finite version of this!

$\textbf{Infinite from finite}$

Suppose you knew the fox was at hole $ \leq N$ and that there was an algorithm to catch it within $f(N)$ days if that were so. If we run the algorithm for $f(N)$ days and don't catch the fox, then we know it started at a hole $> N$. 

We can use this to solve the infinite version as follows:

Consider the sequence $x_n$, defined as $x_1 = 1$ and

$$x_{n+1} = f(x_1) + f(x_2) + \dots + f(x_n) + n$$

Clearly $x_{n+1} - \sum_{i=1}^{n} f(x_i) \to \infty$ and so, given any $M > 0$, eventually $$x_n > M + f(x_1) + f(x_2) + \dots + f(x_{n-1})$$

Our infinite version strategy is now:

Assume the fox is at a hole $\leq x_1$. Run the finite algorithm for $x_1$. If we don't catch it, assume it is at hole $\leq x_2$ and run the finite algorithm for $x_2$ and so on.

If the fox started at hole $M$ initially, then after $n$ steps of the above, the fox will at max be at the hole $M + f(x_1) + \dots + f(x_n)$.

Thus eventually, one of our $x_K$ will be greater than the current hole of the fox, and we will catch it, when we run the finite algorithm for $x_K$.

$\textbf{Finite Algorithm}$

A finite algorithm for $\leq N$ is as follows:

Assume the fox started at an even spot and make a sweep down from $2[(N+1)/2]$. If we don't catch it, we know it started at an odd number and is at a hole $\leq N + 2[(N+1)/2]$. We can now make another sweep down, starting with a high enough hole numbered with the correct parity.

This gives $f(N) = O(N)$, and we eventually catch the fox in $O(M)$ days, where $M$ is the initial hole of the fox.