Let $n$ be a positive integer. In how many ways can a $4 \times 4n$ grid be tiled with the following tetromino? [asy][asy] size(4cm); draw((1,0)--(3,0)--(3,1)--(0,1)--(0,0)--(1,0)--(1,2)--(2,2)--(2,0)); [/asy][/asy]
Problem
Source: Cono Sur Olympiad 2017, problem 3
Tags: combinatorics, cono sur
lifeisgood03
18.08.2017 04:37
We can construct a recursion.
Note that when $n=1$, there are two tilings
If $A_n$ is the number of tilings for the grid, then given a $4\times 4(n-1)$ tiling, we have two choices:
Add a $4\times 4$ block to the end of it: There are two orientations for this block, so the new blocks created are $2A_{n-1}$
"open up" the previous block: Note that the rightmost side of the block must have a tetromino that covers three tiles. We can remove that tetromino and then complete the block. There are two ways to do this: the new block we have, and its reflection.
Thus, $A_n=2A_{n-1}+2$.
Now we just need to find an explicit formula for this. This is not too hard, you can probably look this up, but one finds in the end that $A_n=2^{n+1}-2$
LaPlanta
25.08.2017 05:28
Let $T(n)$ be the number of ways to tile a $4\times4n$ grid. See that $T(2)=2$.
If you start with the $4\times4n$ grid, you can choose two ways to fill the left hand column. After this, there's the choice to fill a square or not. If you do, there are $T(n-1)$ ways to fill the rest. Or you can chose to not fill a square and continue to fill a $4\times8$ rectangle that can't be subdivided into squares (which can be done in only one way after the initial choice) and are left with a $4\times4(n-2)$ grid to tile. This reasoning continues for every $4\times4k$ rectangle with $k\leq n$
The recursion results in $T(n)=2(T(n-1)+\ldots+T(1))$. Solvig it gives $T(n)=3T(n-1)$, so $T(n)=2\cdot3^{n-1}$.
lifeisgood03
25.08.2017 05:36
Quote: $T(2)=2$ This is false: $T(1)=2$ LaPlanta wrote: The recursion results in $T(n)=2(T(n-1)+\ldots+T(1))$. Solvig it gives $T(n)=3T(n-1)$ This is not correct; if you just plug in $n=2$ into your first equation you get $T(2)=4T(1)$ which contradicts your end statement...
LaPlanta
25.08.2017 06:03
Let $T(n)$ be the number of ways to tile a $4\times4n$ grid. See that $T(1)=2$. If you start with the $4\times4n$ grid, you can choose two ways to fill the left hand column. After this, there's the choice to fill a square or not. If you do, there are $T(n-1)$ ways to fill the rest. Or you can chose to not fill a square and continue to fill a $4\times8$ rectangle that can't be subdivided into rectangles (which can be done in only one way after the initial choice) and are left with a $4\times4(n-2)$ grid to tile. This reasoning continues for every $4\times4k$ rectangle with $k\leq n$ The recursion results in $T(n)=2(T(n-1)+\ldots+T(1)+1)$. Solvig it gives $T(n)=3T(n-1)$, so $T(n)=2\cdot3^{n-1}$. The mistake in the recursion of the other post was that I didn't consider the last $4\times4n$ rectangle that can't be subdivided into other rectangles, and can be done in 2 ways. Sorry for that.