You have a block with a width of 3, depth of 3 and a height n
Given n, in how many ways can you fill this block with smaller blocks of 2 x 1 x 1?
if n is uneven, one 1x1x1 block will be unused. This is allowed.
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Are you sure it is research level? What methods have you tried before? Are there any numerical results for small $n$? $\endgroup$– Daniel SoltészOct 13, 2013 at 16:34
-
$\begingroup$ This is an instance of the dimer problem, which has a large literature. $\endgroup$– Chris GodsilOct 13, 2013 at 17:29
-
$\begingroup$ I was indeed not sure if this was research level, but no one on math.stackexchange could solve it, so i went a little higher. Yes there is a reason for the size. This is actually a part of a larger question. A 2x1x1 block represents 2 twin brothers, and the big block represents a building. In how many ways can twins be placed in adjacent rooms in this building. Thanks, i will look up the dimer problem. $\endgroup$– Emiel SteernemanOct 13, 2013 at 17:38
-
3$\begingroup$ This is a Project Euler question, projecteuler.net/problem=324. $\endgroup$– Zack WolskeOct 13, 2013 at 18:42
-
1$\begingroup$ This question appears to be off-topic because it is about a Project Euler question. $\endgroup$– Daniel MoskovichOct 13, 2013 at 23:47
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
For simplicity, I'll assume $n$ is even. Each horizontal slice of the $3 \times 3 \times n$ block can have a finite number of "states". Each state consists of a packing of the $3 \times 3$ square with $2 \times 1$ blocks (in either orientation) and $1 \times 1$ blocks, where the $1 \times 1$ blocks are labelled either ``$+$ or $-$''. The lowest slice is not allowed to have any $-$, the highest slice is not allowed any $+$, and each $+$ must be paired with a $-$ in the next higher level. If there are $N$ states $1 \ldots N$, let $A$ be the adjacency matrix: $A_{ij} = 1$ if state $i$ in one level is compatible with state $j$ in the next level, $0$ otherwise. Let $L$ and $H$ be the column vectors of $0$'s and $1$'s indicating states that are possible in the lowest and highest levels respectively. Then the number of ways is $L^T A^{n-2} H$. The eigenvectors and eigenvalues of $A$ can be used to compute this.
answered Oct 13, 2013 at 18:25