Puzzling Asked on March 16, 2021
What is the minimum number of knights you need to place on a 10×10 chess board, such that every empty cell is attacked by at least one knight?
Good luck!
A possible way to cover the board with indicating the positions of the knights with "X" is:
Next I will prove that with 15 knights it is not possible.
This is a 3x3 area/board inside of a 7x7 board. If a knight is placed on any of the squares of the middle part, the number how many squares are covered by it inside the middle part is written on its square. Any single knight can cover up to 3 squares in this 3x3 area. However, 3 knights cannot cover all 9 of the central squares because a knight in any of the 8 positions that cover 3 squares cannot cover the center square. The conclusion is that at least 4 knights are needed to cover any 3x3 area/board.
Lastly, consider this arrangement.
This is already a 10x10 board. A minimum of 4 knights are needed to cover each of the four 3x3 lettered areas. Since a knight cannot cover squares in two different lettered areas a total of at least 16 knights are required. In case of a 9x9 board there would be at least one knight that could cover one or more squares in two different lettered areas.
The conclusion:
Correct answer by balazs.com on March 16, 2021
Here is a solution using
knights.
I believe this is minimal, but I do not yet have a proof.
The obvious lower bound is 12, as 11 knights can cover at most 88 squares, so there is at least $100-88-11=1$ square uncovered and empty.
This lower bound can be improved slightly if you take into account that a knight covering a corner can cover at most 6 squares. Suppose you use 12 knights. Four of the knights cover 6 squares (including one corner each), and the other 8 knights cover at most 8 squares, and that gives a total of at most $4*6+8*8+12=100$ squares that are covered or non-empty. However, there is no slack at all. For a solution with 12 knights to be possible, every square must be covered exactly once, no knight attacks another, and every knight covers 6 or 8 squares. When you try to place the knights to cover the squares near a corner of the board, it is soon obvious that you will have squares that are covered multiple times.
So at least 13 knights are necessary. There is unfortunately still a gap between this lower bound and what I believe to be the actual minimum.
I also tried to prove it by looking at this pattern:
x x . . . . . . . x . x . . . . . . x x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x x . . . . . . x . x . . . . . . . x x
Each of the twelve marked squares must be covered or contain a knight. However, no two of them can be covered/filled by a single knight (i.e. no two marked squares are one or two knight moves apart), so at least 12 knights are necessary. I have not yet been able to find a similar pattern with more marked squares.
Answered by Jaap Scherphuis on March 16, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP