9
$\begingroup$

Given an $n\times n$ grid, and $2\times 2$ checkered tiles (white in the upper left and bottom right corners, and black in the upper right and bottom left corners), what is the smallest number of black squares that can be showing for a tiling that covers the grid (overlaps allowed)?

Tiles can be rotated in their placement, are assumed to be infinitely thin, and are placed one at a time on top of the grid/tile configuration, that is, the most recent tile that has been placed must have all four squares uncovered. Tiles cannot hang off of the edges of the grid but must be placed entirely within the grid.

I've been able to achieve tilings such that only $n$ black squares are showing, but I can't seem to prove that this is the minimum (if it is).

$\endgroup$
12
$\begingroup$

Yes, $n$ black squares is minimal.

No matter how you tile your grid, there will always be at least one black square in each row and in each column because adding a new tile always places a black square in both of the rows and columns in which the tile was added. The The best you can do is have one black line along the diagonal.

Here's one way to achieve it:

tiling method

$\endgroup$
  • $\begingroup$ Good addition to a good answer. I wish I could +1 again. $\endgroup$ – Ross Millikan May 3 '13 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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