0
$\begingroup$

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?

2 Answers 2

4

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.)

  • 0
    @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.2011-12-04
1

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.

  • 0
    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)2011-12-04