Problem of the Month
Problem 3: December 2023

This month’s problem is an extension of Problem 3 from Part B of the 2023 Canadian Intermediate Mathematics Contest. The original problem was stated as follows:

If you have not already done so, we suggest thinking about the parts above before proceeding.

1. For each positive integer $k$, determine the largest positive integer $n$ with the property that Row $n$ does not include $n^2-kn$. (This generalizes part (c) from the original problem.)

In the remaining questions, $f(n)$ is defined for each $n\ge 1$ to be the largest non-negative integer $m$ such that $m\le n$ and $mn$ is not in Row $n$. For example, Row $6$ is $18,24,30,36$, so $f(6)=2$ since $2\times 6=12$ is not in Row $6$ but $3\times 6$, $4\times 6$, $5\times 6$, and $6\times 6$ are all in Row $6$.

2. Show that $f(p)=0$ for all prime numbers $p$. (Looking closely at the definition of $f(n)$, $f(p)=0$ means that every positive multiple of $p$ from $p$ through $p^2$ appears in Row $p$.)

3. Find an expression for $f(pq)$ where $p$ and $q$ are prime numbers. Justify that the expression is correct.

4. Find an expression for $f(p^d)$ where $p$ is a prime number and $d$ is a positive integer.

5. Take some time to explore the function $f$ further on your own. Are there other results you can prove about the function beyond what is done in (b), (c) and (d)? Is there a nice way to compute $f(n)$ in general without computing each of the first $n-1$ rows?