Consider the following popular problem. Two trains are travelling directly toward each other. The first train moves at 50 km/h and the second train moves at 75 km/h. A bird is just chilling around and eating pebbles when the first train passes it and scares the bird into flight. At this point in time, the trains are 125 km apart. For whatever reason, the bird flies back and forth between the trains until they meet. The bird flies at 100 km/h. When the trains meet, how far has the bird flown?
If you want a hint, read the next paragraph; if you want to try to solve the problem on your own, stop reading now.
I think this started as an interview question. The inventors wanted you to try to do the “obvious thing” which is to figure out how far the bird has gone when it meets the second train for the first time, then calculate how far the bird has gone when it gets back to the first train again, and so on. If you were a good candidate for the job, you’d realize you were walking down one of Zeno’s paradoxes.
At this point, you’d take a step back and think, and hopefully, you’d come up with this solution: I don’t care how many times the bird goes back and forth. For all I know, it goes back and forth infinity times. What I care about is how long the bird travels for and how fast it’s going. I know the bird’s speed, and I can calculate how long it flies based on how fast the trains go and how far apart they are. At this point, you appreciate that the problem was doctored in your favor because 50+75 is 125, which means the trains travel for an hour before they meet, which means the bird travels 100 km. This is the “smart” way to solve the problem.
If you want a hint, read the next paragraph; whoever wants to solve it the “dumb” way on their own should stop reading now.
Zeno’s paradoxes all go the same. Let’s say there’s a bird and a seed the bird wants to peck. As the bird hops toward the seed, it gets halfway toward the seed. From there, it gets halfway between where it was a moment ago and the seed. From there, it gets halfway between where it was a moment ago and the seed. And so on. Zeno thought this meant the bird never gets to the seed because it takes infinity steps for the bird to get there. And yet birds managed this feat all the time, so it was a paradox. It’s not a paradox, because the steps are getting smaller and smaller in a predictable manner, so it’s easy to do infinity of them. For those who came here for the hint, try the problem with the trains having identical speeds if you can’t get it when they have different speeds. For those who want to avoid heavy math, you can skip to the last paragraph.
The bird flying between the two trains will fly between them an infinite number of times before they meet, but that shouldn’t stop us from trying to add them all together. First, let’s rid ourselves of numbers and get to the heart of the problem. Let the original distance between the two trains be , the speed of the first train be , the speed of the second train be , the speed of the bird be , and the distance travelled by the bird , all real numbers. We know and , or the problem doesn’t work. In words, the trains don’t go backward, and the bird flies faster than the trains. If the trains were allowed to have negative speeds, they wouldn’t both be “travelling directly toward each other”, and if the bird flew slower than the trains, it wouldn’t be able to bounce back and forth between them. Also , for obvious reasons.
Let’s solve it the “smart” way in equations and letters real quick, to get used to the symbols we’re using, and so we can verify the answer we get from the “dumb” method. First we found out how long the trains travelled for, then we multiplied by the bird’s speed. We found how long the trains were travelling using their total speed and original distance.
Consider the part of the bird’s journey where it flies from the first train to the second train for the first time. Let’s call the distance travelled during it , and the duration of it . We find the “smart” way, but applied to the bird and second train instead.
Now let’s consider the next part of the bird’s journey. The trains are a different distance apart, but let’s not worry about that for a moment. We’ll simply name the distance between the trains as the bird bounces off the second train for the first time . We’ll retroactively let for the first leg of the journey. To be clear, I’m using capital letters for when the bird is travelling from the first train toward the second, and lowercase letters for when the bird is travelling from the second train toward the first. The number says which round trip this is.
For the first part of round trip 2, the bird is travelling from the first train to the second train for the second time, and we have
which looks so much like the first part of the journey, we’re going to go straight to some generic formulas.
Now it’s time to worry about and , the distances between the trains at the start of each part of the journey. We know , so let’s find . We know the duration of the first part of the journey, and we know how fast the trains are going, so we can find how much closer they are together and subtract that.
And now let’s find and .
But we seek a general form. You can probably already see the pattern:
Let’s find in terms of and in terms of .
Hey look, they are really similar! Let’s set equal to that big mess so we have
These are called a recursive forms because defines itself in terms of . In this case, and . This is bad because if I ask for you’ll have a whole bunch of calculations to do, or a whole lot of symbols to write out, before you get back to which is the only value we really know. Instead, we need an explicit form. Well, it shouldn’t be too hard to see:
Great, so we know how far the bird travels at each leg of the journey. Let’s add all that together.
Well that’s looking pretty nice, except what’s the value of those sums? For a second, let’s look at
There’s too many of those variables there. Maybe we could subtract a bunch of them out if we did
Soon we have to let go to infinity, but for a second let’s consider
First we’ll look at this part:
Remember we initially stated that ? Well that means , and that means
We can follow similar steps to arrive at
Now, the product of two numbers that are between 0 and 1 is also a number between 0 and 1, so we know that . This is great, because it means
You can try it on a calculator if you don't believe me. Type in a number between 0 and 1 (not exactly 1), then multiply by that number, and keep hitting the multiply button and eventually, because calculators don't have infinite precision, you'll end up at 0. Anyway, back to our sum. We had
and now we want n to go to infinity, so
Back in birdland, we had
and we apply the formula we just found for those infinite sums.
It's all downhill from here, folks.
We replace with its definition in terms of
Oh hey that worked out well. As you can see, we've arrived at the answer we got from the "smart" method. Now here's what I hope will happen. I don't know if this question even gets asked during interviews anymore. But I hope you will get asked this question at an interview and proceed to solve it the "dumb" way, acting totally unsure of yourself, mumbling, "Okay, well, first part of the trip…" and, "Then he goes back…" and, "I guess he's going back and forth… a lot of times…" and, "Infinite sum…" and plod through the equations and end up with the right answer, and then check it against the "smart" solution. Your interviewer will probably get lost and not hire you. If they do hire you, you know you're at the right place. But that's not the point. The point is you took an interview question, lifted it above your knee, and smashed it completely in half.