Is it possible to cover an $11 \times 12$ rectangle with $19$ rectangles of $1 \times 6$ or $1 \times 7$?

204 Views Asked by At

Is it possible to cover an $11 \times 12$ rectangle with $19$ rectangles of $1 \times 6$ or $1 \times 7$?

Attempt:

There should be $132$ unit squares to be covered. Since there are $19$ rectangles to be used, let $x$ be the number of $1 \times 6$ rectangles and $19-x$ be the number of $1 \times 7$ rectangles. The solution of $$ (19-x)7 + (x)6 = 132 $$ is $$ 133-7x + 6x = 132 \implies x = 1$$

So there should be only $1$ rectangle of $1 \times 6$, and $18$ rectangles of $1 \times 7$.

Now color the $132$ unit squares black and white like a chessboard, the top left is black..then its right is white...then its right is black again.. and so on.

Odd rows should be $$ [black]-[white]-[black]- ... -[black]-[white]-[black] $$ Even rows is should be $$ [white]-[black]-[white]- ... -[black]-[white]-[black] $$

For a $1 \times 6$ rectangle, it will definitely cover $3$ blacks and $3$ whites.

For a $1 \times 7$ rectangle, it will either cover $4$ blacks and $3$ whites, or cover $3$ blacks and $4$ whites. Let the number of $4$ blacks-$3$ whites coverings be $y$, and $18-y$ for the other one.

Notice that in total we must have $66$ blacks and $66$ whites. So in total there will be $$ |black \: squares| = 3 + 4y + 3(18-y) = 57 + y \implies y = 9$$ $$ |white \: squares| = 3 + 3y + 4(18-y) = 75 - y \implies y = 9$$

So there should be $9$ rectangles that cover $4$ blacks-$3$ whites, and $9$ rectangles that cover $3$ blacks- $4$ whites.

2

There are 2 best solutions below

4
On BEST ANSWER

$$\matrix{\color{red}1,0,0,0,0,0,0,\color{red}1,0,0,0,0\\0,\color{red}1,0,0,0,0,0,0,\color{red}1,0,0,0\\0,0,\color{red}1,0,0,0,0,0,0,\color{red}1,0,0\\0,0,0,\color{red}1,0,0,0,0,0,0,\color{red}1,0\\0,0,0,0,\color{red}1,0,0,0,0,0,0,\color{red}1\\0,0,0,0,0,\color{red}1,0,0,0,0,0,0\\0,0,0,0,0,0,\color{red}1,0,0,0,0,0\\\color{red}1,0,0,0,0,0,0,\color{red}1,0,0,0,0\\0,\color{red}1,0,0,0,0,0,0,\color{red}1,0,0,0\\0,0,\color{red}1,0,0,0,0,0,0,\color{red}1,0,0\\0,0,0,\color{red}1,0,0,0,0,0,0,\color{red}1,0} $$

We have $20$ red cells and $19$ rectangles. Each rectangle can cover at most $1$ red cell. So..

0
On

Same as @Aqua's answer but I made a pretty image:

enter image description here

No two rectangles can cover more than one red square, so you need at least $20$ rectangles to cover all red squares.