Nick Sabbe
ruud de rooijCombinatorics can be a bit weird sometimes: the number of ways to arrange N Tetris pieces into a 2-by-2N rectangle is the Nth Fibonacci number squared.
monument valley girl@ruuddotorg Interesting! Do you know of a proof of the formula? It doesn't seem obvious to me
Aditya Khanna@ruuddotorg @wehpudicabok no Ss and Zs or Ts?
robinhouston@adityakhanna You can't fit 'em in. Try it!
@robinhouston is that a chessboard coloring proof?
@adityakhanna I think it's simpler than that. If one of these shapes occupies a corner then the adjacent corner is isolated and cannot be filled.
Gadfly (-booq-)@wehpudicabok @ruuddotorg One thing that's pinging my intuition about this is, I know that the way to decompose a 1xN line of blocks into either 1x1 or 1x2 blocks,
is Fibn(n).
(That itself I think is... provable reasonably intuitively -- a 1xN can be either a 1x(N-1) and a 1x1 block, or a 1x(N-2) and a 1x2 block.)
And so this isn't a proof, but seeing this fact makes me want to look for a 1-to-1 equivalence between:
- a 2xN into tetrominos
and
- one 1xN into 1x1s and 1x2s on top
- one 1xN into 1x1s and 1x2s on bottom