Dwarves color their houses

Question

The dwarves of the Black Forest live in houses that are each painted either red or blue. Some dwarves are friends, and some aren’t. Every so often, a dwarf will think about repainting his house. To decide whether to repaint, he looks at the colors of his friends’ houses. If his house is red, but more of his friends live in blue houses than in red houses, then he will paint his own house blue. On the other hand, if his house is blue, but more of his friends live in red houses than in blue houses, then he will paint his own house red. Prove that after some point in time, no dwarf ever paints his house again.

Here is my attempt: This problem can be modeled by a graph. The vertices of the graph represent the houses and there is an edge between two vertices if the dwarves of the houses represented by the vertices are friend with each other. The problem then translate to coloring the vertices with two colors. If the graph has no cycle then it is a tree, then we can look at the leaves of the tree and color them and go one layer up and color the nodes according to how many children node has the majority of colors and so on. However, what happen when there is cycle in the graph?

Answer 1

Your problem is known as majority dynamics. It is known that under rather general conditions, the behavior converges to a fixed point or to a cycle of length 2. Presumably in your case the rules are such that cycles of length 2 cannot happen. Try adapting the proof method in Goles and Olivos.

Answer 2

Since the problem is not well defined otherwise, I will assume the dwarves are a finite number.

If all dwarves repaint their houses at the same time, then as Evil pointed out, your thesis could be false (think of an isolated simple cycle of even length where the colors are alternated).

If on the other hand only a single dwarf repaints his house at any given time, your problem has an elementary solution.

Let $G=(V, E)$ be your graph. For each $u, v \in V$ let $\phi : V \times V\rightarrow \{1, -1\}$ be $1$ if $u, v$ are adjacent and have the same color, $-1$ if they are adjacent but differently colored, and $0$ if they are not adjacent.

We observe that a node $u$ may only change color if $$ \sum_{v \in V} \phi(u, v) \lt 0 $$

Therefore, the quantity $$ \Phi = \sum_{u,v \in V} \phi(u, v) $$

is strictly increasing. Since the graph is by hypothesis finite in size, there can only be finitely many changes of colors.