Problem 9.3. Find the least number of colors with the following property: the integers $1,2 \ldots, 2004$ can be colored such that there are no integers $a<b<c$ of the same color for which $a$ divides $b$ and $b$ divides $c$.

Alexander Ivanov
9.3. Denote by $f(n)$ the least number of colors such that the integers $1,2, \ldots, n$ can be colored in the required way. We shall prove that $f(n)=\lfloor(k+1) / 2\rfloor$, where $2^{k-1} \leq n<2^{k}$. Observe that in the sequence $1,2,2^{2}, \ldots, 2^{k-1}$ we have no three numbers of the same color. This means that $f(n) \geq\lfloor(k+1) / 2\rfloor$.

Consider the following coloring by $\lfloor(k+1) / 2\rfloor$ colors (each color is identified with an integer among $1,2, \ldots,\lfloor(k+1) / 2\rfloor$. If $m=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{t}^{\alpha_{t}} \leq n$, where $p_{i}$ are primes, then we have $h(m):=\alpha_{1}+\cdots+\alpha_{t}<k$ and we can correctly color $m$ by the color $\lfloor(h(m)+1) / 2\rfloor$. If $a$ divides $b$ and $b$ divides $c$, then we have $h(a)<h(b)<h(c)$, i.e., $h(c)-h(a) \geq 2$. This means that the numbers $a$ and $c$ have different colors. Hence $f(n)=\lfloor(k+1) / 2\rfloor$. Now applying the above formula for $n=2004$ we get $f(2004)=6$.