# Proof for circular traversal problem

Suppose you are given a circle that is subdivided into N parts. Two bugs race around the circle at distinct, discrete speeds that are less than N parts per time increment. They start at any position on the circle. Prove one of the cases to be true:

1. For any speeds, given infinite time, the bugs will eventually end up on the same part of the circle at the same time.
2. There are a set of speeds that the bugs will never reach the same spot, given infinite time.

I've written out the relation:

$$(n_i + s_i*t) \mod(N) = (n_j + s_j*t) \mod(N)$$

but haven't gotten much further than this.

Although the question doesn't explicitly say it's only dealing with integer quantities, it's implicitly specified by the question text talking about "N distinct parts", "distinct, discrete speeds", and "time increment". Also, the initial relation using modulos implies this as normally they're only used in this way with integers. However, if time is allowed to be any real value, then for any different speed, the $$2$$ bugs will always eventually cross paths when the faster one overtakes the slower one. The rest of this answer assumes only integers are involved.

Your stated relation is the right way to start the solution. Using slightly different variables, let $$n_1, n_2$$ be the starting positions, and $$s_1, s_2$$ be the speeds of the $$2$$ bugs. Then for them to meet up at some time $$t$$ requires that

$$n_1 + s_1 \times t \equiv n_2 + s_2 \times t \pmod N \implies n_1 - n_2 + (s_1 - s_2) \times t \equiv 0 \pmod N \tag{1}\label{eq1}$$

In particular, this means that for some $$k \in \mathbb{Z}$$

$$n_1 - n_2 + (s_1 - s_2) \times t = kN \tag{2}\label{eq2}$$

Let $$d = \gcd(s_1 - s_2, N)$$. Since $$d \mid kN$$ and $$d \mid (s_1 - s_2) \times t$$, this means $$d \mid n_1 - n_2$$ also. If this is not true, then the bugs will never be at the same place at the same time. Thus, the given case $$2$$ is the one which is true.

An example of this is if $$N = 10, n_1 = 4, n_2 = 1, s_1 = 3, s_2 = 1$$. Then, $$d = 2 = \gcd(3 - 1, 100)$$ and $$n_1 - n_2 = 4 - 1 = 3$$, with $$2 \not\mid 3$$ (in particular, the LHS will always be odd and the RHS always even).

• I see. This makes sense, but how does one strictly interpret equation 2? It seems that in equation 2 you have 2 unknowns ($t$ and $k$). I was thinking about solving for $t$ given a value of $k$, but this seems wrong, as not all $k$ have a valid solution for t in the range of real numbers. Is there a way to analytically solve for the time required? Does the solution simply span the space of all whole number combinations of $k$ and $t$, since that is the way the problem is defined? Aug 6, 2019 at 15:10
• @VictorM I assume here, and I perhaps should have explicitly mentioned, that everything being dealt with, including $t$, are integers. This is based on the question text talking about "N distinct parts", "distinct, discrete speeds", and "time increment", not to mention your relation with modulo which is normally only used with integers in that fashion. If $t$ is allowed to range through all real numbers, then with distinct speeds, the faster one will eventually pass the slower one, so the $2$ bugs will always be at the same place at the same time eventually. Aug 6, 2019 at 15:26
• @VictorM As for solving (2), first rearrange it to be something like "$kN + (s_2 - s_1) \times t = n_1 - n_2$. Let $d = \gcd(N, s_2 - s_1)$, as I did in the answer. Next, Bézout's identity guarantees an equation of $aN + b(s_2 - s_1) = d$ for some integers $a,b$. You can determine initial $(a,b)$ using the Chinese Remainder Theorem. The set of all solutions is $(a + j(s_2 - s_1)/d, b - jN/d)$. Multiply these equations by $(n_1 - n_2)/d$ to get all possible solutions. Aug 6, 2019 at 15:36