Can the Spider catch the Fly?

Question

The spider and the fly are both on an infinite line and the spider is hungry. He can move twice as fast as the fly, however his vision is very bad (he can only see the fly when he is 1 meter or less from the fly) and he doesn't know where the fly starts. The fly can always see where the spider is and obviously will move so as not to be eaten. Can the spider catch the fly in finite time, no matter where the fly starts, or will he go hungry?

Answer 1

Assumption (& simplification):

The spider and the fly starts at different finite points on an infinite 1-d axis.

Furthermore, assume the fly starts somewhere. Whether it's 10, 100 or 1000 it doesn't matter (but can't be $\aleph_0$). The spider starts at the origin (position zero).

Answer:

By turning around after going N times the distance before its last turning, the spider can always catch the fly, as long as N > 3.

Example:

With N = 4, the spider turns around at 1, -3, 13, -51, ...

Proof:

Obviously the optimal strategy for the fly is flee away from the spider, so this is assumed to be "always true".

Now that the spider goes twice as fast as the fly:

Assume the first time (from start to first turn) the spider goes 1 meter, then we can construct a list of "turn positions" with the following formula: $$\begin{align} a_0 &= 0 \\ a_1 &= 1 \\ a_{i+1} - a_i &= -N(a_i - a_{i-1}) \end{align}$$ Which solves into $$a_i = \cfrac{1 - (-N)^i}{N + 1}$$ Meanwhile, the distance that the fly can go is: $$b_i = \frac{1}{2} \times \cfrac{N^i - 1}{N - 1}$$ Since $1-(-N)^i$ and $N^i-1$ grows at the same speed, minus the sign for the difference in direction, we know that $a_i$ outruns $b_i$ as long as the following holds: $$\frac{1}{2} < \frac{N-1}{N+1}$$ This proves the conclusion at the beginning.

Answer 2

Yes, the spider can always catch the fly.

First, observe a simpler case:

Fly distance from the spider is known, direction not. Spider starts in one direction long enough to catch the fly if direction is right. If not caught, direction is wrong, change direction and catch the fly on the other direction.

Now, let the start distance to be unknown:

Assume the distance is 2m (or any other $>1m$). Go into one direction just long enough to catch the fly if the direction is right and fly starting distance less than 2m. If not change direction and assume starting distance was twice as assumed in previous step. As starting distance is finite, in some step calculated distance will be larger than starting distance.