7
$\begingroup$

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.

enter image description here

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!

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – abiessu Dec 10 '13 at 19:12
7
$\begingroup$

$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$

(The position of the blue tiles in the image below is just illustrative)

enter image description here

$\endgroup$
  • 6
    $\begingroup$ I think it simplifies things just to point out that the number of white squares covered by each tile is odd; since there are an even number of such squares, there must be an even number of tiles. Nice method, though: +1. $\endgroup$ – John Gowers Dec 10 '13 at 20:04
  • $\begingroup$ @Donkey_2009 Good point! Thanks. $\endgroup$ – hhsaffar Dec 10 '13 at 20:11
  • $\begingroup$ Awesome solutions, thanks! $\endgroup$ – Mathchoice Dec 10 '13 at 21:59

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.