0
$\begingroup$

How many rooks are required such that all dark squares on the chessboard are covered by at least one rook.

$\endgroup$
4
  • $\begingroup$ If I now have the answer, should I post it? $\endgroup$
    – Sunny Lu
    Jan 31 at 7:37
  • $\begingroup$ I suppose you want the minimal number of rooks? $\endgroup$ Jan 31 at 14:11
  • $\begingroup$ How many rooks are required, so yes. $\endgroup$
    – Sunny Lu
    Jan 31 at 15:18
  • $\begingroup$ @SnySmartie I laughed so hard at the edit history. Keep it up! $\endgroup$
    – enzo
    Feb 1 at 0:15

1 Answer 1

4
$\begingroup$

Here is a configuration with 4 rooks. enter image description here

As justhalf and JaapScherphuis have pointed out, this can easily proven to be optimal: each rook can only cover two of the squares of the black diagonal. So 4 rooks are necessary to cover all the black squares.

$\endgroup$
4
  • 13
    $\begingroup$ The proof is easy. Each rook can cover at most 8 black squares, and 32 need to be covered. $\endgroup$ Jan 31 at 9:17
  • 9
    $\begingroup$ Or, look at the 8 diagonal black squares. One rook can only cover 2. $\endgroup$
    – justhalf
    Jan 31 at 9:39
  • 1
    $\begingroup$ The proof of @JaapScherphuis also implies that none of the rooks can be placed on a black square. $\endgroup$
    – WhatsUp
    Jan 31 at 19:19
  • $\begingroup$ thanks again for you comments, included the proof of optimality in the post. $\endgroup$
    – daw
    Feb 1 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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