How many ways are there to tile a 2xn rectangle with dominos?
Many thanks to Karl Heuer for contributing this puzzle.
How many ways are there to tile a 2xn rectangle with dominos?
11 Comments
Phil Ellinger
26/10/2013 07:29:54 pm
1,2,3,5,8,13,21... (n'th Fibonacci number)
Reply
Phil Ellinger
27/10/2013 04:25:21 pm
Got it!
Reply
Paul
27/10/2013 11:18:47 pm
Thanks Phil. You are the first to tackle this puzzle and I do like your approach. Obviously, I can't confirm the answer just yet.
Reply
Tom Thomson
28/10/2013 07:27:46 am
I got bogged down in trying to create a combinatorial mess that I could then simplify, and realised there had to be an easier way. Then tried for a recurrence relation approach, by looking at what would be added, which was almost the right way to do it. I should have calculated the first few elements first and spotted the pattern, rather than trying to derive the pattern from the problem without calculating some sample values, because of course it is exactly as Phil said.
Reply
Paul
28/10/2013 11:21:24 pm
Sometimes it is more satisfying to arrive at a solution after trying a few ideas that went wrong. Thanks as always Tom.
Reply
Tom Thomson
29/10/2013 09:02:50 am
Of course there are conflicting definitions of "n'th Fibonacci number"; Phil is using the definition which has 1 is the first F number and 2 is the second; I grew up with 0 as the first F number (Fsubscript0) and 1 as the second F number (Fsubscript1) so what Phil called the n'th F number is what I would call the n+2'th F number. An interesting way of getting to the Fibonacci sequence. My favorite is: there are n steps, I can climb them one at a time or two at a time or any combination thereof. In how many ways can I climb the n steps? I find these more realistic than the rabbits example, what is more they can be easily generalized (say, we can climb 1, 2 or 3 steps at a time). I find that students readily appreciate the advantages of recursive thinking!
Reply
Trey
16/4/2014 11:55:57 am
1,2,3,5,8,13,21,34
Reply
Trey
16/4/2014 01:14:04 pm
This result follows the fact that
Reply
Trey
17/4/2014 08:48:07 am
Suppose n=8.
Reply
Gerry Rising
3/8/2014 10:40:56 am
Clearly f(1) = 1 and f(2) = 2. Now consider f(3). The only patters you get are those you already displayed for f(1) and f(2) with a single vertical block to the right (or left). (It cannot serve as a horizontal block because it would have no partner.) Thus f(3) = f(1) + f(2). This same pattern continues so you have f(n) = f(n-1) + f(n-2), which is the Fibonacci generating equation.
Reply
Leave a Reply. |
Puzzle Ideas
If you have an idea for puzzle of the month, then please do let me know. Archives
September 2017
Don't forget to check out 'Teach Further Maths' - PowerPoints for Teachers and Students of A-Level Further Maths ...and the brilliant NEW educational card game 'Maths Trumps' |