What is the least number of rooks that can be placed on a standard $8 \times 8$ chessboard so that all the white squares are attacked? (A rook also attacks the square it is on, in addition to every other square in the same row or column.)
Problem
Source:
Tags: combinatorics
anonymouslonely
05.09.2011 20:37
I think is $ 5 $. is easy to see that each rook can attack $ 8 $ cells. so the number is not smaller than $ 4 $. suppose that the number is $ 4 $. then each intersection of one line and one column on which are the rooks have to be black and each row and each column must have at most one rook. from these ones we get a contradiction. it's easy to find an example for $ 5 $.
wcao9311
14.03.2016 06:06
there are a total of 32 white spaces. We prove the min number is 4. Each space can attack 7 cells of its color, and 8 cells of the other color. So we want all the cells to be black to attack the most white cells. We have 8*n<32 for n<4. For N=4 we can illustrate an example. Assuming wlog that the top left square is white and dubbed H1, The rest an be shown as g1,e3,c5,a7.