Each of the spots in a $8\times 8$ chessboard is occupied by either a black or white “horse”. At most how many black horses can be on the chessboard so that none of the horses attack more than one black horse? Remark: A black horse could attack another black horse.
Problem
Source:
Tags: combinatorics
Steve12345
01.03.2021 01:22
Probably 16.
If I understood the problem correctly, it is equivalent to having a chessboard filled with horses and we are asked to mark as many horses as we can such that no horse attacks more than 1 marked horse.
Mark the 4 2x2 in the corners. They work.
To prove that >16 won't work, there must exist a 4x4 square and 5 marked horses. Do some casework and get a contradiction.
bsf714
01.03.2021 13:56
Steve12345 wrote:
Probably 16.
If I understood the problem correctly, it is equivalent to having a chessboard filled with horses and we are asked to mark as many horses as we can such that no horse attacks more than 1 marked horse.
Mark the 4 2x2 in the corners. They work.
To prove that >16 won't work, there must exist a 4x4 square and 5 marked horses. Do some casework and get a contradiction.
Marking the four $2\times 2$ in the corners doesn’t work. If we view the chessboard as an $8\times 8$ matrix, the unmarked horse at position, say, $(6, 3)$ would be able to attack both $(8, 2)$ and $(7, 1)$ (which you have marked).