MathDB
Knights attacking each other

Source: Argentina Cono Sur TST 2024 P5

August 9, 2024
combinatorics

Problem Statement

In chess, a knight placed on a chess board can move by jumping to an adjacent square in one direction (up, down, left, or right) then jumping to the next two squares in a perpendicular direction. We then say that a square in a chess board can be attacked by a knight if the knight can end up on that square after a move. Thus, depending on where a knight is placed, it can attack as many as eight squares, or maybe even less.
In a 10×1010 \times 10 chess board, what is the maximum number of knights that can be placed such that each square on the board can be attacked by at most one knight?