14
$\begingroup$

There are N White Kings on the Chess Board.
There are M Black Knights.
There is no Black King and no other Piece. Only M+N Squares are occupied.

Each White King is attacked by atleast 1 Black Knight, but it can not move itself out of attack.

Maximize N. In the Possible Solutions, Minimize M.

Here are 2 invalid cases:

All Kings are in attack, but c8 can escape to c7 & a7 can escape to b6.

Not all Kings are in attack. King on e4 is not in attack. Also e5 can escape to e6.

Here are 2 valid cases:

N=3 & M=5

N=9 & M=17

[[ This is inspired by this Puzzle ! ]]

Improve this question
$\endgroup$
2
  • $\begingroup$ Minor point, but in your second example, there's a few more escapes you didn't mention. d5 and f5 can also escape to e6, and d3, e3, and f3 can all escape to e2. $\endgroup$
    – Darrel Hoffman
    Commented Jun 28, 2022 at 15:56
  • $\begingroup$ In Example 1 : b8 to c7 & c8 to d7 ; In Example 2 : Yes, e6 & e2 are unprotected & the 3 nearby kings can move there. @DarrelHoffman $\endgroup$
    – Prem
    Commented Jun 29, 2022 at 6:10

3 Answers 3

Reset to default
20
$\begingroup$

50 Kings,14 Knights:

enter image description here

This is optimal but not unique, see bottom of this answer.

Reasoning:

I think the problem is equivalent to covering every square on the board with as few knights as possible and this can be split up into black and white squares. So proving that we need at least seven knights to cover all black squares would suffice.

The above was constructed from this solution to the equivalent problem:

enter image description here

Proof of optimality of this:

To cover the 4 black squares of any file at least two N's are required. For the first and last files these two have to be on the same file themselves and once the file is chosen there is only one way of placing the two N's. (If 3 or 4 N's are used we will still have at least two in one of the files in reach by pigeon hole principle.) Therefore we have 4 N's in two files (b or c and f or g). In particular, they cannot contribute to covering these two files. If fewer than 7 were possible, then we would have to cover both files with the last two N's. These two would then have to sit in the file in middle between the others, leaving only the two symmetric scenarios of two N's in each of either b,d,f or c,e,g. And we can check that this is not a solution:

enter image description here

Note that rotating the board 90° and reapplying this argument almost necessarily leads to our 7 N solution. But there is one alternative solution. (Thanks to @Daniel Mathias for pointing that out and also that there are no other solutions):

enter image description here

Using this we can construct two more solutions to the original problem:

enter image description here enter image description here

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ That's amazing! $\endgroup$
    – Jaap Scherphuis
    Commented Jun 27, 2022 at 11:07
  • 3
    $\begingroup$ I agree it must be optimal. If solving one colour could be done in 6, then that would lead to a 12-knight solution, but the dominating knights problem (where the knights need to cover only the empty squares) has a unique 12-knight solution that does not work for this problem. So solving one colour requires 7, meaning 14 is minimal. $\endgroup$
    – Jaap Scherphuis
    Commented Jun 27, 2022 at 11:53
  • 1
    $\begingroup$ There is another arrangement of 6x2 shown in my deleted answer. All the Kings are covered as agreed by http://oeis.org/A006075, but the Knights do not all mutually protect. $\endgroup$
    – Weather Vane
    Commented Jun 27, 2022 at 12:13
  • 2
    $\begingroup$ There are $\binom{32}{6}=906192$ ways to place six knights on light squares, and checking all of these positions confirms the optimality of this solution. (There was never any doubt.) Also, checking positions with seven knights reveals two distinct solutions. $\endgroup$
    – Daniel Mathias
    Commented Jun 27, 2022 at 20:30
  • 1
    $\begingroup$ @DanielMathias Nice! Now that you tipped me off I had to find the other solution! Will update the post in a minute. $\endgroup$
    – loopy walt
    Commented Jun 27, 2022 at 21:39
10
$\begingroup$

This seems like it could be optimal [Edit: it is not - see loopy walt's answer]:

16 knights, and 48 kings.

enter image description here
This position in the lichess board editor

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ +1 , It was "OPTIMAL" or "BEST" at the moment it was answered, until it was exceeded by the other answer ! $\endgroup$
    – Prem
    Commented Jun 27, 2022 at 11:49
1
$\begingroup$

The answer I found is:

1 (If you cant see the image click on the unloaded image because there is a link to a lichess website to see it better)

Explanation:

The knights are all inter linked (As you can see from the arrows)

The outer knights attack all of the external kings. enter image description here

The internal kings are attacked by these knights. enter image description here

The middle kings are attacked by the knights as well as we can see below. enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ +1 , Nice Work !! The "OPTIMAL Solution" has 50+14 & the Other Solution has 48+16 while your Solution has 40+24 ; All Solutions are covering up the Board !! $\endgroup$
    – Prem
    Commented Jul 5, 2022 at 4:07
  • $\begingroup$ @Prem Yeah but this is what I found so I tought I would share it $\endgroup$
    – Varun W.
    Commented Jul 5, 2022 at 14:15

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