2
$\begingroup$

A $2×N$ rectangle is to be tiled with $1×1$, $1×2$ and $2×1$ tiles. Prove that there is an $x$ such that the number of possible tilings tends to $kx^N$ as $N$ gets large. Find $x$, to $2$ decimal places.

I tried to solve the problem initially by sketching all the possible tilings for $n=1,2,3,..$ but I realised this isn't a practical way to solve the problem.

$\endgroup$
9
  • $\begingroup$ Try to write a linear recursion first by columns, and put it in its matrix form. Perhaps eigenvalues would help there. $\endgroup$
    – Phicar
    Oct 7 '16 at 22:59
  • 1
    $\begingroup$ It is due to be connected to Fibonacci numbers. Have a look for example at (dartmouth.edu/~academicoutreach/docs/…). Besides, I am surprised by the $1 \times 1$. Isn't it $1 \times 2$ ? $\endgroup$
    – Jean Marie
    Oct 7 '16 at 23:02
  • 1
    $\begingroup$ Are you allowed to flip the $2\times 1$ tile? i.e do both $2 \times 1$ and $1\times 2$ tiles allowed? If not, the number of possible tilings is trivial. $\endgroup$ Oct 7 '16 at 23:42
  • $\begingroup$ Yes you are allowed to flip the tiles $\endgroup$
    – Hogg
    Oct 7 '16 at 23:53
  • $\begingroup$ Yes, you can use $1 \times 1$ tiles, $2 \times1$ tiles, and $1 \times 2$ tiles. $\endgroup$
    – Hogg
    Oct 8 '16 at 0:18
9
+50
$\begingroup$

I would like to do some drawings here, but it will be a good exercise to do it on your own ^^

I follow what Philcar said: you can model the problem with a linear recursion. If you only can tile with $1\times 2$ and $2\times 1$, you get the classical tiling problem which leads to Fibonacci numbers and is equivalent to $k\phi^N$ with $\phi$ the golden ratio (1.618...). More generally, if you reach a linear recursion for the number of possible tilings, you will end with a $kx^N$ as awaited. Let us do the job for your case now.

Denote by $R_N$ the $2\times N$ rectangle you want to tile, $T_N$ the number of possible tilings with $1\times 1$, $1\times 2$ or $2\times 1$ tiles, and $L_N$ the possible tilings for a $2\times N$ rectangle with a $1\times 1$ tile at the bottom right (it appears naturally in the computations, see below). What can be said about the tilings of $R_N$ for a given $N$? Suppose you have such a tiling, and just look at the bottom right corner (the $1\times 1$ corner placed at $(2, N)$ with matrix notations:

  • either you get a $2\times 1$ tile, that is a tile filling the last column. Searching possible ways to fill in the rest is the same as searching tilings for $R_{N-1}$ (the remaining places): so you get $T_{N-1}$ such tilings by definition;
  • or you get a $1\times 1$ tile, and you get $L_N$ by definition;
  • or you get a $1 \times 2$ tile. We can either get a $1\times 2$ tile above it, in which case you get $T_{N-2}$ possibilities for the remaining rectangle $R_{N-2}$; or one $1\times 1$ tile above it at the upper right corner (which create an "L"), and you get $L_{N-1}$ possibilities by definition.

At last you end up with a twisted linear recursion for $(T_N,L_N)$:

$$ \forall N \in \mathbf{N}, N \geqslant 2, \left\{ \begin{array}{l} T_N = T_{N-1} + T_{N-2} + L_N + L_{N-1} \\ L_N = T_{N-1} + L_{N-1} \end{array} \right. $$

From those two relations, we get $T_{N-1} + L_{N-1} = L_N = T_N - T_{N-2} -L_N$ so that:

$$L_N = \frac{T_N - T_{N-2}}{2}$$

which gives you the sought recursion:

$$T_N = 3T_{N-1} + T_{N-2} -T_{N-3}$$

So the characteristic equation has three distinct solutions (the paradisiac case), which can be explicited and the greater one is about $\mathbf{x=3.21}$ (see here).

Now if you want to determine the constant $k$, you have to write down the general solution as $T_N = k_1x_1^N + k_2x_2^N + kx^N$ ($x_1$ and $x_2$ being the two other solutions, and use the first values of $T_N$ computed by hand ($N=0, 1, 2$ are easy and sufficient) to determine the constants, in particular the relevant $k$ (but here, you have to use the exact solutions).

$\endgroup$
11
  • 1
    $\begingroup$ @Hogg Take you rectangle $R_N$, you want to tile it. We suppose in this third case that there is a $1\times2$ tile at the bottom right corner. Now, what can happen above it, that is at the top right corner ? There is place either to a 1x2 tile (and you get a $R_{N-2}$ rectangle remaining, so $T_{N-2}$ possibilities for tiling the rest), or to a 1x1, in which case the remainder to tile is... A rectangle from which we substracted an L, as in the second bullet point (but with size one less), right ? Draw a picture, and tell me if you see it! $\endgroup$ Dec 11 '16 at 22:08
  • 1
    $\begingroup$ You can either have a $1\times2$ tile directly above it, or two $1\times1$ tiles above it. Also, should it say $T_{N-2},R_{N-2}$ instead of $T_{N-1},R_{N-1}$ $\endgroup$
    – Hogg
    Dec 11 '16 at 22:10
  • 1
    $\begingroup$ @Hogg No, there is another possibility: On tile 1x1 above it, then a 1x2, it gives an L of size n-2. There is no reason for having a 1x1 tile at the place $(1, N-1)$ if you put a 1x1 at $(1,N)$, you can have something else (in this case a 1x2) $\endgroup$ Dec 11 '16 at 22:15
  • 2
    $\begingroup$ @Hogg We actually discrimine only on what happens on the place $(1,N)$, provided you have the bottom right filled with a tile $1\times 2$. There cannot be a tile $2\times 1$ (not enough place for it, for the place juste below is already filled), hence it remains the two other possibilities : a $1\times 2$ (which gives $T_{N-2}$) and a $1\times 1$ (which gives a $L_{N-1}$). You do not have to understand for the remaining places, it would juste will create more distinctions of cases and more trickier computations: this one suffice. $\endgroup$ Dec 11 '16 at 22:30
  • 2
    $\begingroup$ @Hogg Well, I didn't at first, and I wasn't thinking to need some intermediate quantity like that... but it arose naturally during the computations, I couldn't avoid it... hence I introduced it. It it where the intuition lacks of lucidity and formality allows going further ;) Do you see why when you try ? When you get an "L" (for instance with an 1x1 at the bottom left, you cannot guarantee getting rid of it after one tile more: if you put a 1x2, you get another "L" (smaller, from where we get the idea of finding a recursion relation). Is at least the formal solution satisfying you? $\endgroup$ Dec 13 '16 at 20:43
1
$\begingroup$

For each $2\times 1$ column, your choices are determined by how many rows are continuing a previous $1\times 2$ brick. Initially neither row is (call this state ${\mathsf{0}}$). When neither row is, you may place a $2\times 1$ brick (staying in ${\mathsf{0}}$). Also, each row continuing a previous $1\times 2$ brick must be completed, and each row not continuing a previous $1\times 2$ brick may be used to start a $1\times 2$ brick or to place a $1\times 1$ brick. So your choices are: ${\mathsf{0}}\rightarrow {\mathsf{0}}\;(\times 2),{\mathsf{1}}\;(\times 2),{\mathsf{2}}$; ${\mathsf{1}}\rightarrow {\mathsf{0}},{\mathsf{1}}$; and ${\mathsf{2}}\rightarrow {\mathsf{0}}$. Since you start in state ${\mathsf{0}}$, the number of ways to be in each state after $N$ columns is given by: $$ \left(\begin{matrix}2 & 2 & 1\\ 1 & 1 & 0\\ 1 & 0 & 0 \end{matrix}\right)^N\cdot \left(\begin{matrix}1\\ 0\\0 \end{matrix}\right)\sim u_1\lambda_1^N, $$ where $\lambda_1\approx 3.21432$ is the largest eigenvalue of the matrix being raised to the $N$-th power. In particular, the number of ways to close off the rectangle is equal to the number of ways of being back in state $\mathsf{0}$, still asymptotic to a constant times $\lambda_1^N$.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Could you explain the sentence "So your choices are: $0→0 (×2),1 (×2), 2; 1→0, 1$; and $2→0$". $\endgroup$
    – Hogg
    Dec 31 '16 at 15:07
  • 1
    $\begingroup$ Yes. If the state is 0 (neither row in the middle of a horizontal brick), you can place a vertical brick or two little square bricks, leaving the state 0 (in x2 different ways); or you can place one little square brick and one horizontal brick, changing the state to 1 (in x2 different ways, because the little brick can be in either row); or you can place two horizontal bricks, changing the state to 2. ... $\endgroup$
    – mjqxxxx
    Jan 5 '17 at 15:32
  • 1
    $\begingroup$ ... If the state is 1 (exactly one row in the middle of a horizontal brick), you must complete the horizontal brick, and may place either a little square brick or a new horizontal brick in the other row (causing the state to be 0 or 1, respectively). Finally, if the state is 2 (both rows in the middle of horizontal bricks), you must complete both, taking the state to 0. $\endgroup$
    – mjqxxxx
    Jan 5 '17 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.