1
$\begingroup$

How many coverings of the rectangle with height $1$ and length $n$ exist, if we use only tiles with height $1$ of the following 6 types:

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

The solution should be in a closed form (formula).

$\endgroup$
1
$\begingroup$

define $U(n)$ to be the number of coverings for the $1\times n$ rectangle with the bottom right corner cut off.

Define $T(n)$ to be the number of coverings for the $1\times n$ rectangle with the top right corner cut off.

Define $R(n)$ to be the number of coverings for the $1\times n$ tectangle.

We have $T(n)=R(n-1)$ since the covering must end in a triangle.

We have $U(n)=R(n-1)+U(n-1)$ since the covering can end in a paralelogram or a triangle.

We have $R(n)=T(n)+U(n)+R(n-1)$ depending on which of the three options is used to finish the covering.

Now we just need to know that $U(1)=1,T(1)=1,R(1)=3$ and we can compute any other value with the previous recursion.

Some c++ code (it only works if the actual answer fits inside an int)

#include <bits/stdc++.h>
using namespace std;

const int MAX=100010; // the size of the arrays
int T[MAX]; // an array to save T[i]
int U[MAX]; // an array to save U[i]
int R[MAX]; // an array to save R[i]

int main(){
    T[1]=1;
    U[1]=1;
    R[1]=3;
    int n; // the value for which we want R[i]
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        T[i]=R[i-1];
        U[i]=U[i-1]+R[i-1];
        R[i]=T[i]+U[i]+R[i-1];
    }
    printf("%d\n",R[n]); // be careful of overflows!
}
$\endgroup$
2
  • 1
    $\begingroup$ The largest eigenvalue is $2+\sqrt 2$, so as $n$ gets large the values will multiply by that for each step. $\endgroup$ – Ross Millikan Jul 17 '16 at 21:54
  • $\begingroup$ @Carry I have edited my question. The solution should be a formula. $\endgroup$ – Egor Okhterov Jul 18 '16 at 10:19

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.