Connected colours on 2009 x 2009 board
Source: MEMO 2009, problem 4, team competition
October 1, 2009
combinatorics proposedcombinatorics
Problem Statement
We colour every square of the x board with one of 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 , such that for every colouring of the board at least on colour present at the board is connected.