In how many ways can a 2xn grid be tiled using only 2x1 tiles, which can be laid either horizontally or vertically?
Design a way to enumerate those patterns.
The reason for the Fibonacci is that for a given n, you can take each tiling for n-2 and add = to each of them and then take each tiling for n-1 and add | to each of them.
Since there is 1 way to tile a 0xn and 1 way to tile a 1xn we have Fibonacci.
Years ago at a week-long conference on problem solving for math teachers. I was trying to tackle a problem similar to this one but much more difficult. Counting tilings of x tetrominoes in a nxm grid. It came down to a recursion but I couldn't show why.
After a couple of days the class shared where we were with our 'hard' problems. Later that day he had the whole class work on the problem here. When I solved it and could show the recursion I immediately realized how amazing the techer was! By the next day I had full formulas both recursive and explicit and I knew a lot more about how to teach problem solving to my own students.
|
|
Posted by Jer
on 2015-11-10 13:37:39 |
Solution and my story.
