BULGARIAN NATIONAL MATHEMATICAL OLYMPIAD

We first prove that the function $f$ is injective, i.e. $A\ne B$ implies $f(A)\ne f(B)$. Let $a$ be the smallest number which belongs to exactly one of the sets $A$ and $B$. We can assume, $a\in A$, $a\notin B$. Let $C=\{b_1,b_2,\dots ,b_m\}$ be the set (possibly empty) of the numbers from $B$ which divide $a$. Then the definition of $a$ yields that the numbers from $A$ which divide $a$ are exactly $a$ and the numbers from $C$. This means that $a$ belongs to exactly one of the sets $f(A)$ and $f(B)$, i.e. $f(A)\ne f(B)$.

Consider now the directed graph $G$ with vertices the nonempty subsets of $M$ and edges $(A,f(A))$ (direction from $A$ to $f(A)$) iff $A\ne f(A)$. It follows from the above that every vertex of $G$ is either isolated or it is a tail and a head of exactly one edge. Therefore $G$ can be partitioned into cycles.

We will prove that all cycles in $G$ have even length, whence it follows that two colors are enough. Let $(A_1,A_2,\dots ,A_m,A_1)$ be a cycle of length $m\ge 2$. Let $\{a_1,a_2,\dots ,a_k\}={\bigcup }_{i=1}^m{A}_i$, where $a_1<a_2<\cdots <a_k$. It is clear that $a_1\in A_i$ for every $i=1,2,\dots ,m$. Let $t$ be the smallest number such that there exists $i$ such that $a_t\notin A_i$. There exists index $j$ such that $a_t\notin A_j$, but $a_t\in A_{j+1}$. This implies that $a_t$ has odd number of divisors among $a_1,\dots ,a_{t-1}$. Then $a_t\in A_{j-1}$ and so on, i.e. the $a_t$ alternate, whence we conclude that the cycle's length is even.