Problem 1993

Suppose that $x = \frac{p}{q}$ where $p, q$ are positive integers with $p < q$ and $\gcd(p, q) = 1$. Suppose that the hare takes $p$ minutes for a full turn about the tower. Then the tortoise takes $q$ minutes for a full turn. They will meet again at the same vertex $pq$ minutes when the hare will make $q$ full turns and the tortoise will make $p$ full turns. In particular, the hare will overtake the tortoise exactly $k = q - p$ times taking into account the start of the race but not the end of the race as an overtake.

The overtakes should occur at minutes $0, \frac{pq}{k}, \frac{2pq}{k}, \dots, \frac{(k-1)pq}{k}$. In those minutes the tortoise would have made $0, \frac{p}{k}, \frac{2p}{k}, \dots, \frac{(k-1)p}{k}$ full turns about the tower. Since $(p, q) = 1$, then $(p, k) = 1$ and therefore at these meeting points the tortoise would have in some order made some full turns about the tower plus another $0, \frac{1}{k}, \frac{2}{k}, \dots, \frac{k-1}{k}$ fraction of a full turn.

Case 1: Suppose $k$ is odd. We claim that the $0, \frac{1}{k}, \frac{2}{k}, \dots, \frac{k-1}{k}$ fractions of a full turn correspond, in some order to $0, \frac{1}{k}, \frac{2}{k}, \dots, \frac{k-1}{k}$ fractions of a side. To see this, given $i = 0, 1, \dots, k-1$, note that if $\frac{j-1}{4} \le \frac{i}{k} < \frac{j}{4}$ for some $j = 1, 2, 3, 4$ then the meeting point is on the $j$-th side at a fraction of $4(\frac{i}{k} - \frac{j-1}{4}) = \frac{4i-k(j-1)}{k}$ of the side. No two such fractions can be equal. Indeed if
$$\frac{4i - k(j - 1)}{k} = \frac{4i' - k(j' - 1)}{k}$$
then $4(i' - i) = k(j' - j)$ and since (for $i' > i$ say) $j' - j \in \{1, 2, 3\}$, then $2|k$, a contradiction.

Now if the hare meets the tortoise at a fraction of $\frac{i}{k}$ of the side, then the tortoise can see the hare for $\frac{k-i}{k} \cdot \frac{p}{4}$ minutes. I.e. the time it takes the hare to reach the endpoint of the side. Furthermore, if $i$ is large enough, it is possible for the tortoise to also reach the endpoint before the hare reaches the next endpoint and thus see the hare for a little bit more. The tortoise takes $\frac{k-i}{k} \cdot \frac{q}{4}$ minutes to reach the endpoint. The hare takes $\frac{2k-i}{k} \cdot \frac{p}{4}$ minutes in total to reach the next endpoint. So the tortoise can see the hare for another
$$\frac{(2k - i)p - q(k - i)}{4k} = \frac{p}{4} + \frac{(p - q)(k - i)}{4k} = \frac{p + i - k}{4}$$
minutes, provided that this is non-negative. So the total meeting time is
$$\frac{p}{4} \left( \frac{1}{k} + \frac{2}{k} + \dots + \frac{k}{k} \right) + \frac{1}{4} (1 + 2 + \dots + (p-1)) = \frac{p(k+1)}{8} + \frac{(p-1)p}{8} = \frac{pq}{8}$$
minutes. So we need $x = \frac{1}{8}$ which is accepted as $k = 7$ is odd in this case.

Case 2: Suppose $k = 2r$ where $r$ is odd. We claim that the $0, \frac{1}{k}, \frac{2}{k}, \dots, \frac{k-1}{k}$ fractions of a full turn correspond, in some order to $0, 0, \frac{1}{r}, \frac{1}{r}, \dots, \frac{r-1}{r}, \frac{r-1}{r}$ fractions of a side. The proof is similar to Case 1 with the meeting points being at fractions $\frac{4i-k(j-i)}{k} = \frac{2i-r(j-i)}{r}$ of the sides. Two of these fractions are equal if and only if $4(i' - i) = k(j' - j)$ which (for $i' > i$ say) can occur when $j' = j + 2$ and $i' = i + r$.

If they meet at a fraction of $\frac{i}{r}$ of the side, the tortoise meets that hare for $\frac{r-i}{r} \cdot \frac{p}{4}$ minutes plus possibly another
$$\frac{(2r - i)p - q(r - i)}{4r} = \frac{p}{4} + \frac{(p - q)(r - i)}{4r} = \frac{p + 2i - 2r}{4}$$
minutes provided this is non-negative. So (noting that $p$ is odd in this case) the tortoise can see the hare for
$$\frac{2p}{4} \left( \frac{1}{r} + \frac{2}{r} + \dots + \frac{r}{r} \right) + \frac{2}{4} \left( 1 + 3 + \dots + (p-2) \right) = \frac{p(r+1)}{4} + \frac{(p-1)^2}{8}$$
minutes. This is equal to
$$\frac{p(2r + 2) + (p - 1)^2}{8} = \frac{p(q - p + 2) + (p - 1)^2}{8} = \frac{pq + 1}{8}$$
minutes. So we need
$$\frac{p}{q} = x = \frac{1}{8} + \frac{1}{8pq} \implies 8p^2 = pq + 1 \implies p = 1, q = 7.$$
Thus $x = \frac{1}{7}$ which is accepted since $k = 6 \equiv 2 \pmod{4}$.

Case 3: Suppose $k = 4s$. Similarly to Cases 1 and 2, the $0, \frac{1}{k}, \frac{2}{k}, \dots, \frac{k-1}{k}$ fractions of a full turn correspond, in some order to $0, 0, 0, 0, \frac{1}{s}, \frac{1}{s}, \frac{1}{s}, \frac{1}{s}, \dots, \frac{s-1}{s}, \frac{s-1}{s}, \frac{s-1}{s}, \frac{s-1}{s}$ fractions of a side.
If they meet at a fraction of $\frac{i}{s}$ of the side, the tortoise meets that hare for $\frac{s-i}{s} \cdot \frac{p}{4}$ minutes plus possibly another
$$\frac{p}{q} = x = \frac{1}{8} + \frac{3}{8pq} \implies 8p^2 = pq + 3 \implies p|3$$
This gives the solutions $p = 1, q = 5$ and $p = 3, q = 23$ giving $x = \frac{1}{5}$ and $x = \frac{3}{23}$ which are both accepted.

If we run the process in reverse, the dynamics are the same except that the tortoise can see the hare at some time in the reversed process precisely if the hare could see the tortoise at the same time in the original process. From this observation, the proportion of the race for which the tortoise can see the hare is precisely half the proportion of the race for which the two runners are on the same side of the square. It suffices to show that this proportion is:

(a) $\frac{1}{4}$, when $p-q$ is odd;
(b) $\frac{1}{4} + \frac{1}{4pq}$ when $p-q$ is even but not divisible by 4;
(c) $\frac{1}{4} + \frac{3}{4pq}$ when $4 \mid p-q$.

The proof can then be completed exactly as in Solution 1 to get that $x = \frac{1}{8}, \frac{1}{7}, \frac{1}{5}, \frac{3}{23}$.

To streamline the argument, we assume that the square (always meaning the boundary) has side length $pq$ units, and that in a time-step, the tortoise moves $p$ units, and the hare moves $q$ units. Note that a runner can only be at the vertex of the square at the start or end of a step. We say that a vertex of the square is on the side of the square that lies clockwise from the vertex, and we refer to that as the side's associated vertex. So every point on the square is on exactly one 'side'.

Now, we index all points on the square by their distance from the vertex associated to the side containing that point. So each label occurs exactly four times. So, after $n$ steps of the process, we study the indices of T and H's current locations, which must have the form $(ap, bq)$ for $a \in \{0, 1, \dots, q-1\}$ and $b \in \{0, 1, \dots, p-1\}$. Thus the total distances travelled by T and H have the forms
$$ap + mpq, \quad bq + m'pq, \quad \text{respectively, } m, m' \in \mathbb{N}$$
which means that the number of steps $n$ satisfies
$$n = a + mq = b + m'p. \qquad (1)$$
T and H are on the same side of the square precisely when $4 \mid m' - m$ and are on the same side or on opposite sides of the square precisely when $2 \mid m' - m$, equivalently when $2 \mid m' + m$.

Now, after $pq$ steps, both runners are again at a vertex of the square. We return to the case distinction introduced earlier.

(a) Here, the two vertices are adjacent. Therefore, for any time $0 \le t < pq$, T and H are on the same side of the square at exactly one of the times $\{t, t + pq, t + 2pq, t + 3pq\}$. It follows that across the entire run, T and H will be on the same side exactly $\frac{1}{4}$ of the time.

(c) Here, the two vertices are the same. It then suffices to study the proportion of times the runners are on the same side before timestep $pq$. Note that by the Chinese Remainder Theorem, every $(a, b) \in [0, q-1] \times [0, p-1]$ occurs exactly once as the indexing of the runners' locations $(ap, bq)$ for $n = 0, \dots, pq-1$. But, from (1),
$$a - b = m'p - mq \equiv (m' - m)p \pmod{4}.$$
Since $p$ is odd, $4 \mid m' - m$ precisely if $4 \mid a - b$. So it suffices to enumerate
$$K(p, q) := \left| \left\{ (a, b) \in [0, q-1] \times [0, p-1] : 4 \mid a-b \right\} \right|.$$
By considering the number of times each congruence class appears for $a$ and for $b$, we find, for $p \equiv q \equiv 1$:
$$K(p, q) = \frac{p+3}{4} \times \frac{q+3}{4} + 3 \left( \frac{p-1}{4} \times \frac{q-1}{4} \right),$$
and for $p \equiv 1, q \equiv 3$,
$$K(p, q) = \frac{p+3}{4} \times \frac{q+1}{4} + 2 \left( \frac{p-1}{4} \times \frac{q+1}{4} \right) + \frac{p-1}{4} \times \frac{q-3}{4}.$$
In both cases, a calculation shows $\frac{K(p,q)}{pq} = \frac{1}{4} + \frac{3}{4pq}$, with an obvious symmetric argument for $p \equiv 3, q \equiv 1$.