Diet Tetris (Take 2)

Tiling problems are related to Fibonacci sequences and recursion, and hence are very suitable for the application of dynamic programming.

First, think of the $2 \times 100$ box as a collection of $25$ small boxes of size $2 \times 4$ . We will start tiling from the leftmost box and consider one box at a time. We define the number of ways the $n^{th}$ box can be filled with no overreach as $jar[n][0]$ and the number of ways it can be filled with overreach as $jar[n][1]$ .

Whenever we try to fill a particular box (say, $(n+1)^{th}$ box), we can have $2$ possible initial states. In one state, the box will be empty initially. In the other case, it will have overreach from the previous box (in this case, the $n^{th}$ box). So, in how many ways can we fill the $(n+1)^{th}$ box?

If we want to fill the box with no overreach, we can do it in $2 \cdot jar[n][0] + jar[n][1]$ ways. And, if we want fill it with overreach, the number of ways will be $jar[n][0] + jar[n][1]$ . Hence, we get the following recursive relations.

$jar[n+1][0] = 2 \cdot jar[n][0] + jar[n][1]$ $jar[n+1][1] = jar[n][0] + jar[n][1]$

with the initial conditions

$jar[0][0] = 1$ $jar[0][1] = 0$

Here, what we want to find is $jar[25][0]$ .

N.B. I implemented the 2d array in a 1d list.

1
2
3
4
5
6
7

jar = [1, 0]

for i in range(25):
    jar.append( 2*jar[2*i] + jar[2*i+1] )
    jar.append( jar[2*i] + jar[2*i+1] )

print(jar[50])

Let $f(n)$ be the number of fully tiled 2 x 4n boxes and $g(n)$ the number of "overtiled" 2 x 4n boxes, such as this one (overtiled 2 x 4 box) Then for each fully tiled 2 x 4n box we can add one purple $\textbf{or}$ one blue 2 x 4 block to get a fully tiled 2 x 4(n + 1) box. Also, for each overtiled 2 x 4n box we can add one L - shape to get a fully tiled 2 x 4(n+1) box. The recurrence relation for $f(n)$ is therefore $f(n+1) = 2 f(n) + g(n)$ . Another equation is for overtiled boxes, which can be made either by adding an L - shape after a fully tiled sequence $\textbf{or}$ a Z - shape (two misaligned purple bars) after an overtiled sequence. Thus, second equation is $g(n+1) = f(n) + g(n)$ . Initial conditions are $f(1)=2$ and $g(1)=1$ . Wolfram Alpha successfully solves such systems (even the free version). The answer is $f(25)=20 365 011 074$ .

Let $t(n)$ be the number of ways of tiling a $4n \times 2$ box. Say a tiling has a "vertical break" if we can split it into a tiling of a $4k \times 2$ box and a $4(n-k) \times 2$ box, where $0<k<n$ , without cutting a tile. A couple of observations first:

1) There are two ways to tile a $4 \times 2$ box with no vertical breaks 2) There is a unique way to tile a $4n \times 2$ box with no vertical breaks for $n>1$ (see the last picture in the question for an example)

From this we can build a recurrence for $t(n)$ : there is $1$ way to tile the whole box with no vertical breaks. There are $2t(n-1)$ tilings in which the first vertical break from the left creates a $4 \times 2$ box. Then there are $t(n-k)$ tilings whose first vertical break from the left creates a $4k \times 2$ box, where $1<k<n$ .

Putting all this together, we have $t(1)=2$ , $t(2)=5$ and $t(n)=1+2t(n-1)+\sum_{k=2}^{n-1} t(n-k)$

or, re-indexing the sum, $t(n)=1+2t(n-1)+\sum_{k=1}^{n-2} t(k)$

Also, $t(n+1)=1+2t(n)+\sum_{k=1}^{n-1} t(k)$ so that $\begin{aligned} t(n+1)-t(n)&=2t(n)-t(n-1) \\ t(n+1) &= 3t(n)-t(n-1) \end{aligned}$

This is enough to find the answer; we get $t(25)=\boxed{20365011074}$ .

But there's more! The first few values of $t(n)$ are $2,5,13,34,89,\ldots$ - which are all Fibonacci numbers (in fact the sequence is every other Fibonacci number).

If $F_n$ is the $n$ th Fibonacci number, we have $\begin{aligned} F_n &=F_{n-1}+F_{n-2} \\ F_{n+1} &=F_n+F_{n-1} \\ F_{n+2} &=F_{n+1}+F_n \end{aligned}$

By eliminating $F_{n-1}$ and $F_{n+1}$ we find $\begin{aligned} F_{n-1} &= F_n-F_{n-2} \\ F_{n+1} &= F_n + (F_n-F_{n-2}) = 2F_n-F_{n-2} \\ F_{n+2} &=(2F_n-F_{n-2})+F_n = 3F_n-F_{n-2}\end{aligned}$

which - together with the first two values of $t(n)$ - proves that $t(n)=F_{2n+1}$ . So in particular $t(25)=F_{51}$ .

Filling in pieces from left to right, there are only $4$ different combinations that can be added to completely fill the grid:

If the rightmost piece ends evenly, $A$ or $D$ can be used next, but if the rightmost piece ends unevenly, $B$ or $C$ can be used next. If $A$ is used next then the rightmost number of pieces increases by $3$ , if $B$ is used next then the rightmost number of pieces increases by $1$ , if $C$ is used next then the rightmost number of pieces increases by $4$ , and if $D$ is used next then the rightmost number of pieces also increases by $4$ .

If $A_n$ is the number of ways a sequence with a length of $n$ ends in $A$ , $B_n$ is the number of ways a sequence with a length of $n$ ends in $B$ , $C_n$ is the number of ways a sequence with a length of $n$ ends in $C$ , and $D_n$ is the number of ways a sequence with a length of $n$ ends in $D$ , we have the following relationships:

$A_{n + 3} = B_n + D_n$

$B_{n + 1} = A_n + C_n$

$C_{n + 4} = A_n + C_n$

$D_{n + 4} = B_n + D_n$

where $A_3 = 1$ , $B_4 = 1$ , $C_3 = 0$ , and $D_4 = 1$ .

With a little manipulation, $B_{n + 1} = A_n + C_n = (B_n + D_n) + (A_{n - 1} + C_{n - 1}) = B_n + D_n + B_n = B_n + D_{n + 4}$ , or $B_n = D_{n + 4} + B_n$ .

Using $D_4 = 1$ , $B_4 = 1$ , $D_{n + 4} = B_n + D_n$ , and $B_n = D_{n + 4} + B_n$ , the first few terms are $(D_4, B_4, D_8, B_8, D_{12}, B_{12}...) = (1, 1, 2, 3, 5, 8, ...) = (F_1, F_2, F_3, F_4, F_5, F_6, ...)$ , the Fibonacci sequence. Therefore, $D_n = F_{\frac{1}{2}n - 1}$ and $B_n = F_{\frac{1}{2}n}$ for $n$ values that are multiples of $4$ .

A completed grid will end with either $B$ or $D$ for a total of $S_n = D_n + B_n = F_{\frac{1}{2}n - 1} + F_{\frac{1}{2}n} = F_{\frac{1}{2}n + 1}$ ways.

Therefore, for a $2 \times 100$ grid, there are $S_{100} = F_{\frac{1}{2}\cdot 100 + 1} = F_{51}$ ways to fill it. Using Binet's formula, that means there are $F_{51} = \frac{1}{\sqrt{5}}((\frac{1 + \sqrt{5}}{2})^{51} - (\frac{1 - \sqrt{5}}{2})^{51}) = \boxed{20365011074}$ ways to fill the $2 \times 100$ grid.