1
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ The questions claim that the final configuration is unique isn't true. Consider $n = 4$ with starting configuration $1-2, 3-4$ blue. Toggling 1 gives us $1-3, 1-4, 3-4$ which satisfies the conditions. Toggling 2 gives us $2-3, 2-4, 3-4$ which also satisfies the conditions. More generally, for even $n$, you can toggle any 2 vertices and not change the parity. This is obvious by counting. $\endgroup$ – Calvin Lin Oct 24 '20 at 23:51
  • 1
    $\begingroup$ In addition, it can be shown that for even $n$, there are scenarios where we can't get the desired configuration. Proof: Work modulo 2. Color "blue" as +1 and "green" as 0. Toggling a vertex would add 1 to each of its edges. The goal is for each vertex sum to be 0. When $n$ is even, pick a configuration where one vertex $v_1$ has an even sum and another vertex $v_2$ has an odd sum. Observe that parity of $v_1 + v_2$ doesn't change when we toggle any vertex, hence one of them must be odd at the end of each toggle, so we can't be at the desired configuration. $\endgroup$ – Calvin Lin Oct 24 '20 at 23:55
  • 2
    $\begingroup$ As such, I believe that $n$ must be odd. $\endgroup$ – Calvin Lin Oct 24 '20 at 23:56
2
$\begingroup$

I believe this is a $0^+$ solution for the following reasons:

  1. You didn't show that your algorithm must terminate. You might get caught in an endless loop.
  2. You didn't prove that for any sequence of steps (that anyone takes) which leads to "all even", the final configuration is the same.
$\endgroup$
0

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.