Math Question - MIT Mathematics for Computer Science

[ProgrammingTheFuture]

Why couldn't I prove the hypothesis by simply putting one square in the center for Bill and the rest in the center? What am I missing ?




Essentially you have a courtyard which is 2^n by 2^n and n=2

You must fit L shaped tiles which are 2 by 2

Thm: For all n, there exists a way to tile a 2^n by 2^n region with a center square missing (for Bill).

Pf by induction: P( n ) -- For all n, there exists a way to tile a 2^n by 2^n region with a center square missing (for Bill).

Base Case: P( 0 ) -- one square for Bill --- True

Ind Step: ..Consider a 2^n+1 by 2^n+1 courtyard

I have no idea why I can't simply take the center piece if I can take the corner piece



The link is to a math question at:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-2-induction/ (starts at 59:00)

Thanks!

I am not sure where else to turn other than this forum !

 

[Geekwad]

The scale of his subsequent drawings in wonky, so it's doing a poor job visually representing the formula (math teachers are notoriously bad at drawing)

 

[Math Geek]

with bill being in the center of one of the 2^n squares, the rest of that square can be filled in with the L blocks. the remaining 2^n blocks however, still have an even area since they are not missing a block for bill (he is in the first square we considered). since the L blocks are 3 squares and 2^n is not divisible by 3, then the remaining squares can not be filled in using this logic.

remember this is exact logic here. we are assuming that each individual 2^n square can be filled with the L blocks and them not overlapping to bordering squares in this argument. this can't happen. true you could probably do it with overlapping the square borders with the L blocks but that is not the argument being made in the proof. hence why it does not work. plus bill is only in the middle of the single 2^n square and not the entire courtyard like we need.

by changing bill to a corner square, you can see how he was able to use a single L block to create a situation where each 2^n square was missing a single block so the rest of the argument works. now each 2^n is missing a block like we want/need to happen so we can then fill the odd numbered (2^n)-1 blocks with the L blocks