# Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is logical since we are dealing with cycles).

However, I cannot find any proof that works for a general cycle of this format:

I am trying to prove two things.

First, if a cycle does exist, and you advance the tortoise one node each unit of time but the hare two nodes each unit of time, then they will eventually meet.

Second, when they meet the tortoise will be $n$$\alpha away from the start of the sequence (where \alpha is the loop length) and also n$$\alpha$ away from the hare.

• This is one of the early exercises in Knuth The Art of Computer Programming vol. 1. There may be a solution in Appendix A. – MJD Aug 30 '14 at 0:56
• It's exercise 6 in section 3.1 (page 7) of Knuth volume 2, not volume 1. There is a solution in Appendix A, on page 539. – MJD Aug 30 '14 at 3:20
• For showing that they eventually must meet, consider the first step at which the tortoise enters the loop. If the hare is on that node, that is a meeting and we are done. If the hare is not on that node, note that on each subsequent step the distance the hare is ahead of the tortoise increases by one, which means that since they are on a loop the distance that the hare is BEHIND the tortoise decreases by one. Hence, at some point the distance the hare is behind the tortoise becomes zero and the meet. – tzs Nov 25 '17 at 22:48

If the preliminary tail is length $T$ and the cycle is length $C$ (so in your picture, $T=3$, $C=6$), we can label the tail nodes (starting at the one farthest from the cycle) as $-T, -(T-1),..., -1$ and the cycle nodes $0, 1, 2, ..., C-1$ (with the cycle node numbering oriented in the direction of travel).

We may use the division algorithm to write $T=kC+r$ where $0\le r<C$.

After $T$ clicks the tortoise is at node $0$ and the hare is at node $r$ (since hare has gone $2T$ steps, of which the first $T$ were in the tail, leaving $T$ steps in the cycle, and $T\equiv r \pmod{C}$).

Assuming $r\ne 0$, after an additional $C-r$ clicks, the tortoise is at node $C-r$; and the hare is at node congruent $\pmod{C}$ to $r+2(C-r)=2C-r\equiv C-r \pmod{C}$. Hence both critters are at node $C-r$. [In the $r=0$ case, you can check that the animals meet at the node $0$.]

The distance from the start at this meeting time is thus $T+C-r=(kC+r)+C-r=(k+1)C$, a multiple of the cycle length, as desired. We can further note, this occurrence is at the first multiple of the cycle length that is greater than or equal to the tail length.

• They're on the same node, so in a sense their distance is $0$; however, at that time we can say that Tortoise has gone $(k+1)C$ steps and hare has gone twice as many steps, namely $2(k+1)C$ so the difference in their distance traveled is indeed $(k+1)C$. – paw88789 Aug 30 '14 at 3:46
• If, as you say, they are now moving one step at a time (with the tortoise back at $-T$), then in $T$ steps, the tortoise will be at $0$ (start of cycle). Meanwhile, the hare, also going one step at a time will go from $C-r$ to $C-r+T= C-r+(kC+r)=(k+1)C\equiv 0 \pmod{C}$; and so hare arrives simultaneously at the start of the cycle. – paw88789 Aug 30 '14 at 4:09
• @RohitSinghRathore If $r=0$, they meet after $T$ steps. They don't have to go the additional $C-r$ steps. – paw88789 May 28 '17 at 9:26
• Such a lovely proof! Loved your numbering scheme. I have one question, is there any intuition behind why C - r steps are required for them to meet? – Vikas Tikoo Apr 27 '19 at 6:29
• @Vikas Tikoo Thanks. And to answer your question: Because when tortoise lands on $0$, starting the cycle, hare is on node $r$ in the cycle. So hare is $r$ ahead of tortoise in the cycle. But that also means that hare is $C-r$ behind tortoise. Hare gains $1$ step for each click of time. So it takes $C-r$ clicks for the catch. – paw88789 Apr 27 '19 at 13:26

This can be generalized a little, to hare step sizes $$>2$$ and to the tortoise and hare not necessarily starting on the same node. All step sizes $$>2$$ work if they start on the same node. If they start on different nodes then only a step size of 2 is guaranteed to work no matter what the cycle length.

Let $$T =$$ the number of nodes before the start of the cycle. Let $$C =$$ the length of the cycle. Let $$S =$$ the step size of the hare (2 for the problem as given).

After $$n$$ iterations, the tortoise has moved $$n$$ nodes, and the hare $$nS$$. The hare and tortoise are on the same node whenever $$n \geq T$$ and $$n-T \equiv nS-T$$ mod $$C$$. So we are looking for solutions of $$n(S-1) \equiv 0$$ mod $$C$$ with $$n \geq T$$.

When $$S=2$$ as in the problem as given, this is simply $$n\equiv0$$ mod $$C$$. This happens exactly when $$n$$ is a multiple of $$C$$.

When $$S>2$$ it also happens on every multiple of $$C$$, but might also happens at other times if $$S-1$$ and $$C$$ are not relatively prime.

That covers starting on the same node. For starting on different nodes, let $$h =$$ the starting node of the hare, and $$t=$$ the starting node of the tortoise.

Then we need to solve $$n(S-1) \equiv t-h$$ mod $$C$$ instead of $$n(S-1) \equiv 0$$, subject to $$t+n\geq T$$.

When $$S=2$$, that is $$n\equiv t-h$$ mod $$C$$, which has $$n = t-h+kC$$ as solutions for all integers $$k$$. When $$S>2$$ it is possible that $$n(S-1)\equiv t-h$$ mod $$C$$ has no solutions.

Actually, you can even generalize some more, letting the tortoise have a step size $$>1$$. As long as the tortoise and hare start on the same node, and the hare has a larger step size than the tortoise, it will still work. If $$S_h$$ is the hare's step size and $$S_t$$ is the tortoise's step size, then instead of $$n(S-1)\equiv 0$$ mod $$C$$ we have to solve $$n(S_h-S_t)\equiv 0$$ mod $$C$$.