Author |
Topic: Domino and chess (Read 903 times) |
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
 |
Domino and chess
« on: Jun 29th, 2004, 11:14am » |
 Quote  Modify
|
How many ways are there to arrange 32 domino tiles on a 8x8 chessboard? Of course, a domino tile must cover exactly 2 squares, without an overlap. The tiles are all equivalent.
As an appetizer, how many ways are there on a 2x2, 4x4, 6x6 board?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Domino and chess
« Reply #1 on: Jun 29th, 2004, 2:19pm » |
Quote Modify
|
I can tell you for a 2 x N board.. ::fibonacci(N+1)::
Of course that doesn't help much for 4x4, 6x6 or 8x8
|
| « Last Edit: Jun 29th, 2004, 2:31pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Domino and chess
« Reply #2 on: Jun 29th, 2004, 3:19pm » |
Quote Modify
|
I wouldn't want to spoil your programming fun, but there is actually a general formula for an N x M board.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: Domino and chess
« Reply #3 on: Jun 29th, 2004, 11:34pm » |
Quote Modify
|
Offhand, I can tell you that there are exactly 0 ways for boards with both M and N odd... 
For 3 x N boards, I found that te number of configurations is 0 for odd N and :: 8*3N/2/9 for N > 2 :: for even N. It is not that hard to show: drawing a few situations, you should be able to derive the following recurrence relation for T(N):
T(N) = 2*(T(N-2) + T(N-4) + ... + T(2) + 1);
T(2) = 3.
The rest is easy.
|
| « Last Edit: Jun 29th, 2004, 11:35pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Domino and chess
« Reply #4 on: Jun 30th, 2004, 2:24am » |
Quote Modify
|
I don't think that's right Pietro, for n=4 I get 11, and your formula gives 8
::
The recursive formula is
T(N) = 4 T(N-2) - T(N-4)
with T(0)=1, T(2)=3 (for even)
T(1)=0, T(3)=0 (for uneven, not surprisingly all 0)
closed formula (only for n even)
(1/2 - [sqrt]3/6)*(2 - [sqrt]3)(n/2) + ([sqrt]3/6 + 1/2)*([sqrt]3 + 2)(n/2)
or just round ([sqrt]3/6 + 1/2)*([sqrt]3 + 2)(n/2) to the nearest integer
::
|
| « Last Edit: Jun 30th, 2004, 3:01am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Domino and chess
« Reply #5 on: Jul 10th, 2004, 1:20pm » |
Quote Modify
|
As T&B pointed out.. there is a general formula for this. Here is how they did it (I know the general approach and no details at all). Sorry if you guys know this already, I am just trying to cross the 50 post boundary
Colour the grid like a chessboard, alternate black/white. What we get is a bipartite graph by considering each cell as a vertex and joining neighbouring cells (which share a side) with edges. A tiling of the grid corresponds (in a 1-1 way) to a perfect matching of the graph. Thus the number of tilings is same as the number of perfect matchings in the graph.
Now someone proved that the number of perfect matchings of a graph equals the permanent of a certain matrix.
Someone else(or maybe the same person, don't know) proved that that permanent of that grid is the determinant of someother matrix and gave an easy way to calculate that determinant (that is what the closed formula is)
Quite an interesting problem.
btw, the answer for the 8x8 case is supposedly 12988816.
Here is a link which gives more details:
http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/domino
|
| « Last Edit: Jul 10th, 2004, 1:32pm by Aryabhatta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print