Painting a Board

Question

We have a board like this: (16 column, 10 row)

We are gonna paint n number of box for each column.

And there is one rule:

• There shouldn't be a 2x2 white square.

What is the maximum value of n for this?

---

I painted like this:

I thought it's not 10 obviously, and it is not 9 or 8 either, because I couldn't place like that. So it's 7. But I want to know a proper way to solve this (if there is a way), other than just trying numbers until I found the right one. (Considering, this is the right answer of course...)

Answer 1

There must be a black box in each $2\times 2$ square. As we can tile the $16\times 10$ rectangle with $8\cdot 5=40$ such $2\times 2$ squares, at least $40$ boxes must be black. As $2\cdot 16<40$, at least one of the columns must have at least $3$ black boxes. As all columns shall have the same number of black boxes, all columns must have at least $3$ black boxes. Your drawing shows that this bound is achievable.