11
$\begingroup$

After his first set of theorems involving queen-accessibility, Professor Halfbrain started wondering about infinite chessboards rather than just ones with arbitrary large dimensions.

He came up with a few new theorems:

Theorem 1a. If the squares of an infinite chessboard are coloured with two colours, then the squares of at least one of the colours will form a queen-connected set.

Theorem 1b. If the squares of an infinite chessboard are coloured with three colours, then the squares of at least one of the colours will form a queen-connected set.

Theorem 1c. If the squares of an infinite chessboard are coloured with four colours, then the squares of at least one of the colours will form a queen-connected set.

Let a queen-connected component of a set $S$ of squares be a subset $C$ that is queen-connected, where no other squares in $S$ are queen-accessible from $C$.

Theorem 2a. If the squares of an infinite chessboard are coloured with five colours, then the squares of at least one of the colours will have fewer than five queen-connected components.

Theorem 2b. If the squares of an infinite chessboard are coloured with $n \ge 6$ colours, then the squares of at least one of the colours will have fewer than $n$ queen-connected components.

Can you prove or disprove these theorems? For which values of $n$ does theorem 2b hold true?

Improve this question
$\endgroup$
1
  • $\begingroup$ Theorem 1a seems obviously true. $\endgroup$
    – ghosts_in_the_code
    Oct 7, 2015 at 18:09

5 Answers 5

Reset to default
7
$\begingroup$

I believe the following two claims show that theorems

1b, 1c, 2a, 2b are all false.

Here are the claims:

Claim: On an infinite chessboard, there is an infinite set $S$ of queens such that no two queens attack each other and no square on the board is attacked by three queens.

Let $S$ be a finite set of red queens such that no two attack each other and no square is attacked by three queens. Place blue queens on all squares attacked by exactly two red queens. Now the set of all queens -- red and blue -- is a finite set of queens, and hence there is at least one square $q$ on the infinite chessboard not attacked by any red or blue queen.

Put a red queen on $q$ and add this red queen to $S$ to create a set $S'$ Then $S'$ is a set of queens where no two attack each other, since no two attack each other in $S$ and $q$ doesn't attack any other queens. Furthermore, no square is attacked three times by red queens, since $q$ would need to be one of the attacking queens, but then $q$ would be attacked by a blue queen from before, which is impossible.

Since we can continually add queens to $S$, by doing this infinitely many times we achieve an infinite $S$ which proves the claim.

Claim: It is possible to colour the squares of an infinite chessboard with three colors so that each color has an infinite number of queen-connected components.

Take an infinite set $S$ from the previous claim, and colour these squares red, blue, and green so there is an infinite number of each colour. For any square $q$ attacked by zero or more queens in $S$, colour it a different colour than any attacking queen. This is possible since there are at most two queens from $S$ attacking $q$ and we have three colours to work with. Hence every square in $S$ is its own isolated component, which proves the claim.

Improve this answer
$\endgroup$
0
4
$\begingroup$

Theorem 1c is

False.

We can colour the board as

 A B C D
 C D A B

and then tile this on the entire chessboard.

Improve this answer
$\endgroup$
3
$\begingroup$

Theorem 1a is also true and it 'follows' from the previous result. Suppose we have colored our infinite chessboard blue and red, and suppose without loss of generality the red squares are not queen-connected. In particular, there must be two red squares $r_1,r_2$ such that they cannot be connected by queen moves. We will show the blue squares must form a queen-connected set.

Let $b_1, b_2$ be any two blue squares. If they can be directly attacked by a queen from each other, there is nothing to prove. If they can't, pick large enough $n$ and an $n \times n$ chessboard $B$ that contains all of $r_1,r_2,b_1$ and $b_2$; it is clear this is always possible. Now simply apply Professor Halfbrain's second theorem to deduce the blue squares in $B$ must form a queen-connected set; in particular, $b_1$ and $b_2$ are queen-connected.

The important thing to take away from here is that if two squares are not queen-connected in a board $B$, they remain not queen-connected on a sub-board $B'$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ A non-topological argument is also possible in this case. If the red pair $r_1$, $r_2$ is disconnected, each square attacked by both of them is blue. Call one such square $b_1$, and the intesecting lines $s$ and $t$ (coming from $r_1$ and $r_2$ respectively). If one blue pair is disconnected, one of them does not reach $b_1$. Call it $b_2$. Call $t$ one line from $b_2$ which is not parallel to $r$ and $s$. We can connect our red pair by going from $r_1$ to $r\cap t$ to $t\cap s$ to $r_2$. $\endgroup$
    – MathET
    Oct 9, 2015 at 0:47
  • $\begingroup$ Also, I think you meant "Professor Halfbrain's second theorem: If the squares of an n×n chessboard with n≥2 are painted red and blue, then the red squares or the blue squares (or both) form a queen-connected set." $\endgroup$
    – MathET
    Oct 9, 2015 at 0:49
  • $\begingroup$ You are right, it should be the second theorem. I did not understand your previous argument though. $\endgroup$
    – Fimpellizzeri
    Oct 9, 2015 at 1:00
  • $\begingroup$ Wait a minute, I'll make an answer since the comment format is not very good for a detailed explanation $\endgroup$
    – MathET
    Oct 9, 2015 at 1:07
1
$\begingroup$

The "Theorem 1a" accepts another proof which doesn't depend on topological concepts.

We suppose that both colors are not queen-connected, and derive a contradiction.

If there are two squares in the red set ($r_1$ and $r_2$) which aren't queen-acessible from one another, each square attacked by both of them is blue. Otherwise, there would be a two-move path from one of the squares to the other.

Call one such square $b_1$, and the intesecting attack lines $s$ and $t$ (coming from $r_1$ and $r_2$ respectively).

Now, if one blue pair is not queen-connected, they can't both be able to reach a blue square, since that would imply the existance of a path from one another. So we can take one of our pair which is not connected to $b_1$ and call it $b_2$.

Call $t$ one attack line from $b_2$ which intercepts $r$ and $s$ at a pair of squares. This is always possible, because they are either both orthogonal (and intercepted by a diagonal), both diagonal (and intercepted by an orthogonal), or one orthogonal and one diagonal. In this case, the other orthogonal crosses both. Notice that two diagonals do not always intercept at a square.

Where $t$ crosses $r$, and $t$ crosses $s$, the square must be red, since a blue square would link $b_2$ (contained in $t$) to $b_1$ (contained in $r$ and $s$), which was assumed not to be the case.

We can connect our red pair by going from $r_1$ to $r\cap t$ to $t\cap s$ to $r_2$, since they are all red and all share one attack line with the previous square, contradicting our assumptions. Therefore, either we can't find a blue or a red disconnected pair, so one of the colors is queen-connected.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I understand what you meant now. It's just a pet peeve of mine, but this needn't have been a proof by contradiction. Supposing blue is not queen-connected, you in fact created showed 'constructively' that red must be queen-connected. $\endgroup$
    – Fimpellizzeri
    Oct 9, 2015 at 3:16
  • $\begingroup$ The red needs to be disconnected to show that $b_1$ is blue. Otherwise, there is no problem with the blue pair being connected to it, and the rest of the proof doesn't follow $\endgroup$
    – MathET
    Oct 9, 2015 at 12:56
  • $\begingroup$ Now that you brought it, it seems that there was a mistake in my proof. I was considering that two diagonal lines of attack always intersect at a square. The (corrected) proof still works, but not for the hexagonal case. $\endgroup$
    – MathET
    Oct 9, 2015 at 13:07
0
$\begingroup$

Theorem 1a is false. Here is an example which generates an infinite number of parallel strips of alternating colours. This is a configuration in which neither colour is "queen connected", even if each strip is.

1 2 1 2 1 2 ....

1 2 1 2 1 2 ....

1 2 1 2 1 2 ....

1 2 1 2 1 2 ....

1 2 1 2 1 2 ....

....

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Welcome to Puzzling! That seems to be referring to king-connectedness; a queen can easily move between strips. $\endgroup$
    – Deusovi ♦
    Sep 9, 2016 at 14:36
  • $\begingroup$ @Deusovi exactly how can a queen move from one stripe to another? $\endgroup$
    – Matsmath
    Sep 9, 2016 at 16:59
  • $\begingroup$ @Matsmath: Just use a single move to go from the top left square to the one two squares right. $\endgroup$
    – Deusovi ♦
    Sep 9, 2016 at 17:12
  • $\begingroup$ All right, I have no clue what is going on here. Perhaps I should read some similar, earlier puzzles. $\endgroup$
    – Matsmath
    Sep 9, 2016 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.