There are $12$ mathematicians living in a village, each of whom belongs to the $\sqrt2$-clan or belong to the $\pi$-clan. Moreover every mathematician's birthday is in a different month and every mathematician has an odd number of friends among them the mathematicians. We agree that if mathematician $A$ is a friend of mathematician $B$, then so is $B$ is a friend of $A$. On his birthday, every mathematician looks at which clan the majority of his friends belong to, and decides to join that clan until his next birthday. Prove that the mathematicians no longer change clans after a certain point.
Problem
Source: 2023 Belgium, VWO Flanders MO p4
Tags: combinatorics
onyqz
12.09.2024 17:19
Consider the graph representation: We are given a graph $G=(V,E)$ with $V$ being the set of vertices (i.e. mathematicians) $\{v_1, v_2, \dots, v_{12}\}$ and $E$ being the set of edges (i.e. mathematicians that are friends). The problem's condition give us that $\deg(v_i), \forall 1\leq i \leq 12$, is odd. Moreover, color the vertices red if they are in $\sqrt{2}$-clan and blue if they are in $\pi$-clan.
Now let $x_i$ be the number of vertices that are connected with $v_i$ but have a different color. Define $S=\sum_{k=1}^{12}x_i$.
We see the following: whenever $v_i$ switches colors, then $x_i$ decreases by at least one (since he switches to the color that more friends have). The friends $v_{i_1}, v_{i_2}, \dots, v_{i_k}$ that have the color that $v_i$ switched to, now have $x_{i_1}, x_{i_2}, \dots, x_{i_k}$ decreased by one. The friends $v_{i_1}, v_{i_2}, \dots, v_{i_j}$ that have the color that $v_i$ had before the switch, now have $x_{i_1}, x_{i_2}, \dots, x_{i_j}$ increased by one. However, since $j < k$, the increase is smaller than the decrease, $S$ must decrease for every color switch that happens (when the color does not switch, $S$ obviously remains unchanged). As long as we can change a color (if we could not, than our process already terminated), $S$ decreases monotonically and hence reaches $0$ at some point, which means, that all vertices have the same color.
This concludes the proof. $\square$