BdMO Online Forum

Each side and diagonal of a regular $2n+1$-gon ($2n+1 \ge 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.

Hint Answer

Solution You can get the solution in this book.

Let us label the vertices as $A_1,A_2,A_3, \ots ,A_{2n+1}$.

Every vertex has $2n$ edges. Let $D_i$ be the number of blue edges incident to $A_i$ (For all $0<i\e 2n+1$). Then $2n -D_i$ is the number of green edges incident to $A_i$. It's obvious that $D_i$ and $2n -D_i$ have the same parity. Every vertex is connected with all other vertices through green or blue edges. So if we select one vertex $A_j$ for our move than parity of $D_j$ will be unchanged but parity of every other $D_i$ will Change. Because exactly one edge of every vertex has changed it's colour.


Lemma: Initially we must have odd number of even $D_i$'s and even number of odd $D_i$'s.

Proof: It can be easily proved by the fact that the sum of all degrees is always even.


Let the number of odd $D_i$'s be $p$. We want to make $p=0$ after some moves.

We will take an odd $D_i$ for our first move. Now number of even $D_i$'s equals to $p_0 -1$. Now let us take an even $D_i$. So the number off odd $D_i$'s will become $p_0 -2$ !!

If we follow the same algorithm our $p$ will be reduced by $2$ every time. And because $p$ was even initially, it will come to $0$.

Hence our proof is complete for the first question.


For the second question because we will need even number of moves, the number of blue and green segments shall remain the same. That's all I can say for now

Let us label the vertices as $A_1,A_2,A_3, \dots ,A_{2n+1}$.

Every vertex has $2n$ edges. Let $D_i$ be the number of blue edges incident to $A_i$ (For all $0<i\le 2n+1$). Then $2n -D_i$ is the number of green edges incident to $A_i$. It's obvious that $D_i$ and $2n -D_i$ have the same parity. Every vertex is connected with all other vertices through green or blue edges. So if we select one vertex $A_j$ for our move than parity of $D_j$ will be unchanged but parity of every other $D_i$ will Change. Because exactly one edge of every vertex has changed it's colour.


Lemma: Initially we must have odd number of even $D_i$'s and even number of odd $D_i$'s.

Proof: It can be easily proved by the fact that the sum of all degrees is always even.


Let the number of odd $D_i$'s be $p$. We want to make $p=0$ after some moves.

We will take an odd $D_i$ for our first move. Now number of even $D_i$'s equals to $p_0 -1$. Now let us take an even $D_i$. So the number off odd $D_i$'s will become $p_0 -2$ !!

If we follow the same algorithm our $p$ will be reduced by $2$ every time. And because $p$ was even initially, it will come to $0$.

Hence our proof is complete for the first question.


For the second question because we will need even number of moves, the number of blue and green segments shall remain the same. That's all I can say for now