On 28/01/2017 00:27, Tom Duff wrote:

The warmup to 538's weekly math puzzle asks how many ways Tetris pieces (tetrominos) can fill a 2x10 rectangle. ... It's easy for my program to do other sized rectangles. For 2-by rectangles I get: ... The second column looks like the squares of the Fibonacci numbers. Is there an easy proof?

The first "obvious" thought is: perhaps it turns out that there are F_n configurations of a 1x(2n) rectangle such that the tetromino tilings of a 2x(2n) rectangle are exactly the things you get by putting one on top of the other. That seems like it would be a bit too convenient, and indeed it isn't true. It seems like the options for constructing these things are rather few: they have to be built out of the following components. - 2x2 block (width 2) - Two 1x4 blocks on top of one another (width 4) - Two L-pieces with zero or more 1x4 blocks between, offset by 2 each time (width 4,6,8,...; can go either way up) Let's see, that means a(n) = a(n-1) + a(n-2) + 2[a(n-2)+a(n-3)+...] where n is half the width, and that's got to be easy to solve (start by subtracting two versions of that offset by one and you have a finite-order recurrence, and then everything is routine) and I bet it gives the squared Fibonaccis. That's an easy proof (or will be once the details are filled in) but doesn't provide much actual insight. But maybe there's a way to use that rather restrictive set of structures to see that the answer "must" be fib^2? -- g