Ken's POTW

Tiling a Square
In a set of blocks, there are yellow rectangles (1 unit by 2 units), and there are red squares (1 unit on a side). Your goal is to form squares with these blocks, trying to use a maximum number of red blocks, with the one condition that no two red blocks can have an adjacent side.

A single red block is the solution for the 1x1 square. For a 2x2 square, no red blocks can be used. For a 3x3 square, 3 red blocks is the maximum. Find the maximum number of red blocks and provide a sample tiling for:

  1. A 4x4 square.
  2. A 5x5 square.
  3. A 6x6 square.
Feel free to continue this list. Can anything be said of the general NxN square, or the more general MxN rectangle?

Source: Original.

Mail to Ken