## Problem of the Day #6: Tiling a 2 by 2 by n Box with Rectangular Prisms
*March 25, 2011*

*Posted by Billy in : potd , trackback*

In how many distinct ways can $2n$ identical $1\times1\times2$ rectangular prisms be placed inside a $2\times2\times n$ box?

**Solution:**

Let $a_n$ be the number of ways to completely fill a $2\times2\times n$ box with $1\times1\times2$ blocks, and let $b_n$ be the number of of ways to fill a $2\times2\times n$ box with $1\times1\times2$ blocks such that there is a $1$-block gap at the top that is not filled and the part at the top that is filled has $2$ vertical blocks. An example of an arrangement for $b_4$ is shown above. Note the missing block from the top and the two vertical blocks.

By casework for $n\leq2$, we can see that $a_0=1$ (there is $1$ way to fill a $2\times2\times0$ box with blocksâ€”by placing none), $b_0=0$, $a_1=2$, $b_1=0$, $a_2=9$, and $b_2=4$. Now, we need a recurrence relation. We see that $$b_n=4a_{n-2}+b_{n-1}$$ The $4a_{n-2}$ is from the $4$ ways to add $2$ vertical blocks and $1$ horizontal block to $a_{n-2}$ and the $b_{n-1}$ is from adding two vertical blocks in the “hole” at the top of $b_{n-1}$. We also see that $$a_n=2a_{n-1}+a_{n-2}+b_n$$ The $2a_n$ is from adding $2$ horizontal blocks to $a_{n-1}$, the $a_{n-2}$ is from adding $4$ vertical blocks to $a_{n-2}$, and the $b_n$ is from filling in the hole of $b_n$ with a horizontal block.

We want to get rid of $b$ in the $2$ equations so that we will have a recurrence relation only in terms of $a$. To do this, consider \[\begin{align*}a_{n+1}-a_n &= (2a_{n}+a_{n-1}+b_{n+1})-(2a_{n-1}+a_{n-2}+b_n) \\&= 2a_n-a_{n-1}-a_{n-2}+(b_{n+1}-b_n) \\&= 2a_n-a_{n-1}-a_{n-2}+4a_{n-1} \\&= 2a_n+3a_{n-1}-a_{n-2}\end{align*}\]

Thus, $$a_{n+1}-3a_n-3a_{n-1}+a_{n-2}=0$$ To solve this, we must find the roots of the characteristic polynomial of the relation, $$x^3-3x^2-3x+1$$ We immediately see that $x=-1$ is a root, and after dividing the polynomial by $x+1$ we are left with the quadratic $$x^2-4x+1$$ The roots to this are $x=2\pm\sqrt{3}$, so we can write $$a_n=\alpha(-1)^n+\beta(2+\sqrt{3})^n+\gamma(2-\sqrt{3})^n$$ From our initial conditions, we see that \[\begin{align*}a_0 &= 1 = \alpha+\beta+\gamma \\ a_1 &= 2 = -\alpha+(2+\sqrt{3})\beta+(2-\sqrt{3})\gamma \\ a_2 &= 9 = \alpha+(2+\sqrt{3})^2\beta+(2-\sqrt{3})^2\gamma\end{align*}\] This system of equations yields \[\begin{align*}\alpha &= \frac{1}{3} \\ \beta &= \frac{1}{6}(2+\sqrt{3}) \\ \gamma &= \frac{1}{6}(2-\sqrt{3})\end{align*}\] which means that $$a_n=\frac{1}{3}(-1)^n+\frac{1}{6}(2+\sqrt{3})^{n+1}+\frac{1}{6}(2-\sqrt{3})^{n+1}$$

**Bonus challenge**: write a program to verify that this is correct.

## Comments»

Note: I recently realized that this problem may have been written earlier by someone else somewhere on the internet, but I thought of it without having seen it beforehand.