Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 7 down vote accepted

$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

share|improve this answer
6  
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. –  Donkey_2009 Dec 10 '13 at 20:04
    
@Donkey_2009 Good point! Thanks. –  hhsaffar Dec 10 '13 at 20:11
    
Awesome solutions, thanks! –  Mathchoice Dec 10 '13 at 21:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.