Each side and diagonal of a regular $n$-gon $(n ≥ 3)$ is colored
blue or green. A move consists of choosing a vertex and
switching the color of each segment incident to that vertex
(from blue to green or vice versa). Prove that regardless of the
initial coloring, it is possible to make the number of blue
segments incident to each vertex even by following a sequence
of moves. Also show that the final configuration obtained is
uniquely determined by the initial coloring.
My approach is as follows:
Let $v_1, v_2 , …, v_n$ be the vertices of regular $n$-gon. Let $b_i$ and $g_i$ denote the number of blue and green vertices of vertex $v_i$ for $1 \leq i \leq n$.
$1)$ Then assume $n$ is even.
Note that every vertex of regular $n$-gon is incident with $n-1$ edges. Consider a vertex $v_j$ where $1\leq j \leq n$. We consider some cases:
If $v_j$ has even number of blue segment incident then we consider some other vertex with odd number of blue segments. Assume, then $v_j$ has odd number of blue segments. Then we have
$b_j+g_j=n-1 \equiv 1 (mod2)$. This means that we have even number of green segment. So we can apply move to $v_j$ changing the parity of both blue and green segments. In this case we are done!
Now assume that every segment incident to $v_j$ is colored green (The case where every segment is colored blue can be done similarly). Note that there are odd numbers of green segment incident to $v_j$. Apply move at vertex $v_j$ and all the green segments change into blue. Then pick any vertex incident to $v_j$ say $v_k$ with $j \neq k$ and apply move to vertex $v_k$. Note that every vertex $v_i, i \neq j$ is adjacent to $v_j$ exactly one time. So this changes the color of segment $v_jv_k$ from blue to green. And in this case we are done as well!
$2)$ Assume $n$ is odd.
Note that every vertex of regular $n$-gon is incident with $n-1$ edges. Consider a vertex $v_j, 1 \leq j \leq n$. Then we have $b_j + g_j = n-1 \equiv 0 (mod 2)$.
We again consider some cases:
If all segments are colored in green, then since there are even number of segments incident to $v_j$ we can simply apply move to $v_j$ to get the desired coloring.
Suppose there are odd number of green segments and odd number of blue segments incident to $v_j$. Then we pick a vertex $v_k, j \neq k$ such that $v_k v_j$ is colored green. We apply move at $v_k$, this changes the color of segment $v_jv_k$ from green to blue and this make number of blue segments incident to $v_j$ even. And in this case we are done as well.
Now repeat this algorithm until we make the number of blue segments incident to each vertex even by following a sequence of moves. Note that this also proves final configuration is uniquely determined by initial coloring.
So is there any flaws in my argument? Or my entire proof might be incorrect as well. Please take some time to review it. I'm completely new to combinatorics and I'm not confident about my arguments/proofs. Thank you!
Best Answer
I believe this is a $0^+$ solution for the following reasons: