There is a fox that hides in an infinite row of bushes (indexed by $\mathbb{N}$), give a strategy to eventually catch the fox.

Question

Recently, one of my professors gave a riddle to my class. He got it while studying abroad some years ago. It goes like this,

Before you is an infinite row of bushes (indexed by $\mathbb{N}$). A fox is in one of the bushes, but you do not know which. Each time you look at a bush, if the fox is not there, it jumps ahead a fixed but unknown number of bushes. Give a strategy to eventually capture the fox (in a finite, but potentially large number of attempts).

Let $a \in \mathbb{N}$ be the initial position of the fox and let $b \in \mathbb{N}$ be the unknown jump size. If $(s_n)$ is our sequence of guesses (i.e. $s_4 = 8$ means our fourth guess is the $8$th bush) and $(t_n) = a + b \cdot (n - 1)$ is the sequence of the fox's location, then we are looking to find $(s_n)$ so that there exists an $n \in \mathbb{N}$ where $s_n = t_n$. Here are my thoughts so far:

(1) Because the number of bushes the fox jumps is constant and unknown, our strategy must involve guesses that grow farther apart over time. Say we start with the first bush and cycle through every bush after it, then if $b > 1$ or $a > 1$, we will never catch the fox.

(2) Because our strategy will involve guesses that are increasingly farther apart if we pass the fox at any point, we will not catch it. Thus, it also makes sense to start our guessing with 1.

(3) I considered $(s_n)$ = the $n$th prime. If there is some property that relates $(t_n)$ to prime numbers, maybe this could be useful. I do not know much about primes, so I did not get very far with this strategy.

(4) I made some progress using Fibonacci numbers. If $(s_n) =$ { $1,1,2,3,5,8,13,\dots$ }, then it would suffice to show that on the $n$th guess, the fox cannot be in the interval $(s_{n-1},s_n)$. The first number that does not appear is 4. Thus, the fox would not be caught if $t_5 = 4$. This is not possible because the only $a,b$ that satisfy this are $a = 1$ and $b = 1$, but if $a=1$ we catch the fox on the first guess. The next possible set of bushes in which the fox would not be caught is {6,7}. This would be $t_6 = 6$ or $t_6 = 7$. Once again, the only $a,b$ that satisfy this are $a = 1$ and $b = 1$. This appears to work for the first couple of cases, but this strategy breaks down pretty soon. Notice, if $t_7 = 10$, then with $a = 4$ and $b = 1$, the fox is not caught. Even if this strategy did work, I am not sure how to generalize to an arbitrary guess.

(5) I have previously asked a question related to this here in which I asked the question strictly in terms of sequences and recieved an answer. I am not sure how the answer applies to the question of the fox and the bushes or if that answer even works.

Answer 1

Welcome to mse!

This is a fun question, and here's a sequence of progressively more helpful hints (in case you want to work it out yourself!)

Hint 1 (more of an observation, really):

If a fox starts at $a$ and moves $b$ bushes each time you check, then after $n$ many attempts the fox is located at $a + bn$.

Hint 2 (another observation):

There's only countably many possible foxes. Indeed, they're indexed by a choice of $(a,b) \in \mathbb{N}^2$.

Hint 3 (the first actual hint):

Pretend you're playing against all possible foxes in parallel. Can you devise a strategy that's guaranteed to hit every fox? Said more mathematically, try enumerating the foxes as $F_1, F_2, F_3, \ldots$. Are you familiar with diagonalization?

Hint 4 (this one is a BIG hint):

Say that the $k$th possible fox is the one that starts at $a_k$ and moves $b_k$ many steps at each guess. Can you hit fox $k$ on your $k$th guess? What if every guess you make follows this rule? Since every fox is $F_k$ for some $k$, do you see how you're guaranteed to hit every fox if you do this?

Hint 5 (this is a solution):

Let's make the $F_k$s explicit, as that might make things easier. First, notice that $\pi(a,b) = \frac{(a+b)(a+b+1)}{2} + b$ is a bijection betwen $\mathbb{N}^2$ and $\mathbb{N}$ (see here for instance). So then the fox associated to $(a,b)$ will be called the $\pi(a,b)$'th fox. Then the plan will be, on the $k$th guess, to guess wherever fox $k$ is at that moment. Since every fox is $F_k$ for some $k$, this means we're guaranteed to hit our fox on our $k$th guess! Explicitly, if $\pi(a,b) = k$, then after making $k-1$ guesses, fox $k$ will be in bush $a + (k-1)b$. So for our $k$th guess, we should guess $a + (k-1)b$. Even MORE explicitly, see this table: If you always guess along the diagonal of this table (this is why this proof method is called diagonalization) then you're guaranteed to hit every fox!

---

I hope this helps ^_^

Answer 2

The answer to your previous question does apply. The strategy is to choose some inverse pairing function $f: \mathbb{N} \to \mathbb{N} \times \mathbb{N}$, and then for each turn t, choose where the fox would be if the fox had chosen the values of $a$ and $b$ given by $f(t)$. I.e. look at the $f_a(t)+tf_b(t)$ th bush.

You won't be able to find a working strategy where the gaps increase over time, as every bush must be visited at least once, in case the fox started in that bush and chose $b=0$. In fact, as chosing bush $t$ doesn't work either, this means you have to go backwards or repeat yourself sometimes.