Professor Halfbrain's chessboard theorems

Question

Professor Halfbrain has spent his last weekend with analyzing $n\times n$ chessboards. Halfbrain says that a subset $S$ of squares on such a chessboard is queen-connected, if a chess queen can move around on $S$ and reach all the squares in $S$ while making only legal queen moves. (The queen is only allowed to move from squares in $S$ to squares in $S$, but the move may pass over other squares that are not necessarily in $S$. Every square in $S$ may be visited many times.)

Professor Halfbrain's first theorem: If the squares of an $n\times n$ chessboard with $n\ge2$ are painted red, then these red squares form a queen-connected set.

Professor Halfbrain's second theorem: If the squares of an $n\times n$ chessboard with $n\ge2$ are painted red and blue, then the red squares or the blue squares (or both) form a queen-connected set.

Professor Halfbrain's third theorem: If the squares of an $n\times n$ chessboard with $n\ge2$ are painted red and blue and yellow, then the red squares or the blue squares or the yellow squares (or two of these sets, or all three sets) form a queen-connected set.

Professor Halfbrain's fourth theorem: If the squares of an $n\times n$ chessboard with $n\ge2$ are painted red, blue, yellow and green, then at least one of the color classes must form a queen-connected set.

We all know Professor Halfbrain as an honorable and trustworthy mathematician, but even the best mathematician may sometimes be mistaken. Hence the question: Which of the Professor's four theorems do actually hold true?

Answer 1

Here's a community wiki containing all four of the answers presented by various people:

One-colour theorem

The queen can travel on all the squares of the grid.

Two-colour theorem

(answer by f'')

If a checkerboard is coloured red and blue, either there is a continuous path of neighbouring (by edge or corner) cells of a single colour from the top to the bottom, or a continuous path of neighbouring cells of a single colour from the left to the right.

A queen can travel on this path one square at a time, and therefore can access either every row or column of the checkerboard. From each position on the path, the queen can then access every square of the same colour on the grid.

Three-colour theorem

(answer by Fimpellizieri)

The following grid:

 2 1 1 3
 1 3 1 2
 1 1 3 2
 3 2 2 1

is a counterexample.

Four-colour theorem

(Answer by Joe Z.)

While the four-colour theorem is true, the following grid:

 1 2 3 4
 3 4 1 2
 2 1 4 3
 4 3 2 1

is a counterexample to the four-colour queen-accessibility theorem.

Answer 2

If a checkerboard is colored red and blue, either there is a continuous path of neighboring cells of a single colour from the top to the bottom, or a continuous path of neighboring cells of a single colour from the left to the right. (Neighboring includes diagonally touching cells.)

WLOG there is a red path from the top to the bottom. The path must contain a cell on each row. The queen can follow the path, taking detours to visit all the other red cells in each row before returning to the path.

Answer 3

Adding to Joe Z.'s answer, the third theorem is also false.

     2 1 1 3
     1 3 1 2
     1 1 3 2
     3 2 2 1

The the bottom-right 1, the top-left 2 and the middle 3's (versus the outer 3's) are each queen-isolated.

Thinking on something for the second theorem.

Answer 4

The first theorem is trivial — the queen can obviously travel onto all the squares of a grid.

---

Here's a counterexample for the fourth theorem, using a 4×4 grid:

1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1

For the colours 1 and 4, you can't reach the inner squares from the outer squares, and for the colours 2 and 3, you can't reach any of the squares from another square of the same colour.

Fun fact: This arrangement will work on an infinite grid when tiled. Each of the colours will be divided into two queen-connected subsets.