wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> tiling a nXn checker board with 2x1 dominoes
        
(Message started by: gt on Aug 28^th, 2009, 6:59am)

Title: tiling a nXn checker board with 2x1 dominoes
Post by gt on Aug 28^th, 2009, 6:59am

hey guys...

" in how many ways , can we tile a n X n checker board , with 2X1 dominoes... "

consider cases of n being odd, n being even

and also more general case of an nXm checker board......

i dont know , if this has already been discussed...

this question occurred to me while reading about tiling 2Xn checkerboard with dominoes

Title: Re: tiling a nXn checker board with 2x1 dominoes
Post by towr on Aug 28^th, 2009, 7:33am

The answer for odd n is very easy. (Or, in the case of a rectangle, when both n and m are odd.)

Title: Re: tiling a nXn checker board with 2x1 dominoes
Post by gt on Aug 31^st, 2009, 3:54pm

@above

could u elaborate a bit more

as to why it is easy ???

Title: Re: tiling a nXn checker board with 2x1 dominoes
Post by towr on Aug 31^st, 2009, 11:51pm

on 08/31/09 at 15:54:34, gt wrote:

could u elaborate a bit more

as to why it is easy ???

If n and m are odd, then you have an odd number of squares. But any number of 2x1 dominoes cover an even number of squares; so it just can't work.

Title: Re: tiling a nXn checker board with 2x1 dominoes
Post by R on Sep 23^rd, 2009, 9:24pm

Slightly changing the semantics of the problem, as explaining will be easier for this new semantic. Filling nxn check board with 2x1 dominoes is equivalent to walking in a matrix of nxn to reach the right-bottom corner with jump size = 2.
Now can we write a recurrence relation as follows:

Code:

ways(n,n) = 2 + ways(n-2, n) + ways(n, n-2);

Title: Re: tiling a nXn checker board with 2x1 dominoes
Post by towr on Sep 24^th, 2009, 12:33am

on 09/23/09 at 21:24:36, R wrote:

ways(n,n) = 2 + ways(n-2, n) + ways(n, n-2);

You're not tiling the whole matrix in that recursion. You have to walk through the whole matrix, not just get to the bottom-right.
And don't ways(n-2, n) and ways(n, n-2) have the same value?

Title: Re: tiling a nXn checker board with 2x1 dominoes
Post by R on Sep 24^th, 2009, 1:06am

on 09/24/09 at 00:33:44, towr wrote:

You're not tiling the whole matrix in that recursion. You have to walk through the whole matrix, not just get to the bottom-right.

Starting from (1,1).
Ways was the number of ways in which one can reach from (1,1) to (n,n). It will cover the whole matrix, Right?

Quote:

And don't ways(n-2, n) and ways(n, n-2) have the same value?

In a square matrix, Yes!!!
I meant to write for general case.

Code:

ways(m,n) = 2 + ways(m-2, n) + (m, n-2);

Title: Re: tiling a nXn checker board with 2x1 dominoes
Post by towr on Sep 24^th, 2009, 1:36am

on 09/24/09 at 01:06:03, R wrote:

Starting from (1,1).
Ways was the number of ways in which one can reach from (1,1) to (n,n). It will cover the whole matrix, Right?

I don't see why. You can get from (1,1) to (n,n) without covering the matrix, and in any case, your recursion only counts moves to the right and down; n and m are decreasing. You will cover only n+m squares.

Also, for n=4, your recursion gives me 10, whereas the real number should be at least 25 (5²)
In general n=2k should be greater or equal to fib(2k-1)^k (which is what you get if you independently tile the k 2x2k pieces)

Title: Re: tiling a nXn checker board with 2x1 dominoes
Post by R on Sep 24^th, 2009, 2:19am

on 09/24/09 at 01:36:46, towr wrote:

Oh I see the heck. :)