FelixD wrote: We colour every square of the $ 2009$ x $ 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. I am quite not sure about the part 'intermediate stops' of a sequence of queen's moves. Could anyone (like those who has solved it) explain a bit more about this, please?

epsilonist wrote: I am quite not sure about the part 'intermediate stops' of a sequence of queen's moves. Could anyone (like those who has solved it) explain a bit more about this, please? Well, a color is called connected if a chess queen can move to any square of that color without stopping on squares of different color. So, for example, A is connected on the following board whereas B isn't (because the B in the first line is "separated" from the others): A A B A B A A A A B A B B B A B

A counterexample for 4 colours is as following ABCDABCDABCD... CDABCDABCDAB... ABCDABCDABCD... CDABCDABCDAB... ABCDABCDABCD... .................. It seems 3 colours should work, but don't know how to prove.

Counterexample for 3 colors: Color square (1,1), the top left corner, with A. Color (2008, 2008) with B. Color (1, 2008) and (2008, 1) with C. Of the remaining squares, color all of them on the top row and left column B, all squares on the main diagonal C, and color the rest A. Then all three colors are disconnected, as the first four squares I noted form connected components for each color. To show 2 works: take a connected component of As. If this component spans all columns, it can reach every square on the board, meaning A is connected. Otherwise, we can find two adjacent columns, one of which has A's from this component (call this column $x$) and one of which has no A's (call this column $y$). In each row, take the square from column $x$ if it has a B instead of an A and otherwise take the B on column $y$. This gives us a B in every row, and these Bs form a connected component, so they can reach every square. Thus the Bs are connected.

Counterexample for 2 colors: aaaaaaa...... bbbbbbb...... aaaaaaa...... bbbbbbb...... . . . . . is it right?

I have found a solution in https://skmo.sk/dokumenty.php. But this is written in Slovak, can someone help to translate it into English? The first page:

Attachments:

The second page:

Attachments: