Problem of the Month
Solution to Problem 3: December 2023

For solutions to the original problem from the Canadian Intermediate Mathematics Contest, please refer to the solutions on our website.

We will start by presenting two general facts. It is worth spending some time digesting them before reading the rest of the solution.

Fact 1: For all positive integers \(m\) and \(n\) with \(m \leq n\), if the integer \(mn\) is not in Row \(n\), then there are positive integers \(a\) and \(b\) such that \(ab=mn\) and \(m < a \leq b < n\).

Fact 2: For all positive integers \(m\) and \(n\) with \(m \leq n\), if there are positive integers \(a\) and \(b\) such that \(ab=mn\) and \(m < a \leq b < n\), then the integer \(mn\) is not in Row \(n\).

1. Suppose \(k\) is a positive integer. If \(n\) is a positive integer with \(n \leq k\), then \(n^2-kn \leq 0\), and so \(n^2-kn\) is not in Row \(n\). Therefore, we might as well assume that \(n>k\) as we look for the largest \(n\) such that \(n^2-kn\) is not in Row \(n\).

   Assume now that \(n^2-kn=n(n-k)\) is not in Row \(n\). By Fact 1 with \(m=n-k\), there must be integers \(a\) and \(b\) such that \(ab=n(n-k)\) and \(n-k < a \leq b < n\).

   Because \(a\) and \(b\) are integers strictly between \(n-k\) and \(n\), there must exist integers \(x\) and \(y\) with \(1 < x\leq y < k\) such that \(a=n-y\) and \(b=n-x\). We are assuming that \(n^2-nk=ab\), so we can substitute to get \(n^2-nk = (n-y)(n-x)=n^2-(x+y)n+xy\). This can be simplified and rearranged to get \((x+y-k)n = xy\). The integers \(x\) and \(y\) are both positive, so \(xy\) is positive, which implies that \(x+y-k\) is positive so we can solve for

   \(n\) to get \(n=\dfrac{xy}{x+y-k}\).

   Now suppose \(x+y > k+1\) and consider the expression \(\dfrac{(x-1)y}{(x-1)+y-k} - \dfrac{xy}{x+y-k}\), which we can simplify as follows: \[\begin{align*} \dfrac{(x-1)y}{(x-1)+y-k} - \dfrac{xy}{x+y-k} &= \dfrac{(x-1)y(x+y-k) - (xy)(x+y-1-k)}{(x+y-k)(x+y-1-k)} \\ &= \dfrac{x^2y+xy^2-xyk-xy-y^2+yk - x^2y-xy^2+xy+xyk}{(x+y-k)(x+y-1-k)} \\ &= \dfrac{-y^2 +yk}{(x+y-k)(x+y-1-k)} \\ &= \dfrac{y(k-y)}{(x+y-k)(x+y-1-k)}\end{align*}\] Carefully considering the components of the fraction above, we have that \(y\) is a positive integer with \(y<k\), so the quantity \(k-y\) must be negative, and since \(x+y>k+1\), the quantities \(x+y-k\) and \(x+y-k-1\) are both positive. Therefore, the fraction at the end of the calculation above is negative, so we get that \[\dfrac{(x-1)y}{(x-1)+y-k} - \dfrac{xy}{x+y-k} < 0\] which implies that \(\dfrac{(x-1)y}{(x-1)+y-k} < \dfrac{xy}{x+y-k}\).

   We have shown that if \(x+y>k+1\), then the quantity \(\dfrac{xy}{x+y-k}\) can be made larger by decreasing \(x\) by \(1\). A similar argument shows that if \(x+y>k+1\), then the quantity gets larger when \(y\) is decreased by \(1\). Since \(n = \dfrac{xy}{x+y-k}\) and we seek the largest possible \(n\), we conclude that \(n\) can always be made larger by decreasing \(x+y\) by \(1\), provided \(x+y\) is larger than \(k+1\). Therefore, the maximum value of \(n\) must occur when \(x+y=k+1\).

   Note: It is possible (and essentially assured) that \(\dfrac{xy}{x+y-k}\) is not always an integer. However, since it is maximized when \(x+y=k+1\), which makes the denominator equal to \(1\), the maximum possible value of \(\dfrac{xy}{x+y-k}\) given the constraints on \(x\) and \(y\) happens to be an integer. Therefore, the maximum possible integer value of \(\dfrac{xy}{x+y-k}\) is the maximum possible value, which occurs when \(x+y=k+1\).

   Substituting \(x+y=k+1\) into \(n=\dfrac{xy}{x+y-k}\), we get \(n=xy\). Therefore, the task is to maximize \(xy\) subject to the conditions \(1 < x\leq y < k\) and \(x+y=k+1\).

   Substituting \(y=k+1-x\) into \(xy\), we get \(xy=x(k+1-x)=(k+1)x-x^2\). Since \(k\) is fixed, the expression \((k+1)x-x^2\) is a quadratic in \(x\) with a negative coefficient of \(x^2\). Therefore, it has a maximum value and it occurs when \(x=\dfrac{k+1}{2}\).

   We are looking for the maximum among integer values of \(x\), so if \(\dfrac{k+1}{2}\) is an integer, the maximum occurs exactly when \(x=\dfrac{k+1}{2}\). Since \(x+y=k+1\), this implies that \(y=\dfrac{k+1}{2}\) as well.

   Otherwise, the maximum will occur at the integer nearest \(\dfrac{k+1}{2}\). There is a tie between \(\dfrac{k+1}{2}-\dfrac{1}{2}=\dfrac{k}{2}\) and \(\dfrac{k+1}{2}+\dfrac{1}{2}=\dfrac{k+2}{2}\). Notice that the sum of these two possible values of \(x\) is \(\dfrac{k}{2}+\dfrac{k+2}{2}=k+1\), so one of the values must be \(x\) and the other must be \(y\). Since \(x\leq y\), we have that \(x=\dfrac{k}{2}\) and \(y=\dfrac{k+2}{2}\).

   Now to summarize what we have so far: if we assume that \(n^2-kn\) is not in Row \(n\), then \(n\) is no larger than \(\left(\dfrac{k+1}{2}\right)^2\) when \(k\) is odd and \(n\) is no larger than \(\dfrac{k}{2}\left(\dfrac{k+2}{2}\right) = \dfrac{k(k+2)}{4}\) when \(k\) is even. Note that when \(k=10\), we get \(\dfrac{10(12)}{4}=30\), which agrees with the answer to part (c) of the original problem.

   To finish the argument, we need to verify that \(\left[\left(\dfrac{k+1}{2}\right)^2\right]^2-k\left(\dfrac{k+1}{2}\right)^2\) is not in Row \(\left(\dfrac{k+1}{2}\right)^2\) when \(k\) is odd and that \(\left(\dfrac{k(k+2)}{4}\right)^2 - k\left(\dfrac{k(k+2)}{4}\right)\) is not in Row \(\dfrac{k(k+2)}{4}\) when \(k\) is even. We will only include the verification for when \(k\) is odd here. The verification when \(k\) is even is similar.

   Expanding and simplifying, we have \[\begin{align*} \left[\left(\dfrac{k+1}{2}\right)^2\right]^2-k\left(\dfrac{k+1}{2}\right)^2 &= \left(\dfrac{k+1}{2}\right)^2\left[\left(\frac{k+1}{2}\right)^2-k\right] \\ &= \left(\dfrac{k+1}{2}\right)^2\left[\frac{k^2+2k+1-4k}{4}\right] \\ &= \left(\dfrac{k+1}{2}\right)^2\left[\frac{k^2-2k+1}{4}\right] \\ &= \left(\frac{k^2-1}{4}\right)^2\end{align*}\] Now set \(n=\left(\dfrac{k+1}{2}\right)^2\), \(m=n-k\), and \(a=b=\dfrac{k^2-1}{4}\). It follows from the calculation above that \(mn=ab\). If we can show that \(m < a\leq b < n\), then we can apply Fact 2 to get that \(mn=n^2-kn\) is not in Row \(n\). Note that \(a=b\) by definition, so \(a\leq b\) is automatically true. Expanding gives \(n=\dfrac{k^2+2k+1}{4}\) and \(m=\dfrac{k^2-2k+1}{4}\), and it is easily checked that \[m = \dfrac{k^2-2k+1}{4} < \dfrac{k^2-1}{4} < \dfrac{k^2+2k+1}{4}=n\] for all \(k>1\). This means we can apply Fact 2 as long as \(k>1\), which completes the verification that the maximum value of \(n\) is exactly \(\left(\dfrac{k+1}{2}\right)^2\) when \(k\) is odd and \(k>1\).

   Finally, if \(k=1\), then \(n^2-kn=n^2-n\). By the original contest problem, \(n^2-n\) is in Row \(n\) for \(n\geq 3\). Also, \(n^2-n\) is in Row \(n\) when \(n=2\), but when \(n=1\), \(n^2-n=0\) is not in Row \(n\). Therefore, when \(k=1\), the maximum value of \(n\) for which \(n^2-kn\) is not in Row \(n\) is \(n=1\). Notice that \(\left(\dfrac{k+1}{2}\right)^2\) evaluates to \(1\) when \(k=1\), so the formula works even in this case.

2. Suppose \(m\) is a positive integer with \(m\leq p\) such that \(mp\) is not in Row \(p\). By Fact 1, there exist positive integers \(a\) and \(b\) such that \(mp=ab\) and \(m < a\leq b < p\). The equation \(mp=ab\) implies that \(ab\) is a multiple of \(p\), and since \(p\) is a prime number, \(a\) or \(b\) must be a multiple of \(p\). (This is by a fact often known as Euclid’s Lemma.) We also have that \(a\) and \(b\) are positive and both less than \(p\), so it is impossible for either of them to be a multiple of \(p\) because \(p\) is prime.

   We conclude that there are no positive integers \(m\) with \(m\leq p\) such that \(mp\) is not in Row \(p\). In other words, \(mp\) is in Row \(p\) for every positive integer \(m\) with \(m\leq p\).

   Since \(0\) is not in any row and \(0=0\times p\) is a multiple of \(p\), \(0\) is the largest integer \(m\) with the property that \(m\leq p\) and \(mp\) is not in Row \(p\). Thus, \(f(p)=0\) when \(p\) is a prime number.

3. We will show that \(f(pq)=(p-1)(q-1)\). To do this, we need to establish two things:

   • \((p-1)(q-1)pq\) is not in Row \(pq\).

   • For every integer \(k\) with \((p-1)(q-1) < k \leq pq\), the integer \(kpq\) is in Row \(pq\).

   We will assume that \(p\leq q\). If not, then \(q\leq p\) and the proof is essentially identical.

   To see that the first point is true, set \(n=pq\), \(m=(p-1)(q-1)\), \(a=q(p-1)\), and \(b=p(q-1)\) and apply Fact 2. Note that \(p-1 < p\) so \((p-1)(q-1) < p(q-1)\) or \(m < a\). We also have \(p \leq q\), which can be rearranged to get \(-q\leq -p\), and so \(pq-q\leq pq-p\), which can be factored to get \(q(p-1) \leq p(q-1)\) or \(a\leq b\). Finally, \(q-1 < q\), so \(b=p(q-1) < pq=n\). Putting these inequalities together, we have \(m < a\leq b < n\). Since \(mn=(p-1)(q-1)pq=ab\), the conditions of Fact 2 are satisfied and we can conclude that \((p-1)(q-1)pq\) is not in Row \(pq\).

   Now suppose \(k\) is an integer such that \((p-1)(q-1) < k \leq pq\). We wish to show that \(kpq\) must be in Row \(pq\). To do this, we will assume that it is not in Row \(pq\) and deduce a contradiction.

   To that end, assume that \(kpq\) is not in Row \(pq\). By Fact 1, there must be integers \(a\) and \(b\) with \(k < a\leq b < pq\) such that \(kpq=ab\). If \(a\) is a multiple of \(pq\), then we would have \(pq\leq a\), but \(a<pq\) by assumption, so this is impossible. Therefore, \(a\) is not a multiple of \(pq\). Similarly, \(b\) is not a multiple of \(pq\).

   Since \(ab\) is a multiple of \(pq\) and \(p\) and \(q\) are prime, either \(a\) is a multiple of \(p\) and \(b\) is a multiple of \(q\), or \(a\) is a multiple of \(q\) and \(b\) is a multiple of \(p\). We will assume that \(a\) is a multiple of \(p\) and \(b\) is a multiple of \(q\). The other situation is similar. This implies the existence of integers \(x\) and \(y\) such that \(px=a\) and \(qy=b\). Observe that since \(a<pq\), we must have \(x< q\), and similarly \(y<p\). Since \(x\), \(y\), \(p\), and \(q\) are integers, we conclude that \(x\leq q-1\) and \(y\leq p-1\).

   Since we are assuming that \(kpq=ab\), we have \[k = \frac{ab}{pq} = \frac{pxqy}{pq}=xy\leq (p-1)(q-1)\] However, we are also assuming that \((p-1)(q-1) < k\), so we can deduce that \[k \leq (p-1)(q-1) < k\] which is impossible because it implies \(k<k\). Therefore, our assumption that \(kpq\) is not in Row \(pq\) must be false, and we conclude that \(kpq\) is in Row \(pq\).

   Therefore, \(f(pq)=(p-1)(q-1)\) as claimed earlier.

4. The value of \(f(p^d)\) depends on whether \(d\) is even or odd. If \(d=2r\) for some integer \(r\), then \(f(p^d) = \left(p^r-1\right)^2\). If \(d=2r+1\) for some integer \(r\), then \(f(p^d)=\left(p^r-1\right)\left(p^{r+1}-1\right)\).

   Here we include a proof in the case where \(d\) is even. The proof when \(d\) is odd is a slight modification of the proof given for when \(d\) is even.

   Assume \(d=2r\) for some positive integer \(r\). As with part (c), we need to show that

   • \(p^{2r}\left(p^r-1\right)^2\) is not in Row \(p^{2r}\),

   • and \(kp^{2r}\) is in Row \(p^{2r}\) for every \(k\) with \(\left(p^r-1\right)^2 < k \leq p^{2r}\).

   If we set \(m=\left(p^r-1\right)^2\), \(n=p^{2r}\), and \(a=b=p^r\left(p^r-1\right)\), then we will have \(m < a\leq b < n\) and \(mn=ab\), so \(p^{2r}\left(p^r-1\right)^2\) is not in Row \(p^{2r}\) by Fact 2. This establishes the first bullet point above.

   For the second, suppose \(kp^{2r}\) is not in Row \(p^{2r}\) for some \(k\) with \(\left(p^r-1\right)^2 < k \leq p^{2r}\). By Fact 1, there must be integers \(a\) and \(b\) with \(\left(p^r-1\right)^2 < a\leq b < p^{2r}\) and \(kp^{2r}=ab\).

   The product \(ab\) must have at least \(2r\) factors of the prime number \(p\), meaning the two integers \(a\) and \(b\) have at least a total of \(2r\) factors of \(p\) between them. Therefore, there are non-negative integers \(u\) and \(v\) such that \(u+v=2r\), \(a\) is a multiple of \(p^u\), and \(b\) is a multiple of \(p^v\). By definition, there are positive integers \(x\) and \(y\) such that \(p^ux=a\) and \(p^vy=b\).

   We are also assuming that \(a\leq b < p^{2r}=p^{u+v}=p^up^v\), so \(a=p^ux < p^up^v\) and \(b=p^vy < p^up^v\), which implies \(x < p^v\) and \(y < p^u\). Since \(x\), \(p\), \(u\), and \(v\) are non-negative integers, we have \(x\leq p^v-1\) and \(y\leq p^u-1\). Multiplying these inequalities, we obtain \(xy \leq (p^u-1)(p^v-1)\). We are also assuming that \(kp^{2r}=ab\), so we can substitute to get \[kp^{2r} = xyp^up^v=xyp^{u+v}=xyp^{2r}\] Thus, \(kp^{2r}=xyp^{2r}\), so \(k=xy\), which implies \(k\leq (p^u-1)(p^v-1)\).

   We can now conclude that \(\left(p^r-1\right)^2 < k \leq (p^u-1)(p^v-1)\). To finish the argument, we will show that \((p^u-1)(p^v-1)\leq (p^r-1)^2\), which would imply that \((p^r-1)^2< (p^r-1)^2\), which is clearly false.

   To show that \((p^u-1)(p^v-1) \leq (p^r-1)^2\), we will show that if \(u\) and \(v\) are non-negative integers with \(u+v=2r\), then the quantity \((p^u-1)(p^v-1)\) is maximized when \(u=v=r\).

   Suppose \(u\) and \(v\) are non-negative integers with \(u > v\) and \(u+v=2r\). Consider the quantity \((p^{u-1}-1)(p^{v+1}-1)-(p^u-1)(p^v-1)\). We can manipulate this difference as follows. \[\begin{align*} (p^{u-1}-1)(p^{v+1}-1) - (p^u-1)(p^v-1) &= p^{u+v} - p^{u-1} - p^{v+1} + 1 - p^{u+v} + p^u + p^v - 1 \\ &= p^u + p^v - p^{u-1} - p^{v+1} \\ &=p^v(p^{u-v} + 1 - p^{u-v-1} - p) \\ &= p^v(p^{u-v}-p)\left(1-\frac{1}{p}\right)\end{align*}\] We are assuming that \(u>v\). Since \(u+v\) is even, it must also be true that \(u-v\) is even. Therefore, \(u-v\geq 2\). As well, \(p\) is a prime number so \(p\geq 2\), which implies \(p^{u-v}-p > 0\) and \(1-\frac{1}{p} > 0\). The quantity \(p^v\) is positive, and so we conclude that \(p^v(p^{u-v}-p)\left(1-\frac{1}{p}\right) > 0\), which implies that \((p^{u-1}-1)(p^{v+1}-1) - (p^u-1)(p^v-1) > 0\). Rearranging this inequality, we get \((p^{u-1}-1)(p^{v+1}-1) > (p^u-1)(p^v-1)\).

   What we have shown is that if \(u\) and \(v\) are non-negative integers with \(u+v=2r\) and \(u>v\), we can increase the value of \((p^u-1)(p^v-1)\) by decreasing \(u\) by \(1\) and increasing \(v\) by \(1\). It follows that \((p^u-1)(p^v-1)\) is maximized when \(u\) and \(v\) are as close together as possible, which happens when \(u=v=\dfrac{2r}{2}=r\).

5. In general, \(f(n)\) can be computed as follows: find the unique positive integers \(x\) and \(y\) with \(x\leq y\), \(xy=n\), and \(y-x\) as small as possible. Then \(f(n)=(x-1)(y-1)\).

   For example, if \(n=p\) is a prime number, then the only positive factor pair is \(p=1\times p\), so \(x=1\) and \(y=p\). Indeed, from part (b), \(f(p)=0= (1-1)(p-1)=(x-1)(y-1)\). If \(n\) is a perfect square, then \(n=z^2\) for some positive integer \(z\). Here, we must have \(x=y=z\) because this gives \(y-x=0\), which is the smallest that the difference between the factors in a factor pair could possibly be. Indeed, \(f(z^2)=(z-1)^2\) agrees with the case from part (d) where \(n=p^{2r}\). As a final example, consider \(n=72\). Its positive factor pairs are \((1,72)\), \((2,36)\), \((3,24)\), \((4,18)\), \((6,12)\), and \((8,9)\). The pair with the smallest difference between the factors is \((8,9)\), so we have \(x=8\) and \(y=9\), giving \((x-1)(y-1)=(8-1)(9-1)=56\). Indeed, \(56\times72=63\times64\), so \(56\times72\) is not in Row \(72\). As well, you can check that \(72m\) is in Row \(72\) for each \(m\) from \(57\) through \(72\), which shows that \(f(72)=56\).

   We will now justify that this "formula" always works.

   Fix an integer \(n\) and suppose \(x\), \(y\), \(u\), and \(v\) are positive integers with \(x\leq y\), \(u\leq v\), and \(xy=uv=n\).

   If \(y-x \leq v-u\), then since \(x\leq y\), we have \(0\leq y-x\leq v-u\), so we can conclude that \((y-x)^2\leq (v-u)^2\). Expanding these expressions and adding \(4n\) to both sides, we have \[\begin{align*} y^2 - 2xy + x^2 &\leq v^2 - 2uv + u^2 \\ y^2 - 2xy + x^2 + 4n &\leq v^2 - 2uv +u^2 + 4n \\ y^2 - 2xy + x^2 + 4xy &\leq v^2 - 2uv +u^2 + 4uv \\ y^2 + 2xy + x^2 &\leq v^2 + 2uv +u^2 \\ (y+x)^2 &\leq (v+u)^2\end{align*}\] and since \(y+x\) and \(v+u\) are both positive, we must have \(y+x \leq v+u\). Essentially the same argument in reverse shows that if \(y+x\leq v+u\), then \(y-x\leq v-u\).

   We have shown that \(y-x \leq v-u\) exactly when \(y+x\leq v+u\). This implies that if we consider all positive factor pairs of \(n\), the one that has the smallest difference is also the one that has the smallest sum. Therefore, we can restate our "formula" as follows: Given a positive integer \(n\), let \(x\) and \(y\) be positive integers with \(xy=n\) and \(x+y\) as small as possible. Then \(f(n)=(x-1)(y-1)\). We will assume that the integers \(x\) and \(y\) satisfy \(x\leq y\). If not, then they can be relabelled.

   The overall structure of the argument will resemble the arguments for parts (c) and (d). That is, we will show that \(xy(x-1)(y-1)\) is not in Row \(n\), but if \((x-1)(y-1)<m\leq n\), then \(mxy\) is in Row \(n\). The solution presented will use, without proof, a few well-known facts about divisibility and greatest common divisors.

   To see that \(xy(x-1)(y-1)\) is not in Row \(n\), take \(m=(x-1)(y-1)\), \(a=y(x-1)\), and \(b=x(y-1)\) and apply Fact 2. That these choices of \(m\), \(a\), \(b\), and \(c\) satisfy the conditions of Fact 2 can be verified in essentially the same way as they were in the solutions to parts (c) and (d).

   Now suppose \(m\) is an integer with \((x-1)(y-1) < m \leq n=xy\) such that \(mn\) is not in Row \(n\). By Fact 1, there are integers \(a\) and \(b\) such that \(m < a\leq b < n\) and \(ab=mn\). Let \(d=\gcd(n,b)\) and then define \(e=\dfrac{n}{d}\) and \(f=\dfrac{b}{d}\). Observe that the integers \(e\) and \(f\) must satisfy \(\gcd(e,f)=1\) since if they had a common divisor larger than \(1\), then the greatest common divisor of \(n\) and \(b\) would need to be larger than \(d\).

   Dividing both sides of \(ab=mn\) by \(d\), we get \(af=me\), which shows that \(af\) is a multiple of \(e\). We have already noted that \(e\) and \(f\) have no common divisors larger than \(1\), so we are forced to conclude that \(a\) is a multiple of \(e\). That is, there must be some integer \(g\) such that \(a=eg\).

   To summarize, so far we have that \(d=\gcd(b,n)\), \(de=n\), \(df=b\), and \(eg=a\). Consider the integers \(e\) and \(f\) and suppose \(e\leq f\). Multiplying both sides by \(d\) gives \(de \leq df\) or \(n \leq b\), but this contradicts our assumption that \(b<n\), so we cannot have \(e\leq f\). Therefore, \(f < e\), and since both \(e\) and \(f\) are integers, we get \(f\leq e-1\). Similarly, if \(d\leq g\), then \(de\leq eg\) or \(n\leq a\), which contradicts our assumption, so we conclude that \(g<d\) and so \(g\leq d-1\).

   We are assuming that \((x-1)(y-1) < m\), so we have the following \[n(x-1)(y-1) < mn = ab = egdf \leq de(e-1)(d-1)\] which implies \(n(x-1)(y-1) < de(d-1)(e-1)\). Using that \(n=de\), we cancel to get \((x-1)(y-1) < (d-1)(e-1)\) which can be expanded to get \(xy-x-y+1 < de-d-e+1\), and since \(de=xy=n\), this simplifies to \(d+e < x+y\). However, \(xy=n\) is the factorization of \(n\) into a product of positive integers that minimizes the sum of the factors. Since \(de=n\), the inequality \(d+e < x+y\) is a contradiction of this minimality.

   We conclude that our assumption that \(mn\) is not in Row \(n\) must be false, which means \(mn\) is in Row \(n\). This completes the proof.