Let $r\geq 2$ be a positive integer, and let each positive integer be painted in one of $r$ different colors. For every positive integer $n$ and every pair of colors $a$ and $b$, if the difference between the number of divisors of $n$ that are painted in color $a$ and the number of divisors of $n$ that are painted in color $b$ is at most $1$, find all possible values of $r$.
Problem
Source: 2024 Turkey TST P7
Tags: combinatorics, Piegonhole, Coloring
19.03.2024 00:46
For $r\geq 4$, take $n=pq$. Its divisors are $1,p,q,pq$ and since the number of divisors is less than or equal to the number of colors, no two of them can be the same color. Therefore, all primes are painted in a different color. This is impossible because there are infinite number of primes. $r=2$ works if we paint all numbers according to the sum of powers of prime in their prime power representation, modulo 2. $r=3$ works similarly if we paint all numbers according to the sum of powers of prime in their prime power representation, modulo 3. For example, $30=2^1\cdot 3^1\cdot 5^1$ is painted in color $C_0$ since $1+1+1\equiv 0$ (mod 3) while $49=7^2$ is painted in color $C_2$ since $2\equiv 2$ (mod 3). This works because of the following induction observation: Let's call a set $S$ of integers nice if the number of elements in it congruent to 0,1, and 2 (mod 3) differ by at most one. If $S_1$ and $S_2$ are nice, then $S_3=\{a+b:a\in S_1,b\in S_2\}$ is also nice. And $\{0,1,2,\cdots,n\}$ is nice for every $n$.
19.03.2024 12:31
It's also possible to solve this problem where $1$ is replaced with any constant $C\ge 1$ by basically mimicing the proof of 2024 CTST P9. The answer is still $r=2$ and $r=3$.
03.05.2024 03:17
The only answers are $\boxed{r=2,3}$. For the solution let the colors be $C_1,C_2,\dots,C_r$. Claim: If $4\leq r$ then no such coloring exists By PhP there exists two primes $p$ and $q$ with the same color. Considering $n=pq$ leads to a contradiction. Construction: We will first give a construction for $r=3$. Let $\Omega(n)$ denote the total number of prime divisors of $n$. If $\Omega(n)\equiv 1 \pmod{3}$ color $n$ with $C_1$, if $\Omega(n)\equiv 2 \pmod{3}$ then color $n$ with $C_2$, and if $\Omega(n)\equiv 0 \pmod{3}$ then color $n$ with $C_3$. Let $w$ be the third root of unity. Now assign $C_1$, $C_2$, and $C_3$ to $w^1$, $w^2$, and $w^3$, respectively. Notice that the color assigned to $n$ is equivalent to $w^{\Omega(n)}$. Let $n=p_1^{e_1}p_2^{e_2}\dots p_n^{e^n}$. Then summing the colors over all the divisors of $n$, $$\prod_{i=1}^{n}{\sum_{x_i=1}^{e_i}}w^{x_i}$$This is however a third root of unity. Now assume WLOG that $C_3$ gets at least one more divisor then $C_2$ and at least two more divisors than $C_1$. Then the real part of this sum is strictly greater than $1$, a contradiction. If $r=2$ then the construction and proof are similar to the above.
28.10.2024 22:06
sami1618 wrote: The only answers are $\boxed{r=2,3}$. For the solution let the colors be $C_1,C_2,\dots,C_r$. Claim: If $4\leq r$ then no such coloring exists By PhP there exists two primes $p$ and $q$ with the same color. Considering $n=pq$ leads to a contradiction. Construction: We will first give a construction for $r=3$. Let $\Omega(n)$ denote the total number of prime divisors of $n$. If $\Omega(n)\equiv 1 \pmod{3}$ color $n$ with $C_1$, if $\Omega(n)\equiv 2 \pmod{3}$ then color $n$ with $C_2$, and if $\Omega(n)\equiv 0 \pmod{3}$ then color $n$ with $C_3$. Let $w$ be the third root of unity. Now assign $C_1$, $C_2$, and $C_3$ to $w^1$, $w^2$, and $w^3$, respectively. Notice that the color assigned to $n$ is equivalent to $w^{\Omega(n)}$. Let $n=p_1^{e_1}p_2^{e_2}\dots p_n^{e^n}$. Then summing the colors over all the divisors of $n$, $$\prod_{i=1}^{n}{\sum_{x_i=1}^{e_i}}w^{x_i}$$This is however a third root of unity. Now assume WLOG that $C_3$ gets at least one more divisor then $C_2$ and at least two more divisors than $C_1$. Then the real part of this sum is strictly greater than $1$, a contradiction. If $r=2$ then the construction and proof are similar to the above. Do you mean that linear combinations of $(1,w,w^2)$ always must a real part less than one?