Proof of Floyd Cycle Chasing (Tortoise and Hare)

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

Say there are $l$ elements before the loop starts and $n$ elements in the loop. And $e_l$ is the first element of the loop which is seen when we traverse the linked-list. When we will say "an element $x$ steps ahead of $e$", that will mean, we can reach that element taking $x$ steps from $e$.

Now, when Tr (tortoise) reaches $e_l$, after $l$ iterations, say, Hr (Hare) is $x$ steps ahead of $e_l$. Since Hr has taken total $2l$ steps by then ($l$ steps prior to the loop), so:

$x = l \bmod n$.

In each future iteration, Tr and Hr will progress by 1 and 2 steps respectively, and so each iteration will increase their "gap" by 1. So they will meet after $n-x$ further iterations, when their gap will become $x + (n-x) = n$.

So, till that meeting, Tr has taken total steps = (steps till $e_l$) + (further steps after $e_l$)

= $l + (n-x)$

= $l + n - l \bmod n$

= $n + (l- l \bmod n)$

= a multiple of $n$

Since Hr takes 2 steps in each iteration, so, till the meeting it must have taken double of the Tr's steps, again a multiple of $n$.

You may refer this article (written by me) for more information.