18
$\begingroup$

Recently the British newspaper The Guardian published the following puzzle, titled Naughty Knights:

enter image description here

And here's the solution published by the newspaper later:

enter image description here

Unfortunately, this solution doesn't actually prove that you can't place more than 32 knights. Sure, you can't add any more knights to the above arrangement, but who said you must place the first 32 knights exactly as shown above?

Thinking about it, I found an elegant proof showing that you can't place more than 32 knights, and thought that finding a proof is a good puzzle on its own.

Question: How do you prove that you can't place more than 32 non-attacking knights on a chessboard?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
35
$\begingroup$

Simply group all the squares into pairs a knight's move apart: enter image description here
At most one square in each pair can be occupied, and there are 32 pairs, so there are at most 32 knights.

Improve this answer
$\endgroup$
9
  • 4
    $\begingroup$ One can also prove this using a rot13(pybfrq xavtugf gbhe), but I prefer the proof you gave since it is more obvious. $\endgroup$
    – Jaap Scherphuis
    Commented Dec 20, 2023 at 14:04
  • 1
    $\begingroup$ I'm not sure this is sufficient proof, since this only accounts for this very specific configuration of pairs. $\endgroup$
    – Ivo
    Commented Dec 21, 2023 at 13:23
  • 2
    $\begingroup$ The pairs cover the entire board, so any arrangement of knights on the board divides them among the pairs. $\endgroup$
    – AxiomaticSystem
    Commented Dec 21, 2023 at 13:42
  • 2
    $\begingroup$ I make pairs because I can easily show that no pair can be more than half-full. Decomposing the board into pairs means that the board can't be more than half-full $\endgroup$
    – AxiomaticSystem
    Commented Dec 21, 2023 at 14:20
  • 4
    $\begingroup$ @Ivo Yes, linking is not unique. EVERY linking prevents some solutions. And it doesn't matter which other squares are already attacked, it matters which aren't. This linking tells you that at most one of pair can have knight. With 32 pairs => 32 knights. It could be that, because of some other linking, neither of pair tiles can have knight. But this linking alone is sufficient to show that both squares cannot have knights. $\endgroup$
    – Zizy Archer
    Commented Dec 22, 2023 at 11:04
17
$\begingroup$

To add to the excellent proof posted by @AxiomaticSystem, I am posting my own proof. It came to my mind when I was riding in public transport and couldn't draw anything, so my proof doesn't rely on any drawing or diagram at all :)

(1) Let's suppose that we have managed to place more than 32 non-attacking knights on a chessboard.

(2) We know that a knight's tour exists. A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once.

(3) Now, having a chessboard with more than 32 non-attacking knights on it, let's number the squares in accordance with a knight's tour. Now each square has a unique number between 1 and 64.

(4) There must be at least one pair of squares with adjacent numbers (like 19 and 20) that are both occupied by knights, for we have more than 32 knights and only 64 squares.

(5) The knights on those two squares attack each other, because one of those squares is reached in one move from the other in the tour we chose in order to number the squares.

(6) But the knights were assumed to be non-attacking, so we have arrived at a contradiction. So, assumption (1) is impossible. Quod erat demonstrandum.

Despite my proof not relying on any diagram, I very much like the proof by @AxiomaticSystem because it doesn't rely on any special knowledge like the one about the existence of a knight's tour :)

Improve this answer
$\endgroup$
7
  • $\begingroup$ Can you please elaborate point-4 ? I'm a newbie to puzzling unfortunately. $\endgroup$
    – An_Elephant
    Commented Dec 21, 2023 at 7:31
  • 2
    $\begingroup$ @An_Elephant There are 33+ knights and 31- empty squares you want to position on the tour. As there are more knights than empty squares, two knights have to be adjacent. $\endgroup$
    – Zizy Archer
    Commented Dec 21, 2023 at 8:42
  • 1
    $\begingroup$ @An_Elephant Another way to see it is to group the squares in the tour in pairs. 1 with 2, 3 with 4, and so on. There are 32 pairs and 33 knights. So there must be a pair with 2 knights, i.e., they're adjacent. $\endgroup$
    – justhalf
    Commented Dec 21, 2023 at 11:51
  • $\begingroup$ @ZizyArcher Thanks. I'm a slow learner but I understand it now. $\endgroup$
    – An_Elephant
    Commented Dec 21, 2023 at 13:24
  • 1
    $\begingroup$ I like this proof, but it's a superfluous use of proof by contradiction. With minor adjustments, it can be made a direct proof of the wanted result. $\endgroup$
    – John Bollinger
    Commented Dec 23, 2023 at 20:42
0
$\begingroup$

EDIT: Below is not right, thanks to Especially Lime for pointing it out.

I think the fact that a knight can only attack the opposite color squares is already proof that 32 is the max.

A knight always covers both colors. Therefore whichever placement you have you can't have more than 64/2=32 knights. Either use just 1 color, or force compensation for attacking usable squares.

Consider a strategy where you use both colors: a knight always takes up an attackable square by occupying it, but now it also takes up X squares by attacking the opposite color. So the most efficient you can be while using different colored knights is having it take up X=1 square by its attack, and 1 square by its occupation

Intuitively, but without thinking about it further, I also think that this means the only possible multicolored solution is to have an even distribution of colors.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I don't think that argument can work. For example, consider a piece that only attacks the squares 3 away horizontally or vertically. On a 9x9 chessboard, you could fit 45 of these without attacking by taking alternating 3x3 squares. Take this configuration and remove an end row and column to leave 34 of them on an 8x8 chessboard. $\endgroup$
    – Especially Lime
    Commented Dec 22, 2023 at 21:02
  • 1
    $\begingroup$ You are right, something went wrong in my reasoning haha. $\endgroup$
    – Rutger Broekkamp
    Commented Dec 22, 2023 at 23:32

Your Answer

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

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