A $9\times 7$ rectangle is tiled with tiles of the two types: L-shaped tiles composed by three unit squares (can be rotated repeatedly with $90^\circ$) and square tiles composed by four unit squares. Let $n\ge 0$ be the number of the $2 \times 2 $ tiles which can be used in such a tiling. Find all the values of $n$.
Problem
Source:
Tags: geometry, rectangle, rotation, inequalities, combinatorics proposed, combinatorics
Bugi
20.06.2010 23:25
Color the rectangle in 4 colors like this:
121212121
343434343
...
121212121
We have 20 1's, 16 2's, 15 3's, 12 4's
Let $x,a,b,c,d$ be respectively number of: 2x2 tiles and L-tiles which don't contain a field with color 4,3,2,1. First, it's easily seen that $3\mid x$
Now, $x+a+b+c=20,x+a+b+d=16,x+a+c+d=15,x+b+c+d=12$
This means that $a+b+c+d=21-\frac{4x}{3}$
$d=21-\frac{4x}{3}-20+x=1-\frac{x}{3}$, so we see that $x\le 3$.
It's easy to construct examples for x=0 and x=3 (for x=3, put 2x2 next to each other in one row, starting from a corner for example)
Number1
21.06.2010 00:10
Let's color square $(i,j)$ with black iff $i\cdot j$ is odd. We get: B W B W B W B W B W W W W W W W W W B W B W B W B W B W W W W W W W W W B W B W B W B W B W W W W W W W W W B W B W B W B W B Then all $2\times 2$ tile covers $3n$ white squares and $n$ black squares. Let $a$ be the number of $L$ tiles that covers just white squares and $b$ wich covers $2$ white and $1$ black quare. Then we have: $ 3a+2b+3n = 43$ and $b+n =20$. We get $3a+n =3$, wich means $n=0$ or $n=3$. Here is example for $n=0$: a a b b o o p p r a c c b o n p r r d d c i n n s t t d e i i j m s s t e e g j j m m u u f g g h k l l u x f f h h k k l x x and here for $n=3$: a a b X X m m t t a b b X X m n t s c c d i i n n s s c d d i j j k Z Z e e g g j k k Z Z e f g h p p r Y Y f f h h p r r Y Y
Inequalities Master
22.06.2010 21:58
It's easy to see that $n$ must be divisible by $3$ and since $4n\le 63$, then $n\in \{0,3,6,9,12,15\}$.
For $n=0$, we can tile the table in the following way:
It's easy to see that we can replace the $4$ red-coloured L-shaped $2\times 1$ figures by $3$ squares $2\times 2$, so we can tile the table for $n=3$, too.
Suppose that $n\in \{6,9,12,15\}$ and let $m$ be the number of L-shaped $2\times 1$ figures.
If $n=6$, then $m=13$.
If $n=9$, then $m=9$.
If $n=12$, then $m=5$.
If $n=15$, then $m=1$.
Consider the following colouring of the table:
From it, we can see that any of the two figures can cover at most $1$ black square, so we need at least $20$ figures, i.e. $n+m\ge 20$. But all the cases considered, do not satisfy the inequality, so neither of $\{6,9,12,15\}$ work.
So $\boxed{n\in \{0,3\}}$
Oh, sorry, I see now that it's pretty much the same as Number1's solution.
NuncChaos
26.12.2010 02:36
A question: What aspect motivated you to color the board the way you did? The problem is mostly solved one you color it that way and think about it... but how did coloring the board the way y'all did pop into ur head?
MathLuis
31.01.2025 20:51
If we assign coordinates to the cells of the $9 \times 7$ so that buttom left is $(0,0)$ and top right is $(8,6)$ so that the corresponding coordinate goes up by $1$ when you move one step to the right or one step up then we paint Black (yeah!), all coordinates that have both numbers even, now let $u$ the number of L-triminos that don't touch any black cells and $v$ the number of L-triminos that touch exactly one black cell, if we had $n$ shapes of $2 \times 2$ squares on the grid filling then by counting the cells covered and black cells covered individually we get that $u+v=\frac{63-4n}{3}$ and $v=20-n$ then this gives that $u=1-\frac{n}{3}$ which means that $n=0,3$. To construct for $n=0$ focus on making some fliped L (with scale x2 of our L triminoes) whose only one side at the top touches the limit of the grid which is made from 4 L-triminoes containing the only one that does not go through any black cell, the rest must go through one, so using that information complete the filling greedily to win, and for $n=3$ simply replace the big L-trimino with 3 squares of $2 \times 2$ the rest of the filling is the same, thus we are done .