Let $m$ and $n$ be positive integers. In Philand, the Kingdom of Olymphics, with $m$ cities, and the Kingdom of Mathematicians for Fun, with $n$ cities, fight a battle in rounds. Some cities in the country are connected by roads, so that it is possible to travel through all the cities via the roads. In each round of the battle, if all cities neighboring, that is, connected directly by a road, a city in one of the kingdoms are from the other kingdom, that city is conquered in the next round and switches to the other kingdom. Knowing that between the first and second round, at least one city is not conquered, show that at some point the battle must end, i.e., no city can be captured by another kingdom.
Problem
Source: OlimphÃada 2022- Problem 3/ Level 2
Tags: graph, Combo, graph theory
biomathematics
26.07.2022 06:49
I'll write in terms of graph theory: Let $G_1$ be a finite simple connected graph on the vertex set $V$ with $|V| = m+n$, with $m$ red and $n$ blue vertices. In round $k$, we color any vertex in $G_{k}$ whose color is different from each of its neighbors with the color of their neighbors; this new graph is called $G_{k+1}$. We want to show that if in the first round there is some vertex whose color did not change, then for some $k$ we have $G_k = G_{k+1}$. Let $c_G(v)$ denote the color of $v$ in graph $G$. Call a vertex $v$ of a graph $G$ fixed if it has some neighbor $w$ such that $c_G(v) = c_G(w)$. It is clear that a fixed vertex never changes color and that $c_w(G)$ is also fixed. Therefore, the set of fixed vertices of $G_k$ is a subset of the set of fixed vertices of $G_{k+1}$. Assume the contrary, that is, suppose the battle never ends. The set of fixed vertices must eventually converge to some $S$ which is not the entire set of $m+n$ vertices, nor is it the empty set (because there is some vertex that did not change color in round 1, and this vertex must have had a neighbor with the same color as it is). Consider the set $X = V-S$. This set of vertices changes color every round. Pick any $x \in X$ and any $k$ which is large enough so that the set of fixed vertices is $S$. Let's say $x$ is red in $G_k$, otherwise change $k$ to $k+1$. The set of neighbors of $x$ in $G_k$ must be blue. Now, if any vertex $w$ which is a neighbor of $x$ does not change color in round $k$, then $c_{k+1}(x) = c_{k+1}(w)$, which means $x \in S$, a contradiction. This actually means that $N_k(x) \subseteq X$, because they all changed color in round $k$. This means that the set of neighbors of the neighbors of $x$ must be red in $G_k$. Again, if any of these neighbors of neighbors does not change color, then some vertex $w$ in $N_{k+1}(x)$ will have the same color as a neighbor of $w$, which contradicts $N_k(x) \subseteq X$. We can keep going breadth-wise and get that any vertex reachable from $x$ is in $X$. But the graph is connected and $S$ is non-empty, which is a contradiction.