Domino domination!

Computer Science Level 4

Let $f(n)$ be the number of ways in which one can cover a $3 \times n$ rectangle with dominoes (rectangles with side length $1 \times 2$ ). Find the sum of the digits of $f(100)$ .

Explicit examples

$f(3)=0$
$f(4)=11$
$f(10)=571$

The answer is 131.

1 solution

Ariel Gershon
May 16, 2014

I don't know how to draw pictures here so I'll describe it using chess coordinates.

Suppose we need to tile a $3 \times n$ checkerboard with dominoes. Let the rows be represented by A,B,C; and let the columns be represented by 1,2,3,etc. Let's only consider the cases where $n$ is even.

First let's define an almost-checkerboard to be a checkerboard with one corner missing. Or you could think of it as attaching the squares $A0$ and $B0$ to the existing $3 \times n$ checkerboard. Let's define a new function $g(n)$ , to be the number of ways to tile a $3 \times (n+1)$ almost-checkerboard. Note that an almost-checkerboard of this form can be tiled with dominoes only if $n$ is even.

Now let's try to find a recursive definition for $f(n)$ . Assume that $n \ge 2$ and consider the three squares $A1, B1, C1$ . We have 3 mutually exclusive cases:

$(1)$ $A1$ and $B1$ are covered by a single domino. This forces $C1$ and $C2$ to be covered by a single domino, and the rest is a $3 \times (n-1)$ almost-checkerboard. So in this case, there are $g(n-2)$ ways of tiling the rest.

$(2)$ $C1$ and $B1$ are covered by a single domino. This is similar to case $(1)$ - again there are $g(n-2)$ ways in this case.

$(3)$ $A1, B1$ and $C1$ are covered by 3 different dominoes. Then these three dominoes also cover $A2, B2$ and $C2$ . The rest is a $3 \times (n-2)$ checkerboard, which can be tiled $f(n-2)$ ways.

Therefore, $f(n) = 2g(n-2) + f(n-2)$ for $n \ge 2$ . $(A)$

Similarly, using a case analysis we can find that $g(n) = g(n-2) + f(n)$ for $n \ge 2$ .

Now we can replace $f(n)$ using equation $(A)$ to get:

$g(n) = 3g(n-2) + f(n-2)$ $(B)$

For the base cases we can set $f(0)=1=g(0)$ , and now we have a well-defined joint recursive formula for $f$ and $g$ .

Plugging this into DrRacket, I got $f(100) = 31208688988045323113527764971$ .

I wrote a similar solution in C++ but I didn't get the right answer.

My idea is the same of yours with the only difference that my G(n) is the number of ways to tile a (3 x n) almost checkerboard.

Then:

F(n)=F(n-2) + G(n-1)
G(n)=F(n-1) + G(n-2)
F(0)=1
F(1)=0
G(0)=0
G(1)=1

#include <iostream>
#include <string.h>
using namespace std;

typedef long long ll;

ll f[105];
ll fs[105];

ll func1(int);
ll func2(int);

int main()
{
        memset( f, -1, sizeof(f) );
        memset( fs, -1, sizeof(fs) );

        f[0]=1; f[1]=0;
        fs[0]=0; fs[1]=1;

        ll f100=func1(100);
        int sol=0;
        while( f100!=0 ){
                sol += f100%10;
                f100/=10;
        }
        cout << sol << endl;

    return 0;
}

ll func1(int n)
{
        if( f[n]!=-1 ) return f[n];

        return f[n] = func1(n-2) + 2*( func2(n-1) );
}

ll func2(int n)
{
        if( fs[n]!=-1 ) return fs[n];

        return fs[n] = func1(n-1) + func2(n-2);
}

This method gave me F(100)=1165076283225270251 and then Digit_Sum( F(100) )=65.

Where am I wrong?

Brian Riccardi - 6 years, 8 months ago

Ok I think the problem is because the size of C/C++ "long long" is not enough for F(100). :(

Brian Riccardi - 6 years, 8 months ago

Domino domination!

The answer is 131.

1 solution

0 pending reports