4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ If the fly is infinitely far down the infinite line from the spider, he'll obviously move away from the spider, and the spider, who has no clue as to the fly's infinite whereabouts, can only guess which way to go, and if he does go infinitely towards the fly then they'll just keep going infinitely in the same direction at different speeds for eternity. I'd say the spider goes hungry. $\endgroup$ May 16, 2022 at 20:23
  • $\begingroup$ @Rumpelstiltskin answers are not for comments, please. Additionally it seems you're making some assumptions which, while reasonable, are not confirmed by the OP - I've asked for confirmation in my first comment. $\endgroup$
    – bobble
    May 16, 2022 at 20:25
  • $\begingroup$ @NielIGuess If your comments are for a specific person, please add an @-sign right next to their username (such as @Rumpelstiltskin) to let them know the comment is for them. $\endgroup$ May 16, 2022 at 20:41
  • $\begingroup$ Choosing direction at random and preserve it forever for the spider succeeds if direction is against the fly and not succeeds if it is away. So it is to prove or disapprove an existence of zig-zag spider's strategy of changing direction in some increasing consecutive distances. Fly has a simple optimal strategy - always moving away from the spider. Intuitively it seems that spider can always decrease the distance to the fly enough to catch it. $\endgroup$
    – z100
    May 16, 2022 at 21:34

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You were faster, upvote for this, @iBug $\endgroup$
    – z100
    May 17, 2022 at 19:11
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This assumes that the fly stays stationary, which is not necessarily the case. $\endgroup$
    – iBug
    May 18, 2022 at 6:08
  • $\begingroup$ @iBug, not explained in details, on each step the distance increase, which is finite and exactly determined of a fly is included. And when the initial distance + cumulative increase reached, there is at most two steps to catch the fly, as in a simplified case. $\endgroup$
    – z100
    May 18, 2022 at 9:02
  • 1
    $\begingroup$ If I'm interpreting your answer literally (starting distance was twice as), it's the same as mine with N = 3, which is unfortunately on the edge of failure. In that case, the spider only goes as far as the fly (i.e. $a_i=b_i$), and has no extra distance to cover the initial distance. $\endgroup$
    – iBug
    May 18, 2022 at 18:25
  • $\begingroup$ @iBug, you're right, my construction for sure needs an improvement, at least an adddition of distance increase from previous step to double distance. In fact, this is a nice and theoreticaly interesting problem for math SE. With slightly different formulation, maybe could lead to some kind of problem of convergence existence. $\endgroup$
    – z100
    May 18, 2022 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.