In the previous post we brought up a question as follows:
[Czech and Slovak Republics 1997]
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.
Lets take the four sided square now as n = 4. At each vertex we have two edges and a diagonal incident on it. Let us say the edges are alternatively blue and green and the diagonal is also alternatively blue and green. We again have the same condition that at a vertex, we have a simple majority of one color or all colors the same.and there will be another vertex with the colors switched.
Let us say the simple majority was green and the number of blue segments to this vertex is odd.
The initial configuration is therefore
X G r e e n Y
G B G B
r l r l
e u e u
e e e e
n n x x
Z B l u e W
Where X, Y, Z and W are vertices. As noted earlier vertex X has 1 blue while W has all three blues.
If we make a move at X, the two greens become blue and the diagonal XW becomes green leaving leaving the total count of blues even at any given vertex.
The total number of edges in a square is 4 and with diagonals the count is 6 an even number, the blues and greens can be divided in sets (1,5)(2,4)(3,3). Therefore permitting them to switch the colors at a vertices will not add or subtract the total count but it can be made even because there will be odd number of vertexes with opposite number of colors. While the initial coloring configuration is unique and the flipping sequence to make the coloring at a vertex even and blue is also unique.
Since we verified for both n = odd and n = even, we can state the same for all n>= 3. Formal proof may be shown by induction method.
[Czech and Slovak Republics 1997]
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.
Lets take the four sided square now as n = 4. At each vertex we have two edges and a diagonal incident on it. Let us say the edges are alternatively blue and green and the diagonal is also alternatively blue and green. We again have the same condition that at a vertex, we have a simple majority of one color or all colors the same.and there will be another vertex with the colors switched.
Let us say the simple majority was green and the number of blue segments to this vertex is odd.
The initial configuration is therefore
X G r e e n Y
G B G B
r l r l
e u e u
e e e e
n n x x
Z B l u e W
Where X, Y, Z and W are vertices. As noted earlier vertex X has 1 blue while W has all three blues.
If we make a move at X, the two greens become blue and the diagonal XW becomes green leaving leaving the total count of blues even at any given vertex.
The total number of edges in a square is 4 and with diagonals the count is 6 an even number, the blues and greens can be divided in sets (1,5)(2,4)(3,3). Therefore permitting them to switch the colors at a vertices will not add or subtract the total count but it can be made even because there will be odd number of vertexes with opposite number of colors. While the initial coloring configuration is unique and the flipping sequence to make the coloring at a vertex even and blue is also unique.
Since we verified for both n = odd and n = even, we can state the same for all n>= 3. Formal proof may be shown by induction method.
No comments:
Post a Comment