MathDB
Colouring of 2001 points on a circle

Source: Baltic Way 2001

November 17, 2010
combinatorics proposedcombinatorics

Problem Statement

Let 20012001 given points on a circle be coloured either red or green. In one step all points are recoloured simultaneously in the following way: If both direct neighbours of a point PP have the same colour as PP, then the colour of PP remains unchanged, otherwise PP obtains the other colour. Starting with the first colouring F1F_1, we obtain the colourings F2,F3,….F_2,F_3 ,\ldots . after several recolouring steps. Prove that there is a number n0≤1000n_0\le 1000 such that Fn0=Fn0+2F_{n_0}=F_{n_0 +2}. Is the assertion also true if 10001000 is replaced by 999999?
Back to ProblemsView on AoPS