Waste less time on Facebook — follow Brilliant.
×

Related to Open Problem #1: Exploring the Edge

On a chessboard of a finite size, we want to place kings and knights such that each king attacks exactly 2 kings and 2 knights, and each knight attacks exactly 2 kings and 2 knights.

If some smallest, finite board exists that fulfills the requirements, we know the following of that board:

  • The board has edges
  • Every edge has at least one piece on it

In the boards, I’m going to use black pawns to mark squares that have to be empty, and white pawns to mark squares that need to have either a king or a knight, but it’s not yet clear which of the two.

The piece on the edge can be either a king, or a knight, which means at least one of the following 20 formations (or a vertical reflection of one of those) has to be somewhere on the board:

  • King 1 (impossible)
  • King 2 (impossible)
  • King 3 (impossible)
  • King 4 (impossible)
  • King 5 (impossible)
  • King 6 (impossible)
  • King 7 (still plausible)
  • King 8 (still plausible)
  • King 9 (impossible)
  • King 10 (still plausible)
  • King 11 (still plausible)
  • King 12 (impossible)
  • King 13 (impossible)
  • King 14 (impossible)
  • King 15 (impossible)
  • King 16 (still plausible)
  • Knight 1 (still plausible)
  • Knight 2 (still plausible)
  • Knight 3 (still plausible)
  • Knight 4 (still plausible)

If it’s possible to prove all of these 20 formations are impossible, it’s proven no piece can be on the edge. That would contradict the idea a finite, smallest board exists, which in turn would prove there is no finite, valid board.

So far I’ve been able to proof that 11 of these 20 formations are impossible. I tried to prove the others to be impossible as well, but I was unable to do it. I suspect there's no short and simple proof for any of those.

Below are the proofs why the other 11 formations are impossible. All of these boards only have an edge on the left. The edges on the top, right, and bottom are only there to make the images fit on the screen.

  • King 1

The king on a6 already attacks 3 pieces, so the fourth piece it will attack has to be on either a7, or b7. The king on b6 also already attacks 3 pieces. We also know one more piece has to be on either a7 or b7, so c7, c6, and c5 all have to be empty.
The piece that has to go on either a7 or b7 is a knight. It can’t go on a7, because it would then attack the squares b5, c6, c8, and b9. But c6 is empty. Therefore a7 has to be empty, and b7 needs to have the knight.
The knight on b5 now attacks only 4 non-empty squares, so a3, c3, d4, and d6 all need to have some piece.
Let’s look at square c4. If it has a knight, it would attack 2 knights and the unknown pieces on a3 and d6, so those two need to be knights. But if that’s the case the knight on d6 would attack 3 knights: b7, b5, and c3. Therefore c4 isn’t allowed to have a knight.

Then how about a king? That king would then attack 2 knights, and the unknown pieces on c3 and d4. D3 and d5 would then have to be empty. However, the knight on b4 would then only be able to attack 3 non-empty squares. Therefore c4 has to be empty.

If the unknown piece on a3 would be a knight, it would attack 3 non-empty squares, so it has to be a king.

That king on a3 attacks only 4 non-empty squares, so a2, b2, and b3 need to have 2 kings and 1 knight on them. The piece on b3 isn’t allowed to be one of the kings, because it would then attack 5 pieces. Therefore the knight has to go on b3, and a2 and b2 are kings.
We’ve now reached a contradiction. The king on b2 attacks 4 pieces, so a1 and b1 have to be empty. However, the king on a2 is only attacking 3 pieces, so either a1 or b1 needs to have a knight. Therefore the formation king 1 isn’t allowed.

  • King 2

The knight on a3 attacks only 4 squares, so c4, c2, and b1 need to have some piece. The king on b5 now attacks 4 pieces, so a6 and b6 have to be empty. However, the king on a5 needs a knight on either a6 or b6. Therefore formation king 2 isn’t allowed.

  • King 3

The king on a5 attacks 4 non-empty squares, so a6 and b6 have to be knights. The king on b5 now attacks 4 shapes, so c4, c5, and c6 have to be empty. However, the knight on a3 needs to attack some shape on c4. Therefore formation king 3 isn’t allowed.

  • King 4

The king on b3 already attacks 4 shapes, so c4, c3, and c2 have to be empty.
The king on a4 already attacks 2 kings and 1 knight, so the last knight has to go on either a5, or b5. On a5 that knight would only attack 3 non-empty squares, so the knight has to go on b5.
Now look closely at the area a5, b5, a4, b4, a3, b3. It’s the vertical reflection of the formation king 1, and we’ve already proven above that the formation king 1 isn’t allowed, so king 4 also isn’t allowed. (can somebody give me feedback on the rigorousness of this argument? It makes sense in my head, but I’m not sure if it’s rigorous enough)

  • King 5

The king on b3 already attacks 4 shapes, so c4, c3, and c2 have to be empty. However, the knight on a2 has to attack some shape on c3. Therefore the formation king 5 isn’t allowed.

  • King 6

The knight on a2 can only attack 3 non-empty squares. Therefore formation king 6 isn’t allowed.

  • King 7

I haven’t been able to prove this is impossible yet.

  • King 8

I haven’t been able to prove this is impossible yet.

  • King 9

The knight on a2 can only attack 3 non-empty squares. Therefore formation king 9 isn’t allowed.

  • King 10

I haven’t been able to prove this is impossible yet.

  • King 11

I haven’t been able to prove this is impossible yet.

  • King 12

The king on b3 already attacks 4 shapes, so c4, c3, and c2 have to be empty. However, the knight on a2 needs c3 to have some shape. Therefore king 12 is not allowed.

  • King 13

The king on b3 already attacks 4 shapes, so c4, c3, and c2 have to be empty. However, the knight on a4 needs c3 to have some shape. Therefore king 13 is not allowed.

  • King 14

The king on b3 already attacks 4 shapes, so c4, c3, and c2 have to be empty. However, the knight on a2 needs c3 to have some shape. Therefore king 14 is not allowed.

  • King 15

The knight on a2 needs to attack both c3 and c1. However, the king on b2 already attacks 3 shapes, so either c3 or c1 needs to be empty.

  • King 16

I haven’t been able to prove this is impossible yet.

  • Knight 1

I haven’t been able to prove this is impossible yet.

  • Knight 2

I haven’t been able to prove this is impossible yet.

  • Knight 3

I haven’t been able to prove this is impossible yet.

  • Knight 4

I haven’t been able to prove this is impossible yet.

Note by Stefan Van der Waal
4 weeks ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...