More Fun with Math

The runaway student – three different ways of solving one problem

Here is a problem I read in a Russian site:

A student is running away. He is moving at 1 mph.

Pursuing him are a lion, a tiger and his math teacher.

The lion is 40 miles behind and moving at 6 mph.

The tiger is 28 miles behind and moving at 4 mph.

His math teacher is 30 miles behind and moving at 5 mph.

Who will catch him first?

Analysis

Obviously we have a set of three problems. They are all basically the same, but the details are different. The problems are of the same class.

Here is a little excursion into computer science. One of the things we strive to do is to create solutions for classes of problems rather than individual problems. In your daily routine, you call it re-usability. Not all classes of problems have such solutions. If a class has a general (re-usable) solution, it is called computable. Otherwise it is unsolvable. Within unsolvable classes, we may still solve individual (some but not all) problems, albeit with different approaches to each. Luckily the vast majority of our daily problems are computable, and the 3 problems of our runaway student belong to a computable class.

So, let’s solve for the catch-up time by the math teacher, after all she is the most frightening. She might even make the poor runaway solve this very problem – perish the thought!

Method 1 – numerical analysis.

At 30 miles and 5 mph, it’ll take her 6 hours to come to where the student was to begin with. But by then the student has advanced by 6 miles.

6 miles require 6/5 hours, but by then the student advanced by another 6/5 of a mile as well. And so on and so forth. So what are we to do? One way is to write code and iterate it until we have solved it. But this is an infinite process so we’ll end up with an infinite loop. So what to do? We’ll use the principles of numerical analysis.

Any calculator – your computer included – has a limited number of digits. A double floating point number is good for about 14 digits. Nothing can be computed at a greater accuracy than that. This means that we will not iterate ad infinidum, but rather to the point where 2 consecutive iterations yield the same result. When we do financial computations, we don’t even have to go that far. We stop at the 10^th of a penny.  It behooves us here to stop at a 10^th of a second (100 milliseconds) and this will how we will avoid an infinite loop.

Interestingly this alludes to the Zeno paradoxes of motion – in particular “Achilles and the Tortoise”. Zeno says exactly the same. To catch the tortoise, Achilles must always first come to where the tortoise was, but the tortoise keeps moving – hence Achilles will never catch the tortoise and our math teacher (or lion, or tiger) will never catch the student, or the policeman the thief. Here is my resolution to the paradox. The distance and time in each step are smaller and smaller, so the student will be caught. The only thing that is infinite is the iterative solution. The race is a convergent geometric process so the steps are diminishing, but each step in the solution takes the same amount of effort and time so with an infinite number of steps, we’ll spend an eternity solving it.  This BTW is an original thought that I have never seen before.

But I digress. Let’s simply write the code to solve the problem. To make sure that it runs everywhere, I’ll do it in JavaScript.

function LongCatchUpTime(D, PV, FV)

// D is Distance; PV is Pursuers Velocity; FV is Fugitive’ Velocity

{

    var t = 0;

    var T = 0;

    var d = parseFloat(D);

    var pv = parseFloat (PV);

    var fv = parseFloat (FV);

    t = d / pv;

    while (t > 0.000001) //a 10th of a second is 1/36,000 of an hour, I used 1/100,000

    {

        T = T + t;

        d = t * fv;

        t = d / pv;

    }

    return T;

    }

By and large, the higher the Pursuer’s velocity relative to the fugitive, the faster the calculation.

Solving this with the 10^th of a second limit yields: 7.499999232000001

Method 2 – Geometric Series.

Each step in the iteration above is smaller than the next. As you saw, we stopped iterating when the last step was small enough, small enough not to really matter.  When we have a sequence of numbers in which the ratio of each number to its predecessor is fixed we call the sequence geometric. When we are looking at the sum of sequence, we call the sequence of sums series.  Now let’s look at our student and teacher. The teacher runs 5 times faster than the student, so with each iteration the distance between them shrinks to a fifth of what it was before. This is a fixed ratio so we deal with a geometric series.  We normally designate this ratio as q and when q is less than 1 (0 < q < 1) the sum of  + … +  is  – 1) / (q – 1). When q is less than 1, it is easier to use ) / (1 - q).

Now, the steps are 6 hours then 6/5 hours then 6/5*5 and so on, so q = 1/5. And the whole series is multiplied by 6.

Also because q is less than 1 , 1/  diminishes to 0. So the sum is just  / (1 - q). or 1/ (1 – 1/5) = 1 / (4/5) = 5/4. This times 6 yields 7.5 hours.

We can now continue with some algebra and take it back to a simpler formula. This is arduous and I am not going to do it here. Instead let’s do some simpler algebra.

Method 3 – Simple Algebra.

If the time to capture the fugitive is T and the fugitive travels at 1 mph, then by the time the pursuer catches him he travelled additional T miles. Time is distance divided by speed, so….

(D + T)/V = T  thus

D + T = VT  and

D = VT – T = (V – 1)T  and T = D/(V – 1)

This “strangely” coincides with the solution we just got from the geometric sequence.

This is simpler ad faster. Here is the corresponding code.

function ShortCatchUpTime(D, PV, FV)

{

    var d = parseFloat(D);

    var pv = parseFloat (PV);

    var fv = parseFloat (FV);

    return d / (pv - fv);

}

The code above, for both the iterative solution and the algebraic solution are actually for a larger class of problems.  In our original problem the student’s velocity (speed) is 1 mph. In the code it may be anything as long as it is less than the pursuer’s velocity. As long as PV > FV, the pursuer will catch up. Here is the really general formula:

T = D / (PV – FV)

Finally, let’s run the program for each of the pursuers.  It could not be worse. I know he’d rather be eaten alive than suffering through yet another math lesson.

See the code run? Select  “Catch Up Time” in www.mgsltns.com/games.htm The host is running on Unix, so the link is case sensitive.

That’s All Folks