4
$\begingroup$

How many ways are there to cover a $2\times 16$ rectangle with $2\times 2,$ $2\times 3$ and $2\times 4$ rectangles?

I already dealt with a similar problem, which is how many ways are there to cut a $1\times 8$ rectangle into $1\times 1$ and $1\times 2$ rectangles. The answer to this problem can be calculated using the number of ways to divide $1\times k$ strip for $3\le k\le8$ sequentially, to arrive at $34$. However, this problem is completely different. How can I solve this problem?

$\endgroup$
  • $\begingroup$ Hint: find a recurrence relation to describe the scenario. Your expression for $a_n$, the amount of ways to cover a $2\times n$ rectangle using $2\times 2, 2\times 3,$ and $2\times 4$ rectangles will have something to do with $a_{n-2},a_{n-3}$ and $a_{n-4}$. $\endgroup$ – JMoravitz Jul 4 '17 at 14:19
  • $\begingroup$ $2x+3y+4z=16$ where $x,y,z \in N_0$ with constraints $x\leq 8, y\leq 5, z\leq 4$, $\endgroup$ – serg_1 Jul 4 '17 at 14:28
  • $\begingroup$ i notice that y<=5 , is it because we only can put four 2*3 rectangle , and two 2*2 rectangle which is equal to 2*4 rectangle . hence constraint for y is less than or equal to 5 ? . thanks for give me hint $\endgroup$ – Znik Dzulqarnain Jul 4 '17 at 14:42
  • $\begingroup$ @serg_1 that is incorrect. Your answer seems to assume that two coverings are considered "the same" so long as the amounts of each type of rectangle used are the same, but that is not how these problems are traditionally interpreted. I would consider for example the arrangement 4-4-2-2-4 to be different than the arrangement 2-4-4-4-2 because (among other things) the smaller rectangles are no longer adjacent. $\endgroup$ – JMoravitz Jul 4 '17 at 15:35
4
$\begingroup$

enter image description here

If you have a $2 \times n$ rectangle then call $a_n$ the number of ways to cover that rectangle with $2\times p$ ($p\in \{2,3,4\}$) rectangles.

If you start with $2\times 2$ then you will face the problem $a_{n-2}$, but if you start with $2\times 3$ you will find the problem $a_{n-3}$ and finally if you start with $2\times 4$ you will face $a_{n-4}$ then you have

$$a_{n}=a_{n-2}+a_{n-3}+a_{n-4}$$

and

$$a_2=1\\ a_3=1\\ a_4=2$$

and we also need define $a_1=0$.

now you can go forward and find $a_{16}$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You need to define $a_1$ as $0$ to use this recursion. $\endgroup$ – N. F. Taussig Jul 4 '17 at 15:04
  • $\begingroup$ @N.F.Taussig: You are right. Thanks. $\endgroup$ – Arnaldo Jul 4 '17 at 15:17
  • $\begingroup$ oww yea i realize you need to define a_1 , but thanks for an amazing explanation $\endgroup$ – Znik Dzulqarnain Jul 4 '17 at 15:39
  • $\begingroup$ @ZnikDzulqarnain: you are very welcome $\endgroup$ – Arnaldo Jul 4 '17 at 15:40
3
$\begingroup$

We are dealing with a $2 \times 16$ grid. The first column of two cells can be filled by a $2 \times 2$, a $2 \times 3$ or a $2 \times 4$ grid. Let us call $f(n)$ the number of ways to fill a $2 \times n$ grid. We then have:

$$f(n) = f(n-2) + f(n-3) + f(n-4), n \geq 4$$

We also know that:

$$f(0) = 1$$ $$f(1) = 0$$ $$f(2) = 1$$ $$f(3) = 1$$

A closed form is not straightforward, but we find:

$$f(4) = 2$$ $$f(5) = 2$$ $$f(6) = 4$$ $$f(7) = 5$$ $$f(8) = 8$$ $$f(9) = 11$$ $$f(10) = 17$$ $$f(11) = 24$$ $$f(12) = 36$$ $$f(13) = 52$$ $$f(14) = 77$$ $$f(15) = 112$$ $$f(16) = 165$$

| cite | improve this answer | |
$\endgroup$

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.