How many ways are there to form a 5 × 3 rectangle from squares of side lengths 1, 2 and 3 ?

Question

"How many ways are there to form a 5 × 3 rectangle from squares of side lengths 1, 2 and 3 ?"

Above is a question from SEAMO(South East Asian Math Olympiad). I tried to solve it but failed. I thought to make some combinations and thought of some kind of pattern. But couldn't. BTW this is a SEAMO 2020 Grade 5-6 problem. So please think of easy solutions like some kind of patterns, observations, etc.

ANS:

\begin{align} ANS = 28 \end{align}

Please Help.

Thanks in advance!!!

Answer 1

Let $ a_n$ be the number of ways to form a $ n \times 3$ rectangles using squares of length $1, 2, 3$.

Goal: Find a recurrence relation for $a_n$.

Hint: Starting from the right, consider the largest square that touches the right-most edge.

$a_n = a_{n-1} + 2a_{n-2} + a_{n-3}, a_0 = 1, a_1 = 1, a_2 = 3.$

Corollary: Determine $a_5$.

$a_5 = 28$.

Answer 2

If we take only first row with lenght 5 and generate all possible variants, that add up to 5, we get 13 distinct posibilities:

1. 1 1 1 2 | x3       5. 1 1 3 | x2       9. 2 1 2 | x1
2. 1 1 2 1 | x2       6. 1 3 1 | x1       10. 2 2 1 | x1
3. 1 2 1 1 | x2       7. 3 1 1 | x2       11. 2 3 | x1
4. 2 1 1 1 | x3       8. 1 2 2 | x1       12. 3 2 | x1       13. 1 1 1 1 1 | x8

each variant, then has it's number of possibilities which add up to 28.