Problem of the Month
Solution to Problem 8: May 2023

The following fact will come in handy later in the solution.

Fact 1: Let $p$ and $q$ be integers with $q\ne 0$ such that $p$ and $q$ have no positive divisors in common other than $1$. If $A$ and $B$ are distinct lattice points such that the line segment joining them has slope $\frac{p}{q}$, then the distance between $A$ and $B$ is at least $\sqrt{p^2+q^2}$.

1. 1. Below is a picture of the $\frac{4}{1}$ – loop (in blue) and the $\frac{-1}{4}$ – loop (in red) on $\mathbb{T}$.

      

      There are 17 intersection points. Remember that the two loops intersect at $(0,0)$, which is the same point as the other three vertices of $\mathbb{T}$.

      There are 17 small squares. Of these $17$, 9 are whole squares in the middle of $\mathbb{T}$, 4 are split into two pieces over the horizontal edges of $\mathbb{T}$, and 4 are split over the vertical edges of $\mathbb{T}$.

   2. Here is a picture of a $\frac{2}{3}$ – loop (in blue) and a $\frac{-3}{2}$ – loop (in red) on $\mathbb{T}$.

      

      There are 13 intersection points and 13 small squares.

   3. Here is a picture of a $\frac{4}{3}$ – loop (in blue) and a $\frac{-3}{4}$ – loop (in red) on $\mathbb{T}$.

      

      There are 25 intersection points and 25 small squares.

   4. Here is a picture of a $\frac{1}{1}$ – loop (in blue) and a $\frac{-1}{1}$ – loop (in red) on $\mathbb{T}$.

      

      There are 2 intersection points and 2 small squares. Here the squares are harder to see, since both of them pass through the edges of $\mathbb{T}$, passing over to the other side.

      It is not a coincidence that the number of small squares is equal to the number of intersection points in all four cases.

2. Consider the line of slope $\frac{p}{q}$ through the origin. By Fact 1, $(q,p)$ is the lattice point in the first quadrant that is closest to the origin. Therefore, there are no lattice points on $L_{q,p}$ other than its endpoints. To illustrate the idea in this solution, the diagram below shows $L_{5,11}$ along with every unit lattice square through which it passes.

   

   The $\frac{11}{5}$ – loop continues to wrap around $\mathbb{T}$ until it reaches a corner again. Because of how $\mathbb{T}$ behaves, we can think of the $\frac{11}{5}$ – loop as the result of overlaying all of the unit lattice squares in the diagram above on top of each other. Indeed, if the blue line reaches the top of the square, it jumps to the bottom with the same $x$-coordinate and continues with the same slope. This means that after it jumps, what the line does in $\mathbb{T}$ is the same as what it does as it continues into the adjacent unit lattice square.

   This is true in general. So the number of line segments in the $\frac{p}{q}$ – loop is equal to the number of unit lattice squares that $L_{q,p}$ intersects. By "intersects" we mean that the line passes through some part of the interior of the square and not just a vertex.

   Therefore, to count the line segments in the $\frac{p}{q}$ – loop, we can count the unit lattice squares through which $L_{q,p}$ passes. Line segment $L_{q,p}$ begins in $T$ and passes into a new unit lattice square exactly when it crosses either a vertical line with equation $x=a$ for some integer $a$ or a horizontal line with equation $y=b$ for some integer $b$. Since $L_{q,p}$ passes through no lattice points other than its endpoints, it will never cross such a vertical and a horizontal line at the same time. Since $L_{q,p}$ starts at $(0,0)$ and ends at $(q,p)$, it must cross $q-1$ such vertical lines and $p-1$ such horizontal lines. Adding one to account for the unit square from which it originates, this means there are $(p-1)+(q-1)+1=p+q-1$ line segments in the $\frac{p}{q}$ – loop. For the $\frac{11}{5}$ – loop, this gives $11+5-1=15$ line segments. By counting, you can verify that there are indeed $15$ unit lattice squares in the diagram above. If you carefully draw the $\frac{11}{5}$ – loop, you will see that there are $15$ segments.

3. Since $p$ and $q$ are positive, $\frac{p}{q}$ is positive. Suppose $f(x)=\frac{p}{q}x+b$ is a $\frac{p}{q}$ – lattice line that intersects $T$. Then we must have $b\le 1$, otherwise $T$ would be entirely below the graph of $f(x)$ (remember, its slope is positive). Additionally, we must have that $f(1)\ge 0$, otherwise $T$ would be completely above the graph of $f(x)$.

   The inequality $f(1)\ge 0$ is equivalent to $\frac{p}{q}+b\ge 0$, or $-\frac{p}{q}\le b$. Combining with $b\le 1$, we get $-\frac{p}{q}\le b\le 1$, which we will write as $-\frac{p}{q}\le b\le \frac{q}{q}$.

   So far, we have not used the fact that $f(x)$ contains at least one lattice point. Suppose $f(x)$ passes through some lattice point $(u,v)$. That is, $u$ and $v$ are integers and $f(u)=v$. Then $v=\frac{up}{q}+b$ which can be rearranged to get $b=\frac{vq-up}{q}$. This implies that there is some integer $a$ for which $b=\frac{a}{q}$. Substituting into $-\frac{p}{q}\le b\le \frac{q}{q}$, we get $$-\frac{p}{q}\le \frac{a}{q}\le \frac{q}{q}$$ which is equivalent to $-p\le a\le q$. There are exactly $p+q+1$ integers $a$ that satisfy these inequalities, so there are $p+q+1$ $\frac{p}{q}$ – lattice lines that intersect through $T$.

   Before moving on, we make the observation that two of the $\frac{p}{q}$ – lattice lines that intersect $T$ only pass through the vertices $(0,1)$ and $(1,0)$. This means there are actually $p+q-1$ $\frac{p}{q}$ – lattice lines that pass through the interior of $T$.

4. Since $p\ne 0$ and $q\ne 0$, the loops are neither horizontal nor vertical. Therefore each of the small squares has a unique left-most vertex, which is the vertex with the smallest $x$-coordinate. Each of the small squares has exactly one left-most vertex, and every point of intersection is the left-most vertex of exactly one square. This means that the number of intersection points is equal to the number of squares.

   Note that this lends some credibility to counting the four vertices as one intersection point. See, for example, the $\frac{3}{1}$ and $\frac{-1}{3}$ loops from the problem statement. In that example, the square labelled by $1$ is split into two pieces, and its leftmost vertex is represented by all four vertices of $T$. It might be useful to think about this for a moment before moving on.

5. Since $p$ and $q$ are positive, $-\frac{q}{p}$ is negative. Suppose $f(x)=-\frac{q}{p}x+b$ is a $-\frac{q}{p}$ – lattice line that intersects $L_{q,p}$. Since the slope of $f(x)$ is negative, we must have $b\ge 0$. Otherwise, $L_{q,p}$ would be entirely above the graph of $f(x)$.

   For similar reasoning, we also require that $f(q)\le p$, which means $-\frac{q^2}{p}+b\le p$. This can be rearranged to $b\le \frac{p^2+q^2}{p}$. Combining with $b\ge 0$ gives $0\le b\le \frac{p^2+q^2}{p}$. By essentially the same argument that was used in the solution to part (c), $b$ must take the form $\frac{a}{p}$ for some integer $a$. Therefore, we have $$\frac{0}{p}\le \frac{a}{p}\le \frac{p^2+q^2}{q}$$ and there are exactly $p^2+q^2+1$ integers $a$ with this property. These lines are all different and all intersect $L_{q,p}$, so the answer is $p^2+q^2+1$.

   Before moving on, we note that the lines of slope $-\frac{q}{p}$ that pass through $(0,0)$ and $(q,p)$ are $-\frac{q}{p}$ – lattice lines that intersect $L_{q,p}$. Therefore, there are $p^2+q^2+1-2=p^2+q^2-1$ points of intersection of $-\frac{q}{p}$ – lattice lines with $L_{q,p}$, excluding the endpoints. We will refer to this set of $p^2+q^2-1$ points several times in the solution to part (f), so we will denote it by $X$ for convenience.

6. Let $Y$ be the set of intersection points of the $\frac{p}{q}$ – loop with the $\frac{-q}{p}$ – loop, other than the point represented by the four corners of $\mathbb{T}$. We will show that every point in $X$ corresponds to exactly one point in $Y$, thereby showing that $X$ and $Y$ have the same number of elements. Since there are $p^2+q^2-1$ points in $X$, if we include the point in $\mathbb{T}$ represented by the corners, this will show that the loops have exactly $p^2+q^2$ intersection points in $\mathbb{T}$. By part (d), this will show that the loops divide $\mathbb{T}$ into $p^2+q^2$ small squares.

   The rest of the solution is devoted to showing that $X$ and $Y$ have the same number of elements. We will use the following fact several times. Its proof is not included.

   Fact 2: If an $m$ – lattice line is translated $a$ units to the left and $b$ units to the right for some integers $a$ and $b$, then the line obtained is also an $m$ – lattice line.

   We first observe that every line segment in the $\frac{p}{q}$ – loop is part of some $\frac{p}{q}$ – lattice line. To see why this is true, consider the solution to part (c). It was discussed there that the line segments of the $\frac{p}{q}$ – loop can be obtained by overlaying on $T$ the unit lattice squares through which $L_{q,p}$ passes. For each such unit lattice square, there are integers $a$ and $b$ so that the square can be translated $a$ units to the left and $b$ units down in order to land on $T$. Therefore, if we translate $L_{q,p}$ $a$ units to the left and $b$ units down, it will land exactly on the segment of the $\frac{p}{q}$ – loop in question. $L_{q,p}$ is part of a $\frac{p}{q}$ – lattice line, so by Fact 2 above, we have shown that every line segment in the $\frac{p}{q}$ – loop is part of some $\frac{p}{q}$ – lattice line.

   By part (b), there are $p+q-1$ segments in the $\frac{p}{q}$ – loop. By the remark at the end of the solution to part (c), there are $p+q-1$ $\frac{p}{q}$ – lattice lines that pass through the interior of $T$. Each of the segments in the $\frac{p}{q}$ – loop is in the interior of the square. We conclude that the segments of the $\frac{p}{q}$ – loop are exactly the parts of $\frac{p}{q}$ – lattice lines that pass through the interior of $T$.

   By very similar reasoning, we can also conclude that the $\frac{-q}{p}$ – loop is made precisely of the segments of $-\frac{q}{p}$ – lattice lines that pass through the interior of $T$.

   Consider a point $(u,v)$ in $X$ and suppose it is inside the unit lattice square with vertices $(a,b)$, $(a+1,b)$, $(a+1,b+1)$, and $(a,b+1)$. Let $f(x)$ be the $-\frac{q}{p}$ – lattice line that intersects $L_{q,p}$ at $(u,v)$. The point $(u-a,v-b)$ is in $T$. If we translate $f(x)$ and $L_{q,p}$ to the left by $a$ units and down by $b$ units, the resulting lines will intersect at $(u-a,v-b)$. By Fact 2, translating $f(x)$ in this way results in a $-\frac{q}{p}$ – lattice line and translating $L_{q,p}$ results in a $\frac{p}{q}$ – lattice line. By the previous argument, these will be segments of the $\frac{-q}{p}$ and $\frac{p}{q}$ loops, respectively. Therefore, $(u-a,v-b)$ is a point of intersection of the two loops. This gives a natural way to translate points of $X$ to points in $Y$. In symbols, we send $(u,v)$ to $(u-\lfloor u\rfloor ,v-\lfloor v\rfloor )$.

   Suppose that $(u,v)$ and $(x,y)$ are two different points in $X$. If these points are in different unit lattice squares, then when they are translated to $T$, they will end up on different line segments of the $\frac{p}{q}$ – loop, so they cannot possibly be translated to the same point in $Y$. If they are in the same unit lattice square, then they will be translated to the left and down by exactly the same amount, so they will end up in different places in $T$. Either way, we can conclude that different points in $X$ are sent to different points in $Y$ by the rule described in the previous paragraph.

   Suppose $(u,v)$ is a point in $Y$. This point is on some line segment of the $\frac{p}{q}$ – loop, and we have argued earlier that these segments come from translating unit lattice squares through which $L_{q,p}$ passes (and taking the parts of $L_{q,p}$ along for the ride). Suppose the segment on which $(u,v)$ lies comes from the unit lattice square with vertices $(a,b)$, $(a+1,b)$, $(a+1,b+1)$, and $(a,b+1)$ and call this square $S$. The point $(a+u,b+v)$ is in $S$ and lies on $L_{q,p}$.

   We showed earlier that every line segment on the $\frac{-q}{p}$ – loop is part of some $-\frac{q}{p}$ – lattice line. Let $f(x)$ be the $-\frac{q}{p}$ – lattice line on which $(u,v)$ lies. If we translate $f(x)$ to the right by $a$ units and up by $b$ units, the result will be a new $-\frac{q}{p}$ – lattice line by Fact 2. Moreover, this line will pass through $(u+a,v+b)$, which also lies on $L_{q,p}$. Therefore, $(u+a,v+b)$ is a point in $X$ that is inside the square $S$. If we translate $(u+a,v+b)$ to the left by $a$ and down by $b$, it will be sent to $(u,v)$ by construction.

   We have shown that each of the $p^2+q^2-1$ points in $X$ corresponds to exactly one point in $Y$. As explained earlier, if we consider the four corners of $\mathbb{T}$ as one intersection point, then we get a total of $p^2+q^2$ intersection points of the two loops.

   As mentioned in the problem, we are taking for granted that the squares all have the same size. This means that each of them has an area of exactly $\frac{1}{p^2+q^2}$. Referring back to the Euclid problem from the beginning, we were dealing with the situation where $p=3$ and $q=1$, so the area of the squares is $\frac{1}{3^2+1^2}=\frac{1}{10}$.