Czech and Slovak Republics 1997

For students of class 6-8 (age 12 to 14)
User avatar
Thamim Zahin
Posts:98
Joined:Wed Aug 03, 2016 5:42 pm
Czech and Slovak Republics 1997

Unread post by Thamim Zahin » Mon Feb 27, 2017 9:20 pm

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.
I think we judge talent wrong. What do we see as talent? I think I have made the same mistake myself. We judge talent by the trophies on their showcases, the flamboyance the supremacy. We don't see things like determination, courage, discipline, temperament.

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: Czech and Slovak Republics 1997

Unread post by samiul_samin » Sun Feb 18, 2018 3:31 pm

Hint
Denote the vertex $1,2,3,...,2n+1$
$Use mod 2$
Answer
It is always possible

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: Czech and Slovak Republics 1997

Unread post by samiul_samin » Sun Feb 18, 2018 3:33 pm

Solution You can get the solution in this book.
Mathematical Olympiads 1997-1998:Problems and solution from around the world

Naeem588
Posts:12
Joined:Sat Apr 03, 2021 1:41 am

Re: Czech and Slovak Republics 1997

Unread post by Naeem588 » Thu Apr 27, 2023 12:38 am

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 :(

Naeem588
Posts:12
Joined:Sat Apr 03, 2021 1:41 am

Re: Czech and Slovak Republics 1997

Unread post by Naeem588 » Thu Apr 27, 2023 12:44 am

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 :(

Post Reply