Find the maximum number of colors used in coloring integers $n$ from $49$ to $94$ such that if $a, b$ (not necessarily different) have the same color but $c$ has a different color, then $c$ does not divide $a+b$.
Problem
Source: 2014 Thailand October Camp Number Theory Exam p3
Tags: number theory, Coloring
06.03.2022 12:40
Let $\chi(a)$ be the colour of $a$. Then whenever the argument to $\chi(\cdot)$ is an integer in $[49,94]$:\begin{align*}\chi(\tfrac{2a}{3})&=\chi(a)\\\chi(\tfrac{a+b}{2})&=\chi(a)\quad\text{if }\chi(b)=\chi(a)\\\chi(\tfrac{a+b}{3})&=\chi(a)\quad\text{if }\chi(b)=\chi(a)\end{align*}Smaller fractions $\le\tfrac{a+b}{4}$ are out of range because $49>\tfrac{94}{2}$. Iterating the second of those relations, it's also convenient to note:\[\chi(a+2^rq)=\chi(a)\implies\chi(a+kq)=\chi(a)\ \forall k=0,1,2,3,\ldots,2^r\] Expanding out from $\chi(84)$ and $\chi(90)$: $84\implies 56\implies(63,{\bf 70},77,80)$ are all the same colour, $90\implies 60\implies 75\implies 50\implies (55,65,{\bf 70},80,85)$ are all the same colour, and because they have $70$ in common, both sets have the same colour, red, say. Now $56,60\implies 58=90-2^5\implies \text{all }58\le x\le 90$ are red. $49=\tfrac{57+90}{3}$, so $49$ is red. But then $81=49+2^5$ is red, so in fact all $49\le x\le 90$ are red. What about the leftovers? $93=\tfrac{3}{2}\times 62$, so $93$ is red, then (thanks #3) $91=\tfrac{89+93}{2}$ and $92=\tfrac{91+93}{2}$, leaving only $94$ which is not $\tfrac{3}{2}$ times anything, so can be coloured independently (black, say), for a maximum of $\boxed{\bf{2}}$ colours overall. Edited to correct arithmetic oversight per #3. Don't know how I missed that originally.
06.03.2022 13:57
$91|89+93$.