Let $n$ be natural number. Each of the numbers $\in\{1,2,\ldots ,n\}$ is coloured in black or white. When we choose a number, we flip it's colour and the colour of all the numbers which have at least one common divider with the chosen number. At the beginning all the numbers were coloured white. For which $n$ are all the numbers black after a finite number of changes?
Problem
Source: Swiss Imo Selection 2006
Tags: combinatorics proposed, combinatorics
grobber
26.05.2006 13:15
The following problem has been discussed, in various formulations, several times on the forum (and it has received several solutions; I remember giving an algebraic one, but there were combinatorial proofs as well): Given a graph $G$ (in which eac vertex is considered to be connected to itself) there is a subset $V$ of vertices such that every vertex of $G$ is connected to an odd number of vertices in $V$. Apply this to the graph having $1,\ldots,n$ as vertices and in which $i$ is connected to $j$ iff they are not coprime. This should prove that every positive integer $n$ works: choose precisely the numbers belonging to the set $V$ provided by the problem above, and perform the changes on those; this will change the color of all the numbers, as can easily be seen.
BogG
26.05.2006 13:31
Thank you I will look more P.S What is "vertices" ?? You can tell in Rumanian maybe.. lol
mathmanman
26.05.2006 15:37
Well, since you seem to speak french, I'll tell it in french : sommets.
BogG
26.05.2006 16:40
merci bien ^^
JuanOrtiz
20.04.2014 02:27
I prove this for any graph (I prove the result grobber stated). We use induction. Base case is trivial. We say a graph "works" if we can touch vertices such that from a configuration of all-white, we reach a configuration of all-black. Now assume any graph with $n-1$ vertices works. Then take a graph $G$ with $n$ vertices. "Forget" about one of $G$'s vertices, and apply the inductive hypothesis. If the vertex you forgot about turns black, we're done. So this vertex stayed white. So we now have a method for changing the color of all the vertices except for one, and we can choose this one. If $n$ is even, apply this method for all vertices and we're done. If $n$ is odd, apply this method for all vertices except two. We now have a method to change the color of all vertices except for two, and we can choose these two. We call this method, method $X$. So, since there are an odd number of vertices in $G$, there must be a vertex $V$ with an even degree. Touch this vertex $V$. Change the color of the remaining vertices using method $X$ $(n-d(V)-1)/2$ times. Now we have reached the all-black configuration. So we're done.