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.

UPDATE June 1, 2001: Geoff Cruttwell and friends wrote a computer search for this problem and found a better solution for N=10. Here, X is a red block and - or | is a yellow block. There are 32 Red blocks. 
X|X|X|X--X
||||||--X|
|X|X|X|X||
X|X|X||||X
||||||X|X|
|X|X|X|X||
X|X|X||||X
||||||X|X|
|X|X|X--||
X------X|X
Solutions were received from Rich Polster and Philippe Fondanaiche. Philippe Fondanaiche (Paris, France) sent a very thorough solution:

These solutions were created from his instructions below. For a 4x4, 4 is maximum. For 5x5, 7. And for 6x6, 12. 
R y R y
y y y y
y R y R
y y y y
 
R y R y R
y y y y y
y R y R y
y y R y y
R y y y y
 
R y R y R y
y y y y y y
y R y R y R
R y R y R y
y y y y y y
y R y R y R

TILING A SQUARE
The basic pattern is the following (where R is a red block and Y a yellow one): 

R Y R
Y Y Y
Y R Y

By juxtaposing this pattern k^2 times , we succeed to tile a 3k x 3k square with 3k^2 red blocks and 3k^2 yellow 1x2 rectangles.

A (3k+2) x (3k+2) square can be split into a 3k x 3k square + a L band, 2 in width. This L band can be tiled with 4k tiles such as RYY or YYR or the same vertically. Globally, the square can be covered with 3k^2 + 4k red blocks in maximum.

A (3k+1) x (3k+1) square can be split into a 3k x 3 k square + a L band, 1 in width. If k is even, we can set in the maximum k+1 red blocks; if k odd , k red blocks.

Hence the following formulas encompassing the cases k even = 2p and k odd = 2p+1: 

size of the square                  number of red blocks
6p                                  12p^2
6p+1                                12p^2 + 2p + 1 
6p+2                                12p^2 + 8p 
6p+3                                12p^2 + 12p +3 
6p+4                                12p^2 + 14p +4 
6p+5                                12p^2 + 20p +7
For the first values of p = 0 and p = 1, we obtain: 
size of the square                   number of red blocks
1                                       1 
2                                       0 
3                                       3 
4                                       4 
5                                       7 
6                                      12 
7                                      15 
8                                      20 
9                                      27
10                                     30 
11                                     39
Mail to Ken