3
$\begingroup$

Each side and diagonal of a regular $n$-gon ($n\geq 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 from green to blue). 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.

This questions is confusing me: Label the vertices $a_1,a_2,\dots a_n$ Now let $M(a_i)$ denote the move being applied to vertex $a_i$. Also let $b_i$ be the number of blue segments incident to vertex $a_i$ and define $g_i$ similarly. We have $b_i+g_i=n-1$. Consider some even $n$. Now consider $M(a_1)$. This swaps the colors of all edges incident to $a_1$, but this means that $b_1$ and $g_1$ are swapped. Since $b_1+g_1=n-1\equiv 1 \pmod{2}$, the parity of $b_1$ changes. However now consider what happens to some $a_k$ for $k\neq 1$. The edge joining $a_k,a_1$ swaps colors, while all other segments incident to $a_k$ remain the same color. Note that this either increases $b_k$ by one (hence decreasing $g_k$ by one), or the other way around. This means that the parity of $b_k$ changes as well.

But this means that applying the move $M(a_1)$ changes the parity of every single vertex. So that means if we start with any configuration were the parity of all $b_i$ is not the same, then it is impossible to reach a point where all $b_i$ are even.

For example, consider the case $n=4$ for a square. Initially color the segments $A_1A_2,A_2A_3,A_3A_4,A_4A_1,A_1,A_3$ blue and color $A_2A_4$ green. Then we have $b_1=b_3=3,b_2=b_4=2$, and I haven't been able to find a way to apply moves in such a way to make all the $b_i$ even.

If someone could tell me where my logic is going wrong (or if I misinterpreted the problem), and give me a way to solve the problem for the square case I mentioned above, that would be great. I don't need a solution to the problem yet.

$\endgroup$
2
1
$\begingroup$

I think this works for the first part.

Consider the complete graph $K_n$ with $n$ an odd number. Label the vertices $A_1,A_2,\dots A_n$ Let $b_i$ denote the number of blue segments incident to $A_i$. Let us start out with $k$ of the $b_i$ even and the other $n-k$ of them odd.

We start with the following initial observations:

Lemma 1: The $k$ we start out with is odd.

Proof: Assume that $k$ is even, and without loss of generality let the $k$ vertices $A_1,A_2,\dots A_k$ have even $b$ while the $n-k$ vertices $A_{k+1},A_{k+2},\dots A_n$ have odd $b$. Then the number of blue edges is given by $\frac{1}{2}\sum_{i=1}^n b_i$. But, we have $\sum_{i=1}^k b_k$ is even, while $\sum_{i=k+1}^n b_k$ is odd (since $n-k$ is odd), so the total sum is odd, a contradiction because in this case there isn't an integer number of initial blue edges.

Lemma 2: Applying a move to any vertex $A_i$ will preserve the parity of $b_i$ while swapping the parities of all $b_j$ for $j\neq i$.

Proof: Since we are swapping the colors of all edges incident to vertex $A_i$, $b_i$ will change to $n-1-b_i$. But since $n-1\equiv 0\pmod{2}$, and since we have $b_i\equiv -b_i\pmod{2}$, the parity of $b_i$ stays the same. However, vertex $A_j$ for $j\neq i$ only has one of the edges incident to it's color swapped: edge $A_iA_j$. Therefore $b_i$ turns into $b_i \pm 1$ (depending on what color $A_iA_j$ is), changing it's parity.

Now consider the following algorithm:

Apply the move to any vertex $A_i$ such that $b_i$ is odd. After this move, we have $n-k-1$ vertices with $b$ even and $k+1$ vertices with $b$ odd. Now apply the move to any vertex $A_j$ such that $b_j$ is even. After this move, we have $k+2$ vertices with $b$ even and $n-k-2$ vertices with $b$ odd. This monotonically increases the number of vertices with $b_i$ even.

We know we can always apply the algorithm unless there are no more odd vertices, in which case we are done, so it suffices to continuously apply this algorithm. $\blacksquare$

Edit: Found a solution to show uniqueness.

Consider two arbitrary vertices $A_i,A_i, 0\leq i\neq j\leq n$.

Claim: If $b_i\equiv b_j\pmod{2}$, then the edge $\overline{A_iA_j}$ will end up the same color as it started with. If $b_i\neq b_j\pmod{2}$, then the edge $\overline{A_iA_j}$ will end up the opposite color that it started with.

Proof: First we take the case where $b_i\equiv b_j\pmod{2}$. Now consider $M(A_i)$. This swaps the parity of $b_j$ while keeping the parity of $b_i$ (this is Lemma 2). However, now $b_i,b_j$ are opposite parities, meaning one of them is odd. Because any $M(a_k),k\neq i,j$ would change the parity of both $b_i,b_j$, it is impossible to get them the same parity, and hence impossible to get both of them even, without either $M(A_i)$ again or $M(A_j)$. In either case, $\overline{A_iA_j}$ returns to its original color. Now consider the case where $b_i\neq b_j\pmod{2}$. In this case, note that $M(A_k),k\neq i,j$ will change the parity of both $b_i,b_j$, so we must use either $M(A_i)$ or $M(A_j)$, hence swapping the color of $\overline{A_iA_j}$. However, if we were to use either $M(A_i),M(A_j)$ again, then the parities of $b_i,b_j$ would be different, meaning it would be impossible to get both of them even without applying $M(A_i),M(A_j)$ a third time. $\blacksquare$

Note that when $b_i\equiv b_j\pmod{2}$, move $M(A_x),x\in\{i,j\}$ must be applied an even number of times to reach the desired configuration. When $b_i\neq b_j\pmod{2}$, move $M(A_x),x\in\{i,j\}$ must be applied an odd number of times to reach the desired configuration.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.