0
$\begingroup$

How many ways are there of filling a 2xN board with tetris pieces. I stumbled upon a similar problem and this seemed interesting to solve.

This is my progress: Let S(n) be the number of ways of filling a 2xn board. Evidently, S(2)= 1 and S(4)=4. For n congruent to 2 mod 4, S(n)=2S(n-2)-1 as you can add 2x2 squares to any combination that fills a 2x4 board to either side but you have to subtract one as you would be counting twice to the one composed completely of 2x2 squares. I have been trying to determine S(n) for multiples of 4 but have been unsuccessful. I know I can fill it with ones that can fill 2x4 squares n times, but then for large numbers you can move the 2x2 squares around and these combinations make it hard to determine.

$\endgroup$
  • $\begingroup$ You can't fill a $2 \times 1$ board with Tetris pieces because they all have four squares. $\endgroup$ – Ross Millikan Apr 5 at 21:48
1
$\begingroup$

If I recall the Tetris pieces correctly, the only ones you can use here are the $2 \times 2$ square, the two $L$ pieces, one of each handedness and the straight. If you use an L or a straight you have to fill out a $2 \times 4$ rectangle with another of the same. Let $A(n)$ be the number of ways to fill a $2 \times n$ board. $A(n)$ is only defined for even $n$. You can fill a $2 \times n$ board by making a $2 \times (n-2)$ and appending a square or by making a $2 \times (n-4)$ and appending one of the two configurations of $L$ pieces or a pair of straights. The recurrence is then $$A(n)=A(n-2)+3A(n-4)$$ with starting conditions $$A(0)=1\\A(2)=1$$ The characteristic polynomial is $r^4=r^2+3$ with roots $r^2=\frac 12(1+\sqrt {13}),\frac 12(1-\sqrt {13})$ so the generic solution is $A(n)=a(\frac 12(1+\sqrt {13}))^{n/2}+b(\frac 12(1-\sqrt {13}))^{n/2}$ which give $a=\frac {1+2\sqrt{13}}4,b=\frac {3-2\sqrt{13}}4$ and the result is $$A(n)=\frac {1+2\sqrt{13}}4(\frac 12(1+\sqrt {13}))^{n/2}+\frac {3-2\sqrt{13}}4(\frac 12(1+\sqrt {13}))^{n/2}$$

$\endgroup$
  • $\begingroup$ How is A(0)=1 if it doesn't exist? Additionally, this does not work as A(6)=7. $\endgroup$ – GuauGuau754 Apr 5 at 21:59
  • $\begingroup$ Your edit still doesn't provide the correct answer for A(6) $\endgroup$ – GuauGuau754 Apr 5 at 22:04
  • $\begingroup$ Yes, $A(0)=1$ because there is one way to make a $2 \times 0$ rectangle-don't use any pieces. I had forgotten the straight piece, so the $2$ should be a $3$ as there are $3$ ways to make a $2 \times 4$ besides squares. I will update. $\endgroup$ – Ross Millikan Apr 5 at 22:05
  • $\begingroup$ can you explain how you went from the recursion to the polynomial? $\endgroup$ – GuauGuau754 Apr 5 at 22:24
  • $\begingroup$ It is the standard technique. You imagine a solution of the form r^n and plug it into the recursion. Each root of the polynomial gives a solution. In this case the polynomial is quadratic in $r^2$ because we are only concerned with even $n$. It would have been cleaner to solve the problem for $2 \times 2n$ rectangles. $\endgroup$ – Ross Millikan Apr 5 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.