Author |
Topic: tiling a nXn checker board with 2x1 dominoes (Read 14551 times) |
|
gt
Newbie
Posts: 13
|
 |
tiling a nXn checker board with 2x1 dominoes
« on: Aug 28th, 2009, 6:59am » |
 Quote  Modify
|
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
|
| « Last Edit: Aug 28th, 2009, 7:01am by gt » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: tiling a nXn checker board with 2x1 dominoes
« Reply #1 on: Aug 28th, 2009, 7:33am » |
Quote Modify
|
The answer for odd n is very easy. (Or, in the case of a rectangle, when both n and m are odd.)
|
| « Last Edit: Aug 28th, 2009, 7:40am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
gt
Newbie
Posts: 13
|
|
Re: tiling a nXn checker board with 2x1 dominoes
« Reply #2 on: Aug 31st, 2009, 3:54pm » |
Quote Modify
|
@above
could u elaborate a bit more
as to why it is easy 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: tiling a nXn checker board with 2x1 dominoes
« Reply #3 on: Aug 31st, 2009, 11:51pm » |
Quote Modify
|
on Aug 31st, 2009, 3:54pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: tiling a nXn checker board with 2x1 dominoes
« Reply #4 on: Sep 23rd, 2009, 9:24pm » |
Quote Modify
|
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);
|
|
|
| « Last Edit: Sep 23rd, 2009, 10:04pm by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: tiling a nXn checker board with 2x1 dominoes
« Reply #5 on: Sep 24th, 2009, 12:33am » |
Quote Modify
|
on Sep 23rd, 2009, 9:24pm, R wrote: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);
|
|
|
|
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?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: tiling a nXn checker board with 2x1 dominoes
« Reply #6 on: Sep 24th, 2009, 1:06am » |
Quote Modify
|
on Sep 24th, 2009, 12:33am, 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);
|
|
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: tiling a nXn checker board with 2x1 dominoes
« Reply #7 on: Sep 24th, 2009, 1:36am » |
Quote Modify
|
on Sep 24th, 2009, 1:06am, 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 (52)
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)
|
| « Last Edit: Sep 24th, 2009, 1:37am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: tiling a nXn checker board with 2x1 dominoes
« Reply #8 on: Sep 24th, 2009, 2:19am » |
Quote Modify
|
on Sep 24th, 2009, 1:36am, towr wrote:
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. |
|
Oh I see the heck. 
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print