Saturday, 23 April 2016

mathematics - Professor Halfbrain's chessboard theorems


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



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



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



(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.




(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.




(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.


No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...