Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading about an algorithm. For a part of it, to present the underlying logic uses the following analogy which I do not understand:

If two people run on a track and one of them runs with twice the speed of the other, they will meet at the start of the next round. Now if we assume that the QuickRunner had a head start of $k$ meters on a $n$ step round when will they meet? They will meet $k$ meters before the start of the next lap since QuickRunner would do $k+2(n-k)$ steps, and the slow one would have done $n-k$ steps. So both will be $k$ steps before the start of the loop.

I don't see why they would meet $k$ steps before the start of the loop.

Could you please help understand this?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

When SlowRunner has completed one lap, QuickRunner has completed two, and both are back at their original starting points, with QuickRunner $k$ metres ahead of SlowRunner. Say that QR passed SR $m$ metres before SR’s starting point. In the time that it takes SR to cover the $m$ metres to finish his lap, QR, moving twice as fast, will cover $2m$ metres. The first $m$ of those $2m$ will get him to SR’s starting point, and then he’ll go another $m$ metres beyond that. But we already saw that QR ends up at his original starting point, which is $k$ metres beyond SR’s starting point, so it must be that $m=k$. Thus, QR passed SR $k$ metres before SR’s starting point.

(In the version that you’re reading, the start of the loop is SR’s starting point, and steps is really metres.)

share|improve this answer
    
+1 by me.One point though.If QR meets SR m meters before SR's starting point, obviously QR will cover 2m meters and SR m meters.But how do you conclude that after the 2m meters QR ends up in his starting point?I lost you somewhere.Also if they had the same pace, but QR just had k meters head start, would the same conclusion apply?I.e. meet k meters before start? –  user384706 Dec 4 '11 at 19:47
    
@user384706: When SR has done one full lap and returned to his starting point, QR, running exactly twice as fast, must have covered two full laps and therefore returned to his starting point. No matter where you start, if you run a whole number of laps, you’ll end up back at your starting point. –  Brian M. Scott Dec 4 '11 at 19:54
    
Brian:Ok got it!So this applies assuming different speeds.What if they have the same speed and QR only has a head start of k meters? –  user384706 Dec 4 '11 at 20:01
    
@user384706: Then QR (who won’t really be quick!) will always be exactly $k$ metres ahead of SR. On the other hand, if QR is three times as fast as SR, he’ll overtake SR twice while SR runs one lap, and the second overtaking will occur $2k$ metres before SR’s starting point. –  Brian M. Scott Dec 4 '11 at 20:12

The explanation that you quote is not very helpful. Perhaps some of this is due to mistranslation $-$ has "yard" been translated into some foreign language (the one spoken by user384706), and then back-translated into "step"? Also, "round" should be "lap". But the worst problem is "the start of the next round" (or lap). Whose next lap? The whole point is that the Quick Runner runs two laps while the Slow Runner runs one lap. So "next lap" is meaningless.

Having said that, the easiest way to see the truth of the statement is to turn back time, and have the runners run backwards before the race starts, until they meet. This will happen $k$ yards before the starting line. So then set them running forwards again for 1 lap (resp. 2 laps), and they will meet at the same point, $k$ yards before the starting line.

Edited to add: Yards, steps, meters $-$ Srivatsan edited most (but not all) of the "steps" to "meters", so some of my first paragraph is obsolete.

share|improve this answer
    
+1.The analogy with running backwards was really helpful!I read it in English (I am not a native english speaker) and perhaps the writer also was not english because the things you point out also were confusing to me.Now if the QuickRunner just had k meters head start but both run with the same pace, would they still meet k meters before slow runner's lap? –  user384706 Dec 4 '11 at 19:55
    
@user384706: Perhaps you should think about that for a microsecond. The answer might occur to you :-) –  TonyK Dec 4 '11 at 20:24
    
Fair enough ;). It is just that the analogy is then carried over to pointers (in programming context) which can only have the same speed (talking in cpu cycles) –  user384706 Dec 4 '11 at 20:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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