Tiling

Let $f(n)$ be the number of ways to tile a $2\times n$ grid and let $g(n)$ be the number of ways to tile a $2\times (n+1)$ grid without one of its corners.

It is then not hard to come up with the recursions

$f(n)=2f(n-2)+2g(n-2)+2g(n-3)$ and $g(n)=f(n-1)+2f(n-2)+2g(n-2)$ .

It is easy to calculate that $f(0)=1, f(1)=1, f(2)=4$ and $g(0)=1, g(1)=1, g(2)=5$ , and from there it is easy to compute that $f(8)=\boxed{556}$ .

We can solve this problem using recursion. Let $a_n$ be the number of tilings of a $2\times n$ grid such that neither of the rightmost two squares is occupied by a piece of shape B. Let $b_n$ be the number of tilings of a $2\times n$ grid such that one of the rightmost two squares is occupied by a piece of shape B. Let $c_n$ be the number of tilings of a $2\times n$ grid such that both of the rightmost two squares are occupied by a piece of shape B.

There are 7 ways to add at least one column to a $2\times n$ grid. First of all, we can add a $2\times 1$ rectangle made of two pieces of shape B. This rectangle can only be added to a configuration if neither of the rightmost two squares is occupied by a piece of shape B.

Secondly, we can add a $2\times 2$ square made of one piece of shape A and one piece of shape B. There are four ways to orient this square. If the piece of shape B is on the left, the square can only be added if a configuration does not have both rightmost two squares pieces of shape B. If the piece of shape B is on the right, the square can always be added.

Thirdly, we can add a $2\times 3$ rectangle made of two pieces of shape A. There are two ways to orient this rectangle, and it can be added to any configuration.

From this, we determine a recurrence: $\begin{aligned} a_n&=2(a_{n-3}+b_{n-3}+c_{n-3}+a_{n-2}+b_{n-2}) \\ b_n&=2(a_{n-2}+b_{n-2}+c_{n-2}) \\ c_n&=a_{n-1} \end{aligned}$

Finally, we can form a table, where $s_n=a_n+b_n+c_n$ : $\begin{array}{| l | l | l | l | l | l | l | l | l |} \hline & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline a_n & 0 & 2 & 2 & 10 & 16 & 48 & 96 & 252 \\ \hline b_n & 0 & 2 & 2 & 8 & 12 & 40 & 76 & 208 \\ \hline c_n & 1 & 0 & 2 & 2 & 10 & 16 & 48 & 96 \\ \hline s_n & 1 & 4 & 6 & 20 & 38 & 104 & 220 & 556 \\ \hline \end{array}$

The answer is $s_8=\boxed{556}$ .

Consider three different forms of tiling -

One, $P$ , in which the leftmost edge of the grid is made up of two $B$ pieces next to each other.

Another, $Q$ , where the leftmost edge is made up of an $A$ and a $B$ piece (either way round).

A final, $R$ , with the leftmost edge made up of a single $A$ piece (in either possible orientation).

Any tiling of the $2\times8$ grid must be exactly one of these forms, so the total number of tilings is equal to the sum of these three types.

$P - \begin{matrix} B \cdots \\ B \cdots \end{matrix} \qquad Q - \begin{matrix} A & A \cdots \\ B & A \cdots \end{matrix} \qquad R - \begin{matrix} A & A \cdots \\ A & .\cdots \end{matrix}$

Now we set up recurrences for each of these three tilings.

For $P$ , it is relatively simple. Starting from the left, we have two $B$ pieces, but the restriction in the question prevents us from putting any $P$ or $Q$ tilings on the right of them; otherwise, there would be an $A$ -shaped block of $B$ s. Any $R$ tiling is possible though, because the $A$ and 2 $B$ pieces can coexist happily. Therefore, $P_n = R_{n-1}$ .

For $Q$ , there are two possible starting positions, in which the $A$ and $B$ pieces make a square and the $B$ piece is against the left side. To then extend either of these two positions, any of the other sorts of tilings could be appended to the right, because a flat end of an $A$ piece is the connection. Therefore, noting that the starting position consumes two units of length, $Q_n = 2(P_{n-2} + Q_{n-2} + R_{n-2})$ .

For $R$ , there are now $4$ possible starting positions. In two of them, the $A$ and $B$ pieces again make a square though with the $B$ piece on the right, and in the others there are two $A$ pieces making a $2\times 3$ rectangle. In the former case, any adjacent tiling except a $P$ one is acceptable, and in the latter any tiling at all is allowed. This means that $R_n = 2(Q_{n-2}+R_{n-2}) + 2(P_{n-3} + Q_{n-3} + R_{n-3})$ .

Starting from $n=1$ (we cannot start from $n=0$ because $P_0,Q_0,R_0$ refer to the same empty arrangement and are no longer unique), we see by inspection that

$\qquad \qquad P_1 = 1, Q_1 = 0, R_1 = 0 \\\qquad \qquad P_2 = 0, Q_2 = 2, R_2 = 2 \\ \qquad \qquad P_3 = 2, Q_3 = 2, R_3 = 2$

Then we apply the recurrence, obtaining

$\qquad \qquad P_4 = 2, \;\: Q_4 = 8, \:\;\:\: R_4 = 10 \\ \qquad \qquad P_5 = 10, Q_5 = 12, \:\; R_5 = 16 \\ \qquad \qquad P_6 = 16, Q_6 = 40, \:\; R_6 = 48 \\ \qquad \qquad P_7 = 48, Q_7 = 76, \:\; R_7 = 96 \\ \qquad \qquad P_8 = 96, Q_8 = 208, R_8 = 252$

Finally, the total number of ways to tile a $2\times 8$ grid is equal to $P_8 + Q_8 + R_8 = 556$ .

We can solve it by obtaining a set of recurrence equations:

Let $a_n$ denote the number of ways of tiling for $2\times n$ grid.

Let $b_n$ indicate the number of sets ending with $B$ on top and bottom squares (takes 2x1 space)

Let $c_n$ indicate the number of sets ending with $A^B$ and $A_B$ (takes 2x2 space)

Let $d_n$ indicate the number of sets ending with $^BA$ and $_BA$ (takes 2x2 space)

And let $e_n$ indicate the number of sets ending with $AA$ (takes 2x3 space)

The required answer the sum: $a_n=b_n+c_n+d_n+e_n$

The recurrences are:

$b_n = d_{n-1}+e_{n-1}$ ,

since ending with BB requires that previous tiles are from 'd' or 'e'

$c_n = 2\cdot (b_{n-2}+c_{n-2}+d_{n-2}+e_{n-2})$ ,

since there are two ways of ending 'c' and the previous tiles can be from any of 'b', 'c', 'd' or 'e'.

With similar reasoning,

$d_n=2\cdot (c_{n-2}+d_{n-2}+e_{n-2})$

$e_n = 2\cdot (b_{n-3}+c_{n-3}+d_{n-3}+e_{n-3})$

Initial 3 values for n = 1,2,3 are: $b_1=1, b_2=0, b_3=2$

$c_1=0,c_2=2,c_3=2$

$d_1=0,d_2=2,d_3=0$

$e_1=0,e_2=0,e_3=2$

On calculating the recurrence, we find the first 8 values of $a_n$ to be

$\{1, 4, 6, 20, 38, 104, 220, 556\}$

$\therefore a_8 = \fbox{556}$

As an aside, we can also obtain from the sequence:

$f_n = 4\, f_{n-2} + 2\, f_{n-3} + 2\, f_{n-4} + 4\, f_{n-5}$ with

$f_{0}=1,\; f_{1}=1,\; f_{2}=4,\; f_{3}=6,\; f_{4}=20$

and the generating function:

$G(z) = \dfrac{1+z}{1- 4\, z^2 - 2\, z^3 - 2\, z^4 -4\, z^5}$

We will call the tiles of type A in various orientations different names according to roughly how it looks: L, R, 7, and J (for rotations of $0^\circ, 90^\circ, 180^\circ, 270^\circ$ clockwise respectively; the name for R comes from the lowercase r).

Let $a_n, b_n, c_n$ be the number of ways to tile a $2 \times n$ board such that the first column contains respectively two, one, zero squares covered by a tile of type A. Note that the total number of ways to tile a $2 \times n$ board is then $a_n + b_n + c_n$ . We begin by initializing as follows:

• $a_1 = b_1 = 0$ ; there's not enough space to extend any tile of type A there.
• $c_1 = 1$ for obvious reasons.
• $a_2 = 2$ and $b_2 = 2$ can be brute-forced.
• $c_2 = 0$ ; if the first column doesn't have any tile of type A, the second column is forced not to have any tile of type A either and so violates the condition that no three tiles of type B can be replaced by a tile of type A.
• $a_3 = 2$ . After putting an L-tile on the first column, the remaining space needs to be filled with a 7-tile (not tiles of type B because they can be replaced); similarly, after putting an R-tile on the first column, the remaining space needs to be filled with a J-tile.
• $b_3 = 2$ . After putting a 7-tile, the remaining space is not enough of any tiles of type A. Similar for a J-tile.
• $c_3 = 2$ . After putting two tiles of type B on the first column, both squares in the second column needs to be filled with a tile of type A, so only an L-tile or an R-tile works.

Now we begin the recursion.

Sequence $a$ : WLOG put an L-tile on the first column; later we will multiply the result by two to count where the first column has an R-tile instead. Now there are two cases:

• Case 1: The second column's empty space is filled with a tile of type A.

Then it must be a 7-tile, filling the second and third columns. The rest is a free $2 \times (n-3)$ board, so there are $a_{n-3} + b_{n-3} + c_{n-3}$ ways to fill the rest.

• Case 2: The second column's empty space is filled with a tile of type B.

Then the third column cannot be tiled with two squares of type B. But in all other cases, the third column is free. So there are $a_{n-2} + b_{n-2}$ ways to fill the rest (either one or two squares in the third column are of type A, so it's the sum of $b_{n-2}$ and $a_{n-2}$ ).

In total, $a_n = 2(a_{n-3} + b_{n-3} + c_{n-3} + a_{n-2} + b_{n-2})$ .

Sequence $b$ : WLOG put a 7-tile on the first column; later we will multiply the result by two to count where the first column has a J-tile instead. It's obvious that the rest is a free $2 \times (n-2)$ board, so $b_n = 2(a_{n-2} + b_{n-2} + c_{n-2})$ .

Sequence $c$ : The second column cannot have any tile of type B, so the remaining $2 \times (n-1)$ board must be tiled with two squares of type A in its first column; aka $c_n = a_{n-1}$ .

Just solve the resulting system of recursions to get $a_8 = 252, b_8 = 208, c_8 = 96$ , and so the number of ways to tile a $2 \times 8$ board is $a_8 + b_8 + c_8 = \boxed{556}$ .

Consider ways to tile a $2 \times n$ grid under the problem's restrictions where (a) none of the rightmost two squares are tiled with B; (b) one is; or (c) both are. Let there be $a_n, b_n, c_n$ ways respectively.

For each configuration for $n \geq 4$ , find its rightmost "fault line", i.e. a vertical line along which we can cut the configuration into a smaller configuration plus a few blocks. We'll list all the possibilities to arrive at a set of three recurrences.

(a)-type configurations must end in piece A with its missing corner facing inward, but that piece A could form a $2 \times 2$ block with another B or a $2 \times 3$ block with another A block. In either case, the fault line is immediately next to the blocks, and the added pieces can be flipped vertically in 2 orientations. The first case yields $2(a_{n-2} + b_{n-2})$ possibilities, since we can't extend a smaller (c) configuration or our B block would form an L-shape with the smaller configuration's B squares, while the second case yields $2(a_{n-3} + b_{n-3} + c_{n-3})$ possibilities, since the smaller configuration touches two square of an A-block and no banned L-shapes can arise.

(b)-type configurations must have a piece A with its missing corner facing outward, filled with a piece B; again no banned L-shapes can arise with the smaller configuration to its left, so this can be tacked onto any smaller configuration, and again the added pieces can be flipped vertically for two configurations.

(c)-type configurations just end in two pieces B. They cannot touch any B-pieces, so the smaller configuration can only be type (a), and there is only one orientation.

This analysis gives us these recurrences:

$a_n = 2(a_{n-2} + b_{n-2} + a_{n-3} + b_{n-3} + c_{n-3})$

$b_n = 2(a_{n-2} + b_{n-2} + c_{n-2})$

$c_n = a_{n-1}$

Obviously we can get rid of all the $c_n$ simply by substituting. Getting rid of $b_n$ is a bit trickier, but doable: from smaller recurrences we get

$2b_{n-2} = 4(a_{n-4} + b_{n-4} + a_{n-5})$

$2b_{n-3} = 4(a_{n-5} + b_{n-5} + a_{n-6})$

$2a_{n-2} = 4(a_{n-4} + b_{n-4} + a_{n-5} + b_{n-5} + a_{n-6}$

and when we substitute these into $a_n$ 's original recurrence, all the $b_i$ terms cancel; we get $a_n = 4a_{n-2} + 2a_{n-3} + 2a_{n-4} + 4a_{n-5}$ .

To deal with this recurrence, of course we want to derive a closed-form expression $a_n = k_1r_1^n + k_2r_2^n + k_3r_3^n + k_4r_4^n + k_5r_5^n$ , where the $r_i$ are distinct roots of the polynomial $x^5 - 4x^3 - 2x^2 - 2x + 4$ . Unfortunately this polynomial, being a quintic with no rational roots, is probably not going to be solvable by radicals. Oh well, we can do it numerically and hope that the error won't be too large, since we're only looking for terms up to around $n = 8$ .

So, we solve for roots numerically and find approximate values:

$r_1 \approx -1.59658240467220$

$r_2 \approx -1.21393380795884$

$r_3 \approx 2.34981531571951$

$r_4 \approx 0.230350448455768 - 0.908423178153185i$

$r_5 \approx 0.230350448455768 + 0.908423178153185i$ .

Solving for the recurrence coefficients with the first few terms yields

$k_1 \approx 0.222646558540922$

$k_2 \approx 0.195388512005856$

$k_3 \approx 0.260020188287669$

$k_4 \approx 0.160972370582776 - 0.0509108751992688i$

$k_5 \approx 0.160972370582776 + 0.0509108751992688i$

So now we can evaluate $a_n = k_1r_1^n + k_2r_2^n + k_3r_3^n + k_4r_4^n + k_5r_5^n$ very easily. To finish, we need to express $b_n$ and $c_n$ in terms of $a_i$ s. After more algebra we get $b_n = 2a_n - 2a_{n-1} - 2a_{n-2} + 2a_{n-3} - 4a_{n-4}$ . Of course, our original recurrence for $c_n$ works just fine.

Our final answer is therefore $a_8 + b_8 + c_8 = 3a_8 - a_7 - 2a_6 + 2a_5 - 4a_4$ . Evaluating our closed-form approximation for these $a_n$ yields 555.999999999998. Obviously the actual answer is an integer (in fact, even since reflecting a solution about its long axis is an involution with no fixed points), so the answer is very likely to be $\boxed{556}$ .