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.

suppose you have a square like this(ignore the top black border) of lenght $2^n$ and hence area $4^n$

enter image description here

we have to prove by Principle of Mathematical Induction that we can fill this square (well, one small box is already filled!) by the below figure

enter image description here

share|improve this question
1  
What have you tried? –  Chris Eagle Oct 10 '12 at 13:12
    
You haven't said anything in general about where the filled-in square is. Always the fifth in the top row? Always on the top row somewhere? Or what? –  Chris Eagle Oct 10 '12 at 13:13
add comment

2 Answers

up vote 0 down vote accepted

It is a well-known and pretty tricky problem. Call $L_n$ the shape given by the removal of a $2^n\times 2^n$ square corner from a $2^{n+1}\times 2^{n+1}$ square; $Q_n$ a $2^n\times 2^n$ square. We can show that exists a $L_0$-tiling of $Q_n$ with a square removed (any square) in this way:

  • there exists a $L_0$-tiling of $L_1$, so there exists a $L_n$-tiling of $L_{n+1}$, so there exists a $L_0$-tiling of $L_n$;
  • $Q_{n+1}$ with a square removed can be decomposed into a $L_n$, a $L_{n-1}$, $\ldots$, a $L_1$ and a $L_0$.
share|improve this answer
add comment

Hint: can you see how to make a $2 \times 2$ square? Then can you make a replica of your piece, but twice as large?

share|improve this answer
add comment

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.