13
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 1. The first theorem is obviously correct; just have the queen move horizontally sweeping back and forth across every square. $\endgroup$ – Joe Z. Oct 3 '15 at 15:15
  • $\begingroup$ Also, I know an arrangement that doesn't work for five colours off the top of my head, but not four... $\endgroup$ – Joe Z. Oct 3 '15 at 15:16
  • $\begingroup$ Can you illustrate what you mean when you say that the squares are painted? I don't suppose you mean randomly selected squares are painted. $\endgroup$ – dennisdeems Oct 5 '15 at 13:58
  • $\begingroup$ @Gamow Then when you say the squares are painted red, blue, yellow, and green, it may be the case that every square is blue and no square is any other color. $\endgroup$ – dennisdeems Oct 5 '15 at 15:57
  • $\begingroup$ @dennisdeems: yes, indeed, this may be the case. $\endgroup$ – Gamow Oct 5 '15 at 15:59
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oops, I forgot to make it CW and then it got its first upvote. :( $\endgroup$ – Joe Z. Oct 5 '15 at 9:09
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not quite sold on the first claim (the first paragraph), but if it's true then the second paragraph very clearly solves the problem. $\endgroup$ – Fimpellizieri Oct 3 '15 at 19:21
  • 1
    $\begingroup$ @Fimpellizieri It's true. Suppose there is no continuous path of neighboring red cells from the top to the bottom. Now consider the borders of the disconnected red regions. These must be continious. Another more intuitive way is to think of the red cells as land and the blue as water. To prevent a bridge from top to the bottom, you must have a continuous river across. $\endgroup$ – Rohcana Oct 3 '15 at 19:56
  • 1
    $\begingroup$ @Fimpellizieri It's a well-known theorem in graph theory/topology called the Hex theorem. $\endgroup$ – Joe Z. Oct 3 '15 at 19:57
  • $\begingroup$ @Anachor But there is still need to prove that at least one of them goes from left to right. Some may be in a circle, others start from the sides and come back around, and so on... $\endgroup$ – MathET Oct 3 '15 at 20:31
  • 3
    $\begingroup$ @IvanBarreto First append a row of red cells above the topmost row. Now, consider the topmost red region. The bottom border of this region is a river, ie. a continuous blue region. $\endgroup$ – Rohcana Oct 3 '15 at 20:39
11
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.