The vertices of a regular $n$-gon are initially marked with one of the signs $+$ or $-$ . A move consists in choosing three consecutive vertices and changing the signs from the vertices , from $+$ to $-$ and from $-$ to $+$. a) Prove that if $n=2015$ then for any initial configuration of signs , there exists a sequence of moves such that we'll arrive at a configuration with only $+$ signs. b) Prove that if $n=2016$ , then there exists an initial configuration of signs such that no matter how we make the moves we'll never arrive at a configuration with only $+$ signs.
Problem
Source: Romania JBMO TST 2015 Day 3 Problem 4
Tags: algebra, linear algebra, invariant, combinatorics
junioragd
15.05.2015 11:23
I wonder why these kinds of problems are selected,basicaly just solving Xi+Xi+1+Xi+2=r(mod2)... a)Let $Xi$ be the number of times we performed a move on a triple which starts with $i$.Since performing a move twice is equivalent with not performing it,every $Xi$ is $1$ or $0$.Now,pick some vertex labelled with $i$.We have that Xi+X(i+1)+X(i+2)=$1(mod2)$ if on that vertex is $-$ and else it is $0$ $mod2$.Now,sum equations for vertices $3,4,6,7,9,10...,2013,2014,1$ and we get the value of $X2015$.Simary,we obtain the values of others and it is easy to prove that it satisfayes the equations. b)Labell them $1,2,3,..2016$ and consider all labells whcih are $3k+1$ and $3k+2$.The number of $+$ signes $mod2$ is invariant,so let labell $1$ be $+$ and the rest of them be $-$. Since on labells $3k+1$ and $3k+2$ we must have an even number of $+$ signes,we can never reach a configuration with all $+$ signes.
aleksam
02.06.2015 16:19
The a) part could be solved by induction with step 3. Base, $n=5$ is easy to check by hand. For inductive step, we have that for some $n=3k+2$, we can always reach the configuration with all pluses. Now, add tree consecutive vertices(we will cal them X, Y, and Z, from left to right), and we will call hem new vertices. Obviously, we can set those three vertices to be pluses if we don't care about other vertices. Now, we want to prove that we can use the inductive hypothesis on the rest of vertices. Only problem is when we want to perform a move between vertices that have been separated with three new vertices, WLOG, let two of them be on the left side of three new vertices(we will call them A and B), and the last at the right side of new vertices (we call him C). Instead of one move, we will perform three of them, on the triples: (A, B, X), (X, Y, Z) and (Y, Z, C). The result is the same, and this means that we we can always perform a sequence of moves resulting in configuration whith all pluses.