OFFSET
1,2
COMMENTS
Consider n unit squares contained within an n X n square. The n unit squares are an n-cell pattern of the n X n square if, when copied n-1 times, they can, with various rigid transformations, be combined to tessellate the n X n square.
Put another way:
Consider, for example, for n = 4, a transparency with an outline of a 4 X 4 square filled by 16 unit squares. Any 4 unit squares are painted the same color. Those four squares are a potential n-cell pattern of the 4 X 4 square. Three copies of the transparency are made with only the color of the 4 squares being different. If a person can stack the transparencies in such a way that they fill the 4 X 4 square, then the n-cell pattern is acceptable.
Put another way:
n unit squares from an n X n square are painted a color. Those n unit squares are an n-cell pattern. If n-1 copies of the pattern can be painted (each a different color) and together they fill the n X n square, then the n unit squares form an acceptable n-cell pattern.
Conjecture by Andrew Young: For an n X n square, where n is an odd prime, there is only one n-cell pattern.
Conjecture by Andrew Young and Thomas Young: An odd integer n>=3 is prime iff there exists only one n-cell pattern for an n X n square.
For composite numbers n, an n X n square will always have at least two n-cell patterns: a 1 X n pattern and an f1 X f2 pattern, where 1 < f1 <= f2 < n and f1*f2 = n. For example, a 14 X 14 square can be tiled using fourteen 1 X 14 rectangles or fourteen 2 X 7 rectangles; a 15 X 15 square can be tiled using fifteen 1 X 15 rectangles or fifteen 3 X 5 rectangles; a 9 X 9 square can be tiled using nine 1 X 9 rectangles or nine 3 X 3 squares (as in Sudoku!).
For prime numbers p, a p X p square can always be tessellated with p rectangles that are 1 X p.
LINKS
Thomas Young, The 60 4-cell patterns for a 4 X 4 square.
Thomas Young, The 102 6-cell patterns for a 6 X 6 square.
EXAMPLE
For n = 1, there is one 1-cell pattern because there is only one unit square to paint.
For n = 2, there are two 2-cell patterns:
+---+---+ +---+---+ +---+
| 1 | 2 | | 1 | 2 | | 1 |
+---+---+ +---+---+ and +---+---+
| 3 | 4 | | 4 |
+---+---+ +---+
For n = 3, there is one 3-cell pattern:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 | it is +---+---+---+
+---+---+---+ | 1 | 2 | 3 |
| 7 | 8 | 9 | +---+---+---+
+---+---+---+
For n = 4, there are sixty 4-cell patterns:
+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+
| 5 | 6 | 7 | 8 | one is +---+---+---+---+
+---+---+---+---+ | 1 | 2 | 3 | 4 |
| 9 |10 |11 |12 | +---+---+---+---+
+---+---+---+---+
|13 |14 |15 |16 |
+---+---+---+---+
+---+---+---+---+ +---+
| 1 | 2 | 3 | 4 | is equivalent to | 1 |
+---+---+---+---+ +---+
| 5 |
+---+
| 9 |
+---+
|13 |
+---+
and therefore is counted as one pattern.
Another 4-cell pattern for a 4 X 4
+---+---+---+---+
| x | x | y | y |
+---+---+---+---+
| z | y | x | a | is +---+---+
+---+---+---+---+ | x | x |
| y | z | a | x | +---+---+---+
+---+---+---+---+ | x |
| a | a | z | z | +---+---+
+---+---+---+---+ | x |
+---+
+---+---+
| x | x |
+---+---+---+ is equivalent to
| x |
+---+---+
| x |
+---+
+---+---+ +---+ +---+
| y | y | | z | | a |
+---+---+---+ +---+---+ +---+---+
| y | | z | | a |
+---+---+ +---+---+---+ +---+---+---+
| y | | z | z | | a | a |
+---+ +---+---+ +---+---+
because the shapes can be created through reflection, rotation, or translation.
Therefore, they are counted as one pattern.
For n = 5, there is one 5-cell pattern.
CROSSREFS
KEYWORD
nonn,more,hard
AUTHOR
Thomas Young, May 30 2023
EXTENSIONS
a(7)-a(8) from Andrew Howroyd, Jun 04 2023
STATUS
approved