Switch to: pl

# Achilles and a turtle - about infinite sequences

In the fifth century BC, a famous philosopher, Zeno of Elea, was trying hard to prove that movement is just an illusion. Instead, he contributed to the development of infinite sequences. Let’s learn what they are and if Achilles can outrun a turtle.

Achilles and the turtle stand at the starting line of the race for any finite distance. Achilles can run 2 times faster than the turtle, and therefore allows the turtle to move a certain distance from the start (we will call it d and assume it is smaller than 1/2 of the total distance). Achilles is running 2 times faster than the turtle, so when he till getting to the point d (where the turtle started), the turtle will already run away a half of that distance (d/2). When Achilles gets there, the turtle will “run away” again, by half of the previous distance (d/4). When Achilles reaches this place, the turtle will be again d/8 away from him, and so on forever. Conclusion: Achilles will never catch up with the turtle even though it runs twice as fast as him because they will always be separated by a narrowing distance.

From the mathematical point of view, it is not a hard problem to calculate where Achilles will catch up with the turtle. If the turtle starts at the point d, and turtle’s speed is v, then Achilles speed is v*2. So we can calculate the Achilles’ position using the following equation:

$$x = v*2 * t$$

Where t is time. The position of the turtle can be calculated by:

$$x = d + v * t$$

Achilles catches up with the turtle when they are at the same x. To calculate when that is, we need to connect those two equations:

$$v*2*t = d + v * t$$ $$v*t = d$$

The solution is:

$$t = d/v$$

So:

$$x = d + v * t$$ $$x = d + v * d/v$$ $$x = d + d$$ $$x = 2d$$

So Achilles will catch the turtle, and we know when and where. Although this way of proving the thesis might be considered as cheating, because this is not how Zeno formulated the problem.

So let’s follow his way of thinking. To get where the turtle is, Achilles at first needed to run distance d, then d/2, then d/4, then d/8, d/16, etc. Every next distance is smaller and smaller and can be calculated using the following equation:

$$\frac{d}{2^{n}}$$

Where n = 0, 1, 2, …

The whole distance is a sum of all those distances. How many of them are there? We’ve already established that: the infinite number. So this is how we can express the whole distance:

$$d + \frac{d}{2} + \frac{d}{4} + \frac{d}{8} + \frac{d}{16} + \frac{d}{2^n} + ... = \sum_{n=1}^{\infty} \frac{d}{2^{n}}$$

Just because it is a sum of an infinite sequence, it doesn’t mean it can’t be finite. Every next part is getting smaller.

Let’s try to calculate the result by ourselves and figure out the entire distance after each step:

1. d/2 = d/2
2. d/2 + d/4 = 0.75 d
3. 0.75 d + d/8 = 0.875 d
4. 0.875 d + d/16 = 0.9375 d

You can continue calculating. After the next steps, he will run 0.96875, 0.984375, and 0.9921875 d. After the 10’th step, he will run 0.9990234375. It becomes clear that we are getting closer to d, but we cannot exceed it. After the 100’th step Achilles will reach 9.9999999999999999999999999999 d. So how many steps do we need to get to d? Exactly the infinite number.

Another way to think about it is the visual way. Imagine a square. Then make a line dividing it to 2 rectangles of the same size. Take one of them and make a line to divide it by two. Then take one of those created as a result and divide it by 2. If you continue it indefinitely, you will visualize this sum. Each of these rectangles is 2 times smaller, and yet they all sum up to the one big. Visual way to see why sum of next elements, each 2 times smaller, sums to the size of the first one times two.

Based on those thought experiments we know that the sum is d, and this is where Achilles will catch the turtle.

$$\sum_{n=1}^{\infty} \frac{d}{2^{n}} = d$$

Although this example does not sound very realistic - turtles are generally rather slow. I would assume that Achilles should be at least 10 times faster. In such conditions, where will he catch the turtle? At first, he will need to get to the point where the turtle started - this is d. In that time, the turtle should run away by d/10 = 0.1d. When Achilles gets there, the turtle should run away by d/100 = 0.01. Then by 0.001d, 0.0001d, 0.00001d, 0.000001d, 0.0000001d, etc. It should be visually clear that the sum is 1.11111... (an infinite number of 1) d. The official notation for such a number is 1.(1)d.

So we know where Achilles will catch the turtle when he is 2 and 10 times faster. What about other cases?

We already know that the point where Achilles will catch the turtle can be calculated using the following formula:

$$\sum_{n=0}^{\infty} \frac{d}{p^{n}} = d + \frac{d}{p} + \frac{d}{p^2} + \frac{d}{p^3} + ...$$

Where p is how many times faster Achilles is. We assume that Achilles is faster than the turtle, so p > 1. How much is this sum? This is an infinite sequence, and calculating it can be complicated. Although there is a mathematical trick that can help us - we can express the sum of all that number as a variable (like Z) and try to express some part of the sequence using this variable. For example:

$$Z = d + \frac{d}{p} + (\frac{d}{p^2} + \frac{d}{p^3} + ...) = d + \frac{1}{p}(d + \frac{d}{p} + \frac{d}{p^2} + \frac{d}{p^3}) + ... = d + \frac{1}{p}Z$$ $$Z = d + \frac{1}{p}Z$$ $$Z - \frac{1}{p}Z = d$$ $$\frac{p - 1}{p}Z = d$$ $$Z = \frac{d * p}{p - 1}$$

Let’s check the correctness of this formula. First assuming that p = 2:

$$Z = \frac{d * 2}{2 - 1} = \frac{d * 2}{1} = 2d$$

Perfect. Now for p = 10:

$$Z = \frac{d * 10}{10 - 1} = \frac{d * 10}{9} = d*10/9 = 1.(1)d$$

Works again.

As it turns out, Achilles will be able to catch up with the turtle, and we can calculate where. So Zeno of Elea was wrong. Although, to prove that we had to understand infinite sequences, and thus we’ve learned something new, as our ancestors did in the past.

What do you think about the article? Marcin The author of the Effective Kotlin and Android Development in Kotlin books, founder of the Kt. Academy and Learning-Driven, programming trainer, speaker at international conferences, experienced developer.