4
$\begingroup$

If you watched the Queen's Gambit you'll know that there are lots of upside-down chess boards all over the world's ceilings. If not just take my word for it. The same is true of the actual sky only there is only one infinite chess board there. During daytime the sky is light because there are very few pieces on the board. The pieces themselves are transparent but each piece covers some squares and blocks all light from passing through these squares. You wouldn't notice for what are a few dark squares when there are infinitely many light ones? In the evening the Knights, infinitely many of them, gather and together they cover almost the entire sky. They take great care in making sure that there are no squares double covered for this would create a black hole and instantly erase this world. While they enjoy the darkness they know others don't, so they leave a small set of squares uncovered. These are the stars. Stars can never touch for the combined light of two adjacent stars would blind a Knight.

This story is entirely true except for one detail. Can you find it?

For those who don't read stories:

An infinite square grid (parameterised by pairs of integers) is covered by sets of the form N(x,y)={(x+/-1,y+/-2),(x+/-2,y+/-1)} (Knights) and S(x,y)={(x,y)} (Stars) subject to: 1. Each square is covered exactly once and 2. stars cannot touch i.e. for any two stars S(x,y) and S(x',y') we have max(|x-x'|,|y-y'|) > 1. Find a simple and convincing argument showing that there are no stars.

$\endgroup$

1 Answer 1

3
$\begingroup$

A knight covers eight squares of the same colour on the chessboard, and each star also covers only one colour obviously, so we can look at only one of the colours and the knights/stars that cover it.

Consider the 8 squares covered by a single knight. This consists of four pairs of diagonally adjacent squares, and these surround a region of 4 uncovered squares. This region cannot be covered by only stars since the squares are adjacent, so there must be some coverage by another knight, and it can only cover one adjacent pair. There is essentially only one way to do this without overlap (up to rotational symmetry).

enter image description here

That leaves two adjacent uncovered squares, which again cannot be covered by only stars. There is only one way to cover this by a knight. This process repeats, where each newly placed knight separates of a pair of adjacent squares that can only be covered by another knight. This forms a diagonal chain of knights, covering a band with no uncovered holes for the stars (at least not of the squares of our chosen colour - the other colour comes later).

enter image description here

The above shows that every knight is by necessity part of a diagonal chain. As there is no overlap, all the chains (on our chosen colour) must be parallel. Any gap between two chains cannot be covered by stars alone, so the chains must be adjacent without any gaps between them. Therefore there are no squares (of our chosen colour) left for the stars.

The same is true of the squares of the other colour. These will also be covered by chains of knights, but they can be either parallel or perpendicular to the chains of the first colour as they don't interact with them in any way.

$\endgroup$
2
  • $\begingroup$ Yep, that's more or less what I had in mind. Well done. Btw., did you notice that this also proves that there is no solution for the similar problem: no stars but we also count each knight's current position as covered? $\endgroup$
    – loopy walt
    Jul 19 at 7:18
  • $\begingroup$ @loopywalt I had not noticed that, but you're right. You can't place two knights diagonally adjacent to each other (because that double-covers two squares) so the same reasoning applies, meaning no knights can be placed on the squares of one colour. The same holds for the other colour so there is no solution. $\endgroup$ Jul 19 at 7:51

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.