Bulgarian National Mathematical Olympiad

We first prove that the function $f$ is injective, i.e. $A \neq B$ implies $f(A) \neq 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) \neq 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 \neq 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 < \dots < 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.