Is there any elementary solution for this problem on colored interval?

Question

The problem is as following.

Assume $m,n$ are two coprime odd numbers, consider the interval $[0,mn]$. We cut the interval by $m,2m,\ldots,(n-1)m$ and $n, 2n,\ldots, (m-1)n$ into $m+n-1$ pieces of small intervals. And we color them from left to right by black-and-white periodically and black first. The question is to show $$(\textrm{the length of black})-(\textrm{the length of white})=1$$ For example, if $m=3,n=5$, $$\begin{array}{c*{31}}0 &&&&&& 3 &&&&&& 6 &&&&&& 9 &&&&&& 12 &&&&&& 15 \\ \mid & \blacksquare && \blacksquare &&\blacksquare &\mid & \square && \square & \mid & \blacksquare & \mid & \square&& \square&& \square &\mid & \blacksquare &\mid & \square&& \square&\mid & \blacksquare&& \blacksquare&& \blacksquare & \mid \\ 0 &&&&&&&&&& 5 &&&&&&&&&& 10 &&&&&&&&&& 15\end{array} $$The length of black is $8$ and the length of white is $7$.

In my blog, I presented two "analytic" solutions, which are both due to Liu Ben, using the trick of exponential sums. They are so nice in the sense of "analytic" approach.

At the end of the post, I came up a "elementary" solution I want to explain more precisely here.

Consider a billiards table of size $m\times n$, and struck the billiard from one of corners on $45^{\circ}$. Every time the ball knockes the boundary, it changes its color. Then $$(\textrm{the length of black interval})=\sqrt{2}\times (\textrm{the length of orbit of black ball})\qquad {(*)}$$ and $$(\textrm{the length of white interval})=\sqrt{2}\times (\textrm{the length of orbit of white ball})\qquad {(**)}$$ So it suffices to count the length of the grid at the direction of $\diagup$ and $\diagdown$, which is not difficult to compute.

But in this solution, it is not easy to explain why $(*)$ and $(**)$ holds, though we know it from "life experience". And I think there may be some more elementary method to solve this problem. So my questions are

• Is there any elementary solutions to this problem?
• Is there any "strict process" for the billiard problem ?
• Moreover, although I learnt it no more than 1 mouth ago, I think it is so genius that it must be classical and discovered by ancients. So are there any reference for this problem ?

Answer 1

Draw the large square $Q:=[0,nm]\times[0,mn]$ in the integer lattice. Draw $n-1$ vertical dividers horizontally $m$ apart and $m-1$ horizontal dividers vertically $n$ apart. The square $Q$ is then divided into $nm$ rectangles $R_{jk}$, each consisting of $mn$ lattice squares. Let $\ell$ be the diagonal of $Q$ connecting $(0,0)$ with $(nm,mn)$. This $\ell$ is divided into $n$ equal parts by the vertical dividers and into $m$ equal parts by the horizontal dividers. Therefore we can consider $\ell$ as a copy of the long horizontal line in the first figure of the question. Whenever $\ell$ crosses a divider line it enters a new rectangle $R_{jk}$. These $m+n-1$ rectangles are colored red in the figure. Note that in addition $\ell$ is a diagonal of exactly $nm$ unit squares of the lattice.

We now copy these red rectangles together with the parts of $\ell$ in them into a new $(m\times n)$-rectangle $R$. We then shall see a family of $45^\circ$-segments $\sigma_i$ in $R$. Looking at this second figure it is still possible to follow the original $\ell$: Whenever a $\sigma_i$ hits a boundary edge $e\subset R$ the next segment in the original $\ell\subset Q$ begins at the corresponding point on the parallel edge $e'\subset R$, until we finally arrive at $(m,n)$. From ${\rm gcd}(m,n)=1$ it follows that the segments $\sigma_i$ are disjoint, and as they make up exactly $mn$ unit square diagonals we obtain the picture on the right below.

In order to discuss the coloring of the $\sigma_i$ color the unit squares of $R$ checkerboard like with black squares at the vertices of $R$. Since $m$ and $n$ are odd it turns out that the $\sigma_i$ through black unit squares will automatically be colored black and the $\sigma_i$ through white unit squares will be colored white. Now there is one more black square than there are white squares, and we are done.

Answer 2

Here is a more formal realization of the billiard ball argument.

Write down a sequence of $mn$ ordered pairs where:

• the first coordinate first follows the sequence $1, 2, \dots, m$ then the sequence $m, m-1, \dots, 1$ then continues alternating these two sequences.
• the second coordinate first follows the sequence $1, 2, \dots, n$ then the sequence $n, n-1, \dots, 1$ then continues alternating these two sequences.

Intuitively, an ordered pair $(x,y)$ in the $i^{\text{th}}$ position means that in the $i^{\text{th}}$ step, the billiard ball is traversing the square at coordinates $(x,y)$.

We color an ordered pair $(x,y)$ black if $x+y$ is even and white if $x+y$ is odd. Then we can see that ordered pairs switch color precisely at points where the first sequence goes $m, m$ or $1,1$, and at points where the second sequence goes $n, n$ or $1,1$. These are points where the billiard ball ricochets, and also points where we go from one interval to another.

So to get the result, we need to show that each pair $(x,y) \in \{1,2,\dots,m\} \times \{1,2,\dots,n\}$ appears exactly once: that the billiard ball passes over every square of the grid. This can be done, but it's slightly annoying.

(Then we'd need to count the number of black pairs and white pairs in this grid. I do this below.)

---

The following approach is a simpler argument along the same lines. Write down the sequence $(i \bmod m, i \bmod n)$ for $i=0,1,\dots,mn-1$. Once again, color an ordered pair $(x,y)$ black if $x+y$ is even and white if $x+y$ is odd.

(This corresponds to a "teleporting" ball which, when it reaches an edge of the table, teleports to the opposite edge and continues moving in the same direction.)

Now we only have to show three things:

First, the color of ordered pairs in the sequence describes exactly the colors of the intervals. This is because $(i \bmod m, i \bmod n)$ and $(i+1\bmod m, i+1\bmod n)$ have the same color if there is "no carry": if we add $1$ to both coordinates. Parity only switches when we go from $m-1$ to $0$ in the first coordinate or $n-1$ to $0$ in the second.

Second, each possible ordered pair $(x,y)$ occurs exactly once. This is precisely the statement of the Chinese Remainder Theorem.

Third, the number of pairs $(x,y)$ where $x+y$ is even is off by $1$ from the number of pairs $(x,y)$ where $x+y$ is odd. To do this, pair them off:

• For any $x$-coordinate, pair off $(2k-1,x)$ and $(2k,x)$ for $k=1,2,\dots,\frac{n-1}{2}$. These have opposite colors.
• Pair off $(0,2k-1)$ and $(0,2k)$ for $k=1,2,\dots,\frac{m-1}{2}$. These have opposite colors.
• The only unpaired number is $(0,0)$, which is black, so the number of black pairs is one more than the number of white pairs. This finishes the proof.