How I Created a Math Olympiad Problem

Hi, Choo Ray here.

Before IMO 2024, the Singapore team had a joint friendly contest with Iran and Taiwan (spoilers ahead). As I found out, it takes quite a lot of work to run a contest. We wanted to simulate the IMO format in terms of topic diversity and difficulty but our shortlist lacked depth in certain topics. Less than a month from the IMO, we were scrambling to have the problems ready. In the end, we cobbled together a paper over some Discord conversations with our friends from Iran and Taiwan.

A few months prior, I was jogging at Botanic Gardens, which left my mind free. So I thought, what if we took a positive integer and added its totient function? I was hoping for this to have nice properties since the totient function is closely related to the original number and its prime factors. Inspired by a problem from the National Team Selection Test that had just concluded, I asked myself: does such a sequence always contain infinitely many prime factors? By the end of my jog I came up with the following counterexample: $10,14,20,28,40,56,...$

A few weeks later I was with Lucas when the conversation turned to proposing problems for various contests. I remembered this problem and posed it to him. He thought for a bit and quickly revealed a simpler sequence I had missed: $4,6,8,12,16,24,...$ Not willing to let the idea flop so fast, I came up with a slight variation: "What if instead of just adding the totient, we added two times the totient each time? Or three times the totient?"

We did not make further progress on this extension in the 5 minutes after (computing totients are hard), but I was intrigued enough to work on it a few days after and quickly discovered that adding two times the totient, we can have: $2,4,8,16,32,...$ It takes little effort to generalize this to any prime, since $p^x + p\cdot\varphi (p^x)=p^{x+1}$, then the powers of $p$ work. So that settles every case where we add a prime multiple of the totient. However, I encountered difficulties in trying to find an example for the sequence $x\rightarrow x+4\cdot\varphi(x)$, even after computing the results for $1$ to $100$!

I decided to send the problem to Aloysius to see if I was just having a skill issue.

consider the operation that sends n to n+k*totient(n). Is it always possible to find a starting positive integer so that if we keep applying this operation, the set of primes dividing some element in the sequence is finite?

Meanwhile I continued working on the problem. I was quite happy with generalizing $2,4,8,16,32,...$ to $p,p^2,p^3,...$ and I thought: could we generalize further? Sure, we could have sequences where each number is a multiple of the previous but keeping the same prime factors. The key insight is that since $\varphi(n) = n\cdot\prod_{p|n}(1-\frac{1}{p})$, with the set of prime factors constant, the ratio between successive terms is preserved, forming a geometric progression. This allowed me to find sequences for $k=6,9,10,14,15$, while $k=4,8,12$ remained elusive.

Aloysius came back with a similar idea about geometric progressions. Soon we discovered a fundamental flaw with such constructions: it was impossible to construct a geometric progression for $k=4$. Note that to achieve $n|n+k\cdot\varphi(n)$, we must have $1+k\prod_{p|n}(1-\frac{1}{p})$ being an integer. Now the key observation is that the largest prime divisor of $n$ must divide $k$ in order to get "cancelled" from the denominator. When $k=4$, $n$ cannot have any prime larger than $2$, but powers of $2$ result in non-powers after one step.

I thought that was a significant enough result to build a problem around. Over the following weeks, I worked on the idea of "integer ratio sequences", where each term is an integer multiple of the previous. At one point I realized that if we restrict successive terms to have a divisibility relation, then we must eventually have a geometric progression. Note that $n+k\cdot\varphi(n)<(k+1)n$, so that the ratio of successive terms takes on a finite number of values. Then finitely many primes can divide any term of the sequence. By infinite pigeonhole, there exist two terms with the same set of primes, so that at the first instance, $1+k\prod_{p|n}(1-\frac{1}{p})$ must have introduced no new primes, then the set of primes becomes fixed and we have a constant ratio. Later on I realized another way to frame the argument. At any point, if the set of primes stays constant from one term to the next you have a geometric progression, but otherwise the cardinality of that set keeps increasing, which contradicts the fact that we only have finitely many primes dividing any term. When I told this result to the Singapore team post-contest, some felt that it would have been a good substitution to the actual contest problem.

Part of the reason why that version did not appear in contest was that I was simultaneously working on numerical results too. From the investigation of case $n=4$ we know that the largest prime divisor of $n$ must divide $k$. It happens that the following year, 2025, is a number with small prime divisors! Therefore, I tried to disprove $k=2025$ having integer ratio sequences. A short case bash tells us that when the first term in the sequence only has prime factors in the set ${2,3,5}$, the second term will contain primes outside of that set which fails immediately.

Then I tried to find another $k$ close to 2025 that permitted a geometric progression and after some computations I found that with the set of primes ${3,5,7}$ I am able to construct a sequence for $k=2065$. So I created a two part problem, asking to show whether $k=2025$ and $k=2065$ had integer ratio sequences.

When typing up the problem I realized that the sequence being infinite was now not necessary for the solutions I had. In fact it would permit other solutions based on the earlier infinite pigeonhole/prime counting ideas and I wanted to limit the solution space, so I changed it to a sequence of length $10$. When double checking my solution I had a mild crisis over whether $\varphi(1)=0$ (which would allow the sequence $1,1,1,1,1,...$) and decided to just patch it out explicitly.

This led to the final version of the problem:

(2024 IRN-SGP-TWN Friendly Math Competition P4) Consider the function $f_k:\mathbb{Z}^{+}\rightarrow\mathbb{Z}^{+}$ satisfying $f_k(x)=x+k\varphi(x)$ where $\varphi(x)$ is Euler's totient function, that is, the number of positive integers up to $x$ coprime to $x$. We define a sequence $a_1,a_2,...,a_{10}$ with $a_1=c$ $a_n=f_k(a_{n-1})$ $\forall$ $2\le n\le 10$ Is it possible to choose the initial value $c\ne 1$ such that each term is a multiple of the previous, if (a) $k=2025$ ? (b) $k=2065$ ?

Bonus Content

During the contest, some students found a construction for $k=2065$ involving the set of primes ${2,7,29,59}$.

After typing this blogpost I decided to get some computer assistance:

Wha...?