XXXIII Cono Sur Mathematical Olympiad

Let $S_i$ be the cardinality of the set of the numbers colored $C_i$. We begin by bounding the number of colors for which $S_i=1$. Let's say there are $\ell$ of those. If $a_j$ are the numbers with such colors and we have $a_1<a_2<\cdots <a_{\ell }$, then we must have $a_1\mid a_2\mid \cdots \mid a_{\ell }$. Therefore $a_j\ge 2a_{j-1}$ and we conclude that $a_{\ell }\ge 2^{\ell -1}$. Since $a_{\ell }\le 170$, we get $2^{\ell -1}\le 170$, so $\ell \le 8$.

Now we bound $k$. We have $170={\sum }_{i=1}^k{S}_i={\sum }_{S_i=1}{S}_i+{\sum }_{S_i>1}{S}_i$. If we bound the cardinality of the sets that do not have only one number by 2, we get $170\ge \ell +2(k-\ell )=2k-\ell \ge 2k-8$. From here we conclude that $k\le 89$. This is the maximum possible value, it remains for us to show an example with $k=89$ colors.

The proof of the bound guides us in the construction of the example. For 8 colors we must color only one number and those numbers have to be the powers of 2. For the rest of the colors we have to color exactly 2 numbers.

Let $D_i$ be the set of the numbers colored $C_i$. We construct the following example:

$$D_1=\{1\},D_2=\{2\},D_3=\{4\},$$ $$D_4=\{3,5\},D_5=\{8\},$$ $$D_6=\{6,10\},D_7=\{7,9\},D_8=\{16\},$$ $$D_9=\{11,21\},D_{10}=\{12,20\},\dots ,D_{13}=\{15,17\},D_{14}=\{32\},$$ $$D_{15}=\{22,42\},D_{16}=\{23,41\},\dots ,D_{24}=\{31,33\},D_{25}=\{64\},$$ $$D_{26}=\{43,85\},D_{27}=\{44,84\},\dots ,D_{46}=\{63,65\},D_{47}=\{128\},$$ $$D_{48}=\{86,170\};D_{49}=\{87,169\},\dots ,D_{89}=\{127,129\}.$$

The sum of every set is a power of 2, and they are ordered. Therefore each of them divides the next one. The example has the desired properties.