A355477 Maximum number of skew-tetrominoes that can be packed into an n X n square.

0, 0, 1, 3, 4, 8, 9, 14, 16, 23, 25, 33, 36, 46, 49, 60, 64, 77, 81, 96, 100

Offset: 1

Author

Alexander D. Healy, Jul 03 2022

Keywords

• nonn
• more

Comments

Skew-tetrominoes are tiles of the form:

_

| |

|_|

together with all rotations/reflections of this shape.

It is not hard to see that skew-tetrominoes cannot completely tile an n X n square, so a(n) < n^2/4.

The odd terms are easily understood: a(2m+1) = m^2.

A straightforward (greedy) construction shows that m^2 skew-tetrominoes (all with the same orientation) can be packed into a (2m+1) X (2m) rectangle. Therefore a(2m+1) >= m^2.

On the other hand, we also have a(2m+1) <= m^2: Consider all cells with indices of the form (2i, 2j); there are m^2 such cells in a (2m+1) X (2m+1) square. Moreover, any valid placement of a skew-tetromino must cover one of these cells, so a(2m+1) <= m^2.

The behavior of a(2m) appears more subtle; the initial terms satisfy a(2m) = m^2 - floor(m/2), but this formula breaks down at a(20) = 96 (not 95).

Additional terms:

(Lower bounds are from explicit constructions; upper bounds are from mixed-integer-programming search.)

a(22) in {116, 117}.

a(23) = 121.

a(24) = 139.

a(25) = 144.

a(26) in {163, 164}.

a(27) = 169.

a(28) in {190, 191}.

a(29) = 196.

a(30) in {218, 219, 220}.

a(31) = 225.

a(32) in {248, 249, 250, 251}.

a(33) = 256.

a(34) in {280, 281, 282, 283}.

a(35) = 289.

a(36) in {316, 317, 318}.

a(37) = 324.

a(38) in {352, 353, 354, 355}.

a(39) = 361.

a(40) in {388, 389, 390, 391, 392, 393, 394}.

a(41) = 400.

a(42) in {432, 433, 434}.

Examples

			a(8) = 14 by the following packing of 14 skew-tetrominoes into an 8 X 8 square:
   _______________
  |_|1 _| |___| |_|
  |___| 2_|3 _|_4 |
  |_ 5|_|___| | |_|
  | |___| | 6_|_7 |
  |_8 | 9_|_|_10|_|
  | |_|_|11_| |___|
  |_12|___|13_|14_|
  |_|_|___|_|___|_|
		

Links

• Alexander D. Healy, Examples of (near-)optimal packings for n <= 42
• Wikipedia, Tetromino

Crossrefs

Cf. A256535.

Formula

a(n) < n^2/4.

a(2m+1) = m^2.