Note: blue text is broken atm after porting over to Hugo site.

So a while ago, Eugene had the idea of having a “bluetext” walkthrough. The idea was that you have the walkthrough alongside a complete solution so you have both the thought process and how it would translate on paper.

I tried to compile a collection of bluetexted problems but never really got around to it. Anyway, here’s the very first one I tried.

(Somewhat interestingly, hackmd.io supports arbitrary CSS!)

(Math Prize for Girls Olympiad 2016 Q4) Let $d(n)$ denotes the number of positive divisors of $n$, and call a function $f$ completely multiplicative if $f(m)f(n)=f(mn)$ for all $m,n$ within the domain of $f$.

Does there exist a bijection $f:\mathbb{N}\rightarrow\mathbb{N}$ on the naturals such that $d\circ f$ is completely multiplicative?

Soution and Walkthrough. The easiest thing to grapple with here is the “completely multiplicative” condition. The implication is that the function is completely dependent on its values at primes $p_i$, so let’s get that out of the way.

Note that if the prime factorization of $n$ is $p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$, then $$d(f(n))=\prod_{i=1}^k d(f(p_i))^{\alpha_i}$$

What now? If we daydream a little we could hope for $f=d^{-1}$. Unfortunately, $d$ is too small (easily $< \sqrt{n}$), so there’s no way the bijection will work out. But, we also notice our constraints on $f(n)$ aren’t too exacting: if we swap $f(n)$ for anything else with the same number of divisors, the resulting function will still work!

This has tremendous implications on the bijectivity condition, since we can pretty much ignore it: $f(n)$ can now be as big as we’d like as long as there are infinitely many $n\in \text{Im }f$ with $d(n)=k$, since we can biject them back to all numbers with $k$ divisors (which there are infinitely many of unless $k=1$).

It suffices to construct an injective $f_0:\mathbb{N}\rightarrow\mathbb{N}$ such that (1) $d\circ f_0$ is completely multiplicative; (2) for any fixed $k$, $\text{Im }f_0$ contains infinitely many solutions to $d(n)=k$ for all $k\ge 2$ (3) $\text{Im }f_0$ contains 1 as an element. Indeed, suppose: $$A=\{n\mid d(n)=k\}=\{a_1

Of course, this is way too convoluted. But the important idea here is that we should not try to construct $f$ directly, but as a bijection between sets.

Maybe let’s define $h=d\circ f$, then we want $h$ to be completely multiplicative, and have the same number of solutions as $d$ for each value (i.e. $\left|\{n\mid h(n)=k\}\right|=\left|\{n\mid d(n)=k\}\right|$). This may sound difficult, but actually the set $\{n\mid d(n)=k\}$ is infinite for $k\ge 2$.

But as we’ve realised, $h$ is completely defined by its prime values, so we need $h(p)$ to take each prime value infinitely many times (over prime $p$). This can be arranged:

Consider a bijection $h_0:\mathbb{N}\rightarrow\mathbb{N}^2$. Let $\{p_1

Hence, a bijection $f_k:\{n\mid h(n)=k\}\rightarrow \{n\mid d(n)=k\}$ exists for any fixed $k$, so it is clear that $f(n)=f_{h(n)}(n)$ satisfies the conditions given, since $d(f(n))=h(n)$.

Comments. Two key takeaways in this rather difficult problem:

• The most important clues are often obvious ideas: in this case, it was swapping $f(n)$ for something else with the same $d$-value
• Sometimes, a wrong idea can lead to a correct one: the initial attempt to construct $f_0$ was implausible to try, but it contained an idea that would eventually solve the problem.