How Many Ways Can You Tile the Tilted Square?

Consider the following array of $25$ squares, set out as a square standing on one corner, with rows of $1$, $3$, $5$, $7$, $5$, $3$ and $1$ squares.

You fill the array with rectangles by repeating two steps. First, select one of the $12$ squares along the outer perimeter that is not yet part of a rectangle. Second, form the largest rectangle you can that includes the square you just selected and other squares not yet part of any rectangle. You repeat these steps until every square along the perimeter has been selected. How many distinct final states are possible? (States that are rotations or reflections of each other count as distinct.)

The Fiddler, Zach Wissner-Gross, June 21, 2024(original post)

The official solution appeared in the post of June 28, 2024 and gives $106$, agreeing with the answer below. The Extra Credit half of that post is paywalled, so the count of $3002$ and the general formula are my own.

Solution

Give each square the coordinates of its centre, with the middle square at $(0,0)$. The array is then the set of squares $(x,y)$ with $|x| + |y| \le 3$, and the perimeter squares are the twelve with $|x| + |y| = 3$. They are exactly the two end squares of each row.

The process looks as though it could branch wildly, since every step offers a choice. The idea that tames it is this: every rectangle the process forms cuts what is left into pieces of just two shapes, which the figure below calls pyramids and staircases, and from then on each piece fills itself in without any influence from the others. So the count can be built up from small pieces.

The first rectangle. Suppose the first square chosen is $(-a,-b)$, in the lower left, where $a$ and $b$ are whole numbers with $a + b = 3$ (the other three quarters are the same by symmetry). A rectangle containing this square has its lower left corner at some square $(x_1, y_1)$ with $x_1 \le -a$ and $y_1 \le -b$. That corner square must lie in the array, so $|x_1| + |y_1| \le 3 = a + b$, which forces $x_1 = -a$ and $y_1 = -b$. In the same way, the lower right corner $(x_2, -b)$ must satisfy $|x_2| \le a$, and the upper left corner $(-a, y_2)$ must satisfy $|y_2| \le b$. So every rectangle through $(-a,-b)$ fits inside the box of squares with $|x| \le a$ and $|y| \le b$. That box lies inside the array, since its corners satisfy $|x| + |y| = a + b = 3$. It is therefore the largest rectangle, and the only one of its size. The first rectangle is always this centred box, $2a+1$ squares wide and $2b+1$ tall. There are four of them: $1 \times 7$, $3 \times 5$, $5 \times 3$ and $7 \times 1$.

What the first rectangle leaves. Above the box sit the squares with $y > b$. Their rows have $2a - 1$, $2a - 3$, …, $3$, $1$ squares, a pyramid of height $a$ resting on the box. Below the box is another pyramid of height $a$, and to the left and right are pyramids of height $b$. No two of these four pieces touch, even at a corner: the nearest squares of the top and left pieces are $(-(a-1), b+1)$ and $(-(a+1), b-1)$, two apart in each direction. A rectangle is a solid block of free squares, so it can never reach from one piece into another. Each piece therefore runs its own course, and any final state of the top pyramid can be combined with any final state of each of the other three. If $P(h)$ is the number of final states of a pyramid of height $h$, the first rectangle $(2a+1) \times (2b+1)$ leads to $P(a)^2 P(b)^2$ final states.

Pyramids. Number the rows of a pyramid of height $h$ from the top, so that row $r$ has $2r - 1$ squares and row $h$ rests on the rectangle below. The ends of every row are perimeter squares of the original array, and no other squares of the pyramid are. Suppose the end square of row $r$ is chosen. The rows above row $r$ are narrower and do not reach that end’s column, so the rectangle starts at row $r$. It can be no wider than row $r$. The rows below are all wider, so the full width of row $r$, carried all the way down to the bottom row, is free. That block, $2r - 1$ wide and $h - r + 1$ tall, is the largest rectangle, and the only one of its size.

The block leaves a pyramid of height $r - 1$ on top. On each side it leaves the parts of rows $r+1, \dots, h$ that stick out beyond it, with $1, 2, \dots, h - r$ squares: a staircase of size $h - r$, flat against the block and stepped on the outside. Writing $S(m)$ for the number of final states of a staircase of size $m$, and using the same independence as before, $$P(h) \;=\; \sum_{r=1}^{h} P(r-1)\, S(h-r)^2, \qquad P(0) = 1 .$$

Staircases. In a staircase of size $m$, row $i$ (from the top) has $i$ squares, and only its outer end is a perimeter square. Choosing the outer end of row $i$ forms, by the same reasoning, the block of rows $i$ to $m$ that is $i$ squares wide. It leaves a staircase of size $i - 1$ above it and a staircase of size $m - i$ beside it, made of the overhanging parts of the rows below. Hence $$S(m) \;=\; \sum_{i=1}^{m} S(i-1)\, S(m-i), \qquad S(0) = 1 ,$$ which is the recurrence of the Catalan numbers: $S = 1, 1, 2, 5, 14, \dots$ for $m = 0, 1, 2, 3, 4, \dots$.

Why nothing is counted twice or stranded. In every piece, different first choices give different final states, because they put a particular square (the middle of the bottom row of a pyramid, or the bottom inner square of a staircase) into different rectangles. The same holds for the whole array, where the middle square’s rectangle tells the four first rectangles apart. So the sums above add up disjoint sets of final states. And every piece that still has squares still has a perimeter square (the end of its top row), so the process never stops with a square left over.

The count. The pyramid numbers are $$\begin{align*} P(1) &= P(0)S(0)^2 = 1, \\ P(2) &= P(0)S(1)^2 + P(1)S(0)^2 = 1 + 1 = 2, \\ P(3) &= P(0)S(2)^2 + P(1)S(1)^2 + P(2)S(0)^2 = 4 + 1 + 2 = 7 . \end{align*}$$ Summing over the four first rectangles, $(a,b) = (0,3), (1,2), (2,1), (3,0)$, $$1^2 \cdot 7^2 + 1^2 \cdot 2^2 + 2^2 \cdot 1^2 + 7^2 \cdot 1^2 = 49 + 4 + 4 + 49 .$$ $$\boxed{\ 106 \text{ distinct final states.} \ }$$ The two $49$s are the official solution’s “seven ways on each half” when the first rectangle runs right down the middle.

The computation

The program plays the process exactly as stated, with no use of pyramids or staircases.

1. List every rectangle that fits inside the array, largest first, each as a bit mask of its squares.

2. From a set of free squares, try every free perimeter square in turn. For that square, take the largest listed rectangle that contains it and is wholly free, and check that no other rectangle of the same size would also do (the rule would be ambiguous otherwise).

3. Recurse on the squares that remain, remembering results for sets already seen, and collect the final states as sets of rectangles. When no perimeter square is free, check that no square at all is left over.

It finds $106$ final states.

from functools import lru_cache

def count_final_states(n):
    span = range(-n + 1, n)
    cells = [(x, y) for x in span for y in span if abs(x) + abs(y) <= n - 1]
    bit = {c: 1 << i for i, c in enumerate(cells)}
    rim = [bit[c] for c in cells if abs(c[0]) + abs(c[1]) == n - 1]
    rects = []                                   # every rectangle inside the array
    for a in span:
        for b in span[a + n - 1:]:
            for c in span:
                for d in span[c + n - 1:]:
                    box = [(x, y) for x in range(a, b + 1) for y in range(c, d + 1)]
                    if all(p in bit for p in box):
                        rects.append((len(box), sum(bit[p] for p in box)))
    rects.sort(reverse=True)                     # largest first
    through = {r: [(s, m) for s, m in rects if m & r] for r in rim}

    def biggest(free, r):
        fits = [(s, m) for s, m in through[r] if m & free == m]
        assert len(fits) == 1 or fits[0][0] > fits[1][0]   # never a tie
        return fits[0][1]

    @lru_cache(maxsize=None)
    def finish(free):
        todo = [r for r in rim if r & free]
        if not todo:
            assert free == 0                     # no square is left over
            return {frozenset()}
        out = set()
        for r in todo:
            box = biggest(free, r)
            out |= {rest | {box} for rest in finish(free & ~box)}
        return out

    return len(finish(sum(bit.values())))

print(count_final_states(4))

It prints

106

Extra Credit

Now the array has five squares along each outer edge (rows of $1, 3, 5, 7, 9, 7, 5, 3, 1$, so $41$ squares), and the same process is followed. How many distinct final states are possible? Can you find a general formula for an array with $N$ squares along each outer edge?

Solution

Nothing in the argument above used the size of the array. With $N$ squares along each edge, the array is the set of squares with $|x| + |y| \le N - 1$. The first rectangle is again a centred box $(2a+1) \times (2b+1)$, now with $a + b = N - 1$, and it again leaves two pyramids of height $a$ and two of height $b$. So $$\boxed{\ T(N) \;=\; \sum_{a+b=N-1} P(a)^2\, P(b)^2 , \ }$$ with the pyramid numbers given by $$P(0) = 1, \qquad P(h) = \sum_{r=1}^{h} P(r-1)\, C_{h-r}^{\,2} ,$$ where $C_m = \frac{1}{m+1}\binom{2m}{m}$ is the $m$th Catalan number. The pyramid numbers run $1, 1, 2, 7, 38, 274, 2350, \dots$, and the next one is $$P(4) = P(0)C_3^2 + P(1)C_2^2 + P(2)C_1^2 + P(3)C_0^2 = 25 + 4 + 2 + 7 = 38 .$$ For $N = 5$ the first rectangle has $(a,b) = (0,4), (1,3), (2,2), (3,1)$ or $(4,0)$, giving $$T(5) = 38^2 + 7^2 + 2^2 \cdot 2^2 + 7^2 + 38^2 = 1444 + 49 + 16 + 49 + 1444 .$$ $$\boxed{\ 3002 \text{ distinct final states.} \ }$$ The sequence $T(N)$ for $N = 1, 2, 3, \dots$ begins $1, 2, 9, 106, 3002, 153432$. Almost all of it comes from the long, thin first rectangles (with $a$ or $b$ equal to $0$), which leave two big pyramids: for $N = 5$ they account for $2888$ of the $3002$ states.

The computation

The program from the main problem plays the process for $N = 1$ to $5$, and the formula is evaluated alongside it. The two agree at every size, including $3002$ for $N = 5$. (The same simulation also gives $153432$ for $N = 6$, matching the formula, but it takes about twenty seconds, so it is left out here.)

from math import comb

def formula(n):
    catalan = [comb(2 * m, m) // (m + 1) for m in range(n)]
    P = [1]
    for h in range(1, n):
        P.append(sum(P[r - 1] * catalan[h - r] ** 2 for r in range(1, h + 1)))
    return sum(P[a] ** 2 * P[n - 1 - a] ** 2 for a in range(n))

for n in range(1, 6):
    print(n, count_final_states(n), formula(n))

It prints

1 1 1
2 2 2
3 9 9
4 106 106
5 3002 3002