Team Selection Test for IMO 2024

Answer: $r=2,3$.

Suppose that $r\ge 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\ge 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)(\mathrm{mod}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)|\le 1\text{ for all pairs }(i,j),\text{ where }i,j=0,1,2.(†)$$

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),d_{p_{m+1}^{3l+0}}(1)=d_b(1),d_{p_{m+1}^{3l+0}}(2)=d_b(2)$$ $$d_{p_{m+1}^{3l+1}}(0)=d_b(2),d_{p_{m+1}^{3l+1}}(1)=d_b(0),d_{p_{m+1}^{3l+1}}(2)=d_b(1)(‡)$$ $$d_{p_{m+1}^{3l+2}}(0)=d_b(1),d_{p_{m+1}^{3l+2}}(1)=d_b(2),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,d_a(1)=d_b(1)+lD,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),d_a(1)=d_b(1)+lD+d_b(0),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),d_a(1)=d_b(1)+lD+d_b(0)+d_b(2),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)(\mathrm{mod}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$.