# Color an N×N Board: No Colored Cell Touch

What is the largest number of cells of a 6×6 board that could be colored such that no two colored cells touch (not even at a corner)?

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander BogomolnyWhat is the largest number of cells of a 6×6 board that could be colored such that no two colored cells touch (not even at a corner)?

An answer to the problem is 9 cells as shown in the left diagram below.

Why there could not be more colored cells? Because, as shown in the right diagram above, the board could be cut into 2×2 squares, and 9 is the number of such squares. It needs to be observed that no 2×2 square may contain more than 1 colored cell.

To generalize: in a (2N)×:(2N) one can color at most N² cells so that no two colored cells touch. For a

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny