1
$\begingroup$

Source: MIT OCW 6.042 by Tom Leighton, Lecture 2; Please skip to time 1:00:45.

In this question, the professor proves:

$2^n.2^n$ courtyard can be filled with tiles of L shaped (composed of 3 unit square tiles) having a free unit square tile free for Bill at the center is true for all $n \in N$

Failing to do so, he changes the technique to:

$2^n.2^n$ courtyard can be filled with tiles of L shaped (composed of 3 unit square tiles) having a free unit square tile free for Bill at the corner is true for all $n \in N$

But this technique cannot be extended to prove the initial proposition. So he takes a stronger technique:

$2^n.2^n$ courtyard can be filled with tiles of L shaped (composed of 3 unit square tiles) having a free unit square tile free for Bill at any position is true for all $n \in N$


I understand the idea behind taking stronger technique, and also understand the proof. I don't understand one thing.

I know that when you prove some proposition true you have to prove it for all cases. But in the above proof he fixed the positions of three blank squares, and only one is free. Like here blue, green and yellow are fixed and only red can be anywhere.

The total possibilities for four $4.4$ courtyards having one unit square missing, arranged in a big square of $8.8$ courtyard: $2^4.2^4.2^4.2^4 = 2^{16}$ possible layouts.

But the above proof fixes three squares so it becomes; $2^4+2^4+2^4+2^4 = 4.2^4 = 2^6$.

I'm thinking that proof like this and with this perspective it seems an incorrect proof to me. I know the proof is right, my approach is wrong, please tell me how does it work for every possibility, for example this.

$\endgroup$

2 Answers 2

1
$\begingroup$

Your question actually shows that you do not understand induction. I very strongly advise you to learn basic first-order logic, because that is the only way to truly understand induction. However, in the interim you should read this on induction and this on game semantics.

Once you fully understand those two posts, it should be clear what you have here:

Given any $2^n×2^n$ square grid with a missing unit square:
  If $n = 0$, then it is trivially tileable. So we are left with the case $n>0$.
  Thus the missing square is in one of the $4$ equal parts each of size $2^{n-1}×2^{n-1}$.
  We can remove $3$ appropriate centre squares so that each part has exactly one missing square.
  Note that those $3$ centre squares can be covered by an L-tile.
If each of those $4$ parts can be L-tiled, then the whole grid can be L-tiled.
Therefore by induction the whole grid can be tiled.

Furthermore, the professor is incorrect that the corner version of the theorem cannot be used to prove the original proposition! Suppose you have proven the corner version. Then any square grid with size at least $2×2$ and all centre squares removed can be L-tiled (since each of the 4 parts can be L-tiled, by the corner version), and hence any square grid with size at least $2×2$ and one centre square removed can also be L-tiled.

$\endgroup$
11
  • $\begingroup$ Thanks for providing your previous posts, they are high level stuff for me. I understood a lot of it, but cannot say full of it. I'll read it again after more practice with induction. And yeah the professor said he cannot rotate the $2^n.2^n$ grid because there could be a piece such that it has two unit-squares in this grid and one in another, but it's not the case as our grids are complete themselves, thanks for verifying it too. Also please comment on my possibility deduction. Is it any logical? (Total $2^{16}$ ways and the approach in the video covers only $2^6$ possibilities thingy) $\endgroup$ Apr 11, 2020 at 8:12
  • $\begingroup$ @RisingUnderDog: As I said, if you really want to understand induction you have no choice but to learn first-order logic. I did not respond to your other remarks because they are based on a faulty understanding of induction. Think slowly about induction the way I presented it in the other post. You break down an arbitrary given grid into smaller grids, and if each smaller grid can be L-tiled then the original grid can as well. This means that you have reduced the original problem to smaller problems. Each smaller problem in turn can be reduced in the same manner. $\endgroup$
    – user21820
    Apr 11, 2020 at 8:38
  • $\begingroup$ This reduction process is the correct way you should understand induction in the meantime before you learn basic first-order logic, as an interim way to get a simple but accurate grasp of induction. The reduction process eventually ends up with many tiny problems each with size $1×1$, which is the so-called base case here. The fact that it must eventually end up with only base cases is precisely the core of induction. $\endgroup$
    – user21820
    Apr 11, 2020 at 8:41
  • $\begingroup$ @RisingUnderDog: So your first step right now should be to understand the reduction process as explained in my post to the point that you are certain that the claim (every square grid of size $2^n×2^n$ can be L-tiled) is true for every natural $n$. Don't care about "induction". Just focus on the reasoning that shows that, no matter what grid you give me, I can follow the reduction process all the way to obtain an L-tiling. Once you fully get that, then let me know again and I will explain exactly what induction is doing to validate that reasoning. $\endgroup$
    – user21820
    Apr 11, 2020 at 8:51
  • $\begingroup$ Starting at about 1:12:15 the professor does realize that the 'corner' version of the proof is sufficient to then also prove the 'center' version. $\endgroup$
    – Bram28
    Apr 11, 2020 at 14:16
0
$\begingroup$

Start with a $2^{n+1}\times 2^{n+1}$ courtyard with any unit square missing. Scale the courtyard down by a factor of $\frac 12$. Now you have a $2^{n}\times 2^{n}$ courtyard with some unit square having a defect in form of a half-unit square missing. By induction hypothesis, this $2^n\times 2^n$ courtyard can be tiled by L shapes leaving the defective unit square free. Now scale by a factor of $2$ back to the original situation. Replace the now big L shapes by four L shapes each. The defective square was scaled up to a $2\times 2$ square with the original missing unit square in one of its corners. This can be covered by a single L shape.

$\endgroup$
2
  • $\begingroup$ Thankyou I understand it now this way. Just one thing it will become one-fourth of a unit square, not half-unit square. Please also see my possibility deduction, total $2^{16}$ and the approach in the video covers $2^6$ possibilities only, please comment on that too $\endgroup$ Apr 11, 2020 at 7:49
  • $\begingroup$ @RisingUnderDog With "half-unit square" I meant a square with side length half a unit. But, yes, by area it is one-fourth. - Re your other objection (Is till didn't watch the video): You miscount. As in my version but in a different, he starts with any arbitrary missing and reduces this to some specific place missing. That doesn't prevent application of the induction hypothesis that it can be done with any place missing $\endgroup$ Apr 11, 2020 at 8:16

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.