Team Selection Test for IMO, 2024

Answer: $r = 2, 3$.

Suppose that $r \geq 4$. Since there are infinitely many primes, there are same coloured primes $p$ and $q$. Since all divisors of $n = pq$ are $1, p, q, pq$, and hence no divisor of $n = pq$ is coloured into some of $r \geq 4$ colours. Thus, the problem conditions are not satisfied.

Let $r = 3$. Each positive integer $n$ with prime factorization $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m}$ we colour to $(a_1 + a_2 + \cdots + a_m) \pmod{3}$. The number $n = 1$ with $t = 0$ we colour to $0$. By induction over the number of different primes in the prime factorization of $n$ we will show that this colouring satisfies the problem conditions. Let $d_n(0), d_n(1), d_n(2)$ be the number of divisors of $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m}$ coloured to $0, 1, 2$, respectively.

If $t = 0$ then the corresponding $d(0) = 1, d(1) = 0, d(2) = 0$ and conditions are held. Suppose that problem conditions are held for all integer numbers with $t = m$ and consider $a = p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m} \cdot p_{m+1}^{a_{m+1}}$, with $d_a(0), d_a(1), d_a(2)$. Let $d_b(0), d_b(1), d_b(2)$ be the number of divisors of $b = p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m}$ of colours $0, 1, 2$, respectively. By induction hypothesis
$$|d_b(i) - d_b(j)| \leq 1 \text{ for all pairs } (i, j), \text{ where } i, j = 0, 1, 2. \quad (\dagger)$$

Any divisor of $a$ has a form $d \cdot p_{m+1}^u$, where $d$ is a divisor of $b$ and $0 \le u \le a_{m+1}$. Then
$$d_{p_{m+1}^{3l+0}}(0) = d_b(0), \quad d_{p_{m+1}^{3l+0}}(1) = d_b(1), \quad d_{p_{m+1}^{3l+0}}(2) = d_b(2)$$
$$d_{p_{m+1}^{3l+1}}(0) = d_b(2), \quad d_{p_{m+1}^{3l+1}}(1) = d_b(0), \quad d_{p_{m+1}^{3l+1}}(2) = d_b(1) \quad (\ddagger)$$
$$d_{p_{m+1}^{3l+2}}(0) = d_b(1), \quad d_{p_{m+1}^{3l+2}}(1) = d_b(2), \quad d_{p_{m+1}^{3l+2}}(2) = d_b(0)$$
Let $d(0) + d(1) + d(2) = D$.

Case 1: $a_{m+1} = 3l$. Then by $(\ddagger)$
$$d_a(0) = d_b(0) + lD, \quad d_a(1) = d_b(1) + lD, \quad d_a(2) = d_b(2) + lD$$
and hence by $(\dagger)$ the conditions are held.

Case 2: $a_{m+1} = 3l+1$. Then by $(\ddagger)$
$$d_a(0) = d_b(0) + lD + d_b(2), \quad d_a(1) = d_b(1) + lD + d_b(0), \quad d_a(2) = d_b(2) + lD + d_b(1)$$
and hence by $(\dagger)$ the conditions are held.

Case 3: $a_{m+1} = 3l+2$. Then by $(\ddagger)$
$$d_a(0) = d_b(0) + lD + d_b(2) + d_b(1), \quad d_a(1) = d_b(1) + lD + d_b(0) + d_b(2), \quad d_a(2) = d_b(2) + lD + d_b(1) + d_b(0)$$
and hence the conditions are held.

Let $r = 2$. Each positive integer $n$ with prime factorization $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_m^{\alpha_m}$ we colour to the colour $(\alpha_1 + \alpha_2 + \cdots + \alpha_m) \pmod{2}$. As in the case $r = 3$, it can be readily shown that this colouring also satisfies the problem conditions.

Therefore, the only possible values of $r$ are $2$ and $3$.