# Korean Math Olympiad (Construct rectangle)

Prove that an $m$ × $n$ rectangle can be constructed using copies of the following shape if and only if $mn$ is a multiple of 8 where $m$ > 1 and $n$ > 1.

My solution: starting from 2 × 4 and 3 × 8 basic shapes, which can be constructed easily from the given L shape. This allows us to construct 3 × 8k shapes (k = 1, 2, 3...), adding 2 × 4 shapes, we can construct m × 8k shapes, where m is 3, 5, 7... In this case, n = 8k, so mn is a multiple of 8.

On the other hand, using 2 × 4 basic shape alone, we can construct 2j × 4k shapes, where mn is also a multiple of 8.

My question is, how can I prove these are the only shapes allowed, which is the "only if" part of the question.

Thanks!

• Base case: note that $4\mid m\cdot n$ since the shape has $4$ component square parts. Then you only need to prove that $8\nmid m\cdot n$ cannot be created by any combination of the basic shape... – abiessu Dec 10 '13 at 19:12

$4|mn$ so at least one of $m$ or $n$ must be even. Let's suppose $n=2k$. We color the grid with alternate black and white columns of length $m$. $n/2$ white columns and $n/2$ black columns. Now there are two kinds of L shaped objects, those covered 3 white squares, we call them type A, and those that covered 1 white square,we call them type B.
The total number of white squares is : $\frac{mn}{2}=3n_A+n_B$. And the total number of L shaped tiles is $\frac{mn}{4}=n_A+n_B$. Subtracting both sides of the two equations we will have $mn/4=2n_A$. So $mn=8n_A$