MEMO 2009 ekipno problem 4

  Avg: 2.0
  Avg: 6.0
Dodao/la: arhiva
April 28, 2012
We colour every square of the 2009 \times 2009 board with one of n colours (we do not have to use every colour). A colour is called connected if either there is only one square of that colour or any two squares of the colour can be reached from one another by a sequence of moves of a chess queen without intermediate stops at squares having another colour (a chess quen moves horizontally, vertically or diagonally). Find the maximum n, such that for every colouring of the board at least on colour present at the board is connected.
Source: Srednjoeuropska matematička olimpijada 2009, ekipno natjecanje, problem 4