CPSC 513 Example Set 1

Assume that you have a square that measures 2ⁿ × 2ⁿ units (where n ≥ 1), and that this square has an arbitrarily-placed (other than that it must be aligned on the unit grid) 1 × 1 unit hole removed from it.

Example with n = 3 and the bottom-left corner of the hole at position (5, 4):


Prove that the remainder of the square can be precisely tiled (that is: no tiles overlap, every 1 × 1 unit square is covered and no tiles extend beyond the boundaries of the square) with 'L'-shaped tiles:

When attempting to come up with a proof of a proposition, one sometimes-helpful method is to first "talk over" the solution, and try to come up with something phrased informally. Then, when you are happy with the informal solution, tighten up the wording to something more precise and rigorous, making sure that you have closed any holes left open by the original phrasing. The point to mathematical rigor is just to make sure there are no holes in your proof!

When we discussed this problem in tutorial, it was proposed that one could "start with the smallest square" and show that it can be tiled, then to progress to the next smallest square, show that it can be tiled, and so forth. This is an excellent start to an inductive proof.

So, starting with the smallest legal square; that is, the 2¹ × 2¹ = 4 × 4 square, we can easily see that no matter which of the 4 possible units is removed, the remaining 3 can be covered with a single 'L'-shaped piece:



With an inductive proof, you will often find that the base case can be demonstrated by a simple exhaustion of all possibilities, which is the case here. If we approach this proof as an induction on the value of n, then we have proved that the base case (n = 1) holds.

It was next suggested that we could form the next larger square by "wrapping an 'L'-shaped piece around" one corner of the smaller square, then tiling the remainder, which can be visually seen to be possible:





While we never addressed this explicitly in tutorial, it needs to be recognized at this point that there are 4 different corners to the original square, and the above expansion can happen at any of those 4 corners, not just the lower-right corner. This is one of those potential "holes" than needs to be patched when you are turning your informal phrasing into a rigorous proof.


This is a good "first stab" at the inductive step of our proof, but we are not there yet. When proving a proposition by performing induction on the value of n, the inductive principle says that we must assume the proposition holds for n = k (for weak induction; strong induction allows us to assume the principle holds for all 1 ≤ n ≤ k), then prove the principle holds when n = k + 1.

The above demonstration holds for the first inductive step: we have assumed the proposition holds for n = 1, and used that to describe how it still holds for n = 1 + 1 = 2. Now we need to generalize that principle so that it holds for any k ≥ 1.

At this point in the tutorial, it was pointed out that we could generalize by substituting a 2^k × 2^k square in the above picture for the 2¹ × 2¹ square, and a 2^k+1 × 2^k+1 square for the 2² × 2² one. This gives us the generalized inductive step that we are looking for:



We have to be a bit careful here. While it was visually evident in the earlier k = 1 case that the remaining area could be precisely tiled, that is no longer so. However we do know that we can break this remaining area up into three squares of size 2^k × 2^k, that each of these three has one unit missing, and therefore that they can be precisely tiled. We may not be able to instantly "see" how to tile them, but logic tells us we must be able to do it!

In a complete proof, we start by re-stating the proposition which we wish to prove. This has 3 advantages: It forces us to re-read the question and ensure we are proving the right thing! It reduces the need for the reader to flip back and forth between the proposition and the proof, and makes it easier for them to verify that all our steps are correct. Most importantly, it gives us a chance to define and lock down the terms we wish to use, reducing vagueness, which is one of the biggest sources of holes.


Proposition:
Given a square measuring 2ⁿ × 2ⁿ units with an arbitrarily-placed (save for being aligned on the unit grid) 1 × 1 unit square removed, it is possible to precisely tile the remainder of the square using 3-unit² 'L'-shaped tiles.



Now for the proof itself. Is this an inductive proof? Then say so! To prevent confusion (both yours and the reader's), state the property on which you are performing the induction.


Proof (by induction on the value of n):



An inductive proof needs a base case.


Base case: n = 1


If n = 1, then the 2ⁿ × 2ⁿ square has in fact the dimensions 2 × 2.



It's always a bit of a judgement call as to when something becomes "obvious" and does not need to be described in any more detail. In this demonstration proof, I have erred on the side of caution below and gone into more detail than is strictly necessary. I could probably have just said something along the lines of "all 4 placement possibilities for the hole clearly uphold the proposition." Be a bit cautious when using words like "clearly" and "obviously," though — it is easy to gloss over holes without even realizing that they are there. When in doubt, it never hurts to go into more detail.


The hole must therefore be in one of the upper-left, upper-right, lower-left or lower-right corners. In any case, the remaining 3 units form an 'L'-shape that can be covered precisely with one tile, rotated as appropriate.



An inductive proof needs an inductive step.


Inductive step: n > 1



We are using weak induction. Write out the inductive hypothesis.


Assume that a square measuring 2^k × 2^k units (for any k > 1) with any one unit removed can be precisely tiled.



The inductive step can be thought of as a "mini-proof" inside the overall proof. So state that which we are trying to prove.


Then we require that a square measuring 2^k+1 × 2^k+1 units with any one unit removed can also be precisely tiled.



Now go for it! The "wrapping around" terminology used in the informal discussion above is a bit vague, so I am tightening it up as follows. It often helps to straighten your thoughts by appealing directly to the inductive hypothesis (sometimes more than once, as in this case). It is also often helpful (making it easier to be precise) to name the things you are discussing, so that you can unambiguously refer to them by that name, rather than a vague phrase or description.


Consider a square S having dimensions 2^k+1 × 2^k+1. S may be broken into four 2^k × 2^k quadrants (possible because of the assumed dimensions of S). The hole must occur in one of those four quadrants. By the inductive hypothesis, the rest of that quadrant where the hole occurs can be precisely tiled.

Also because of the inductive hypothesis, we may choose any one unit to remove from each of the three remaining quadrants, and precisely tile the rest.



Any time you claim that you will do X, you should include some justification as to why X is allowed.


As we are free to choose any unit we wish, let us remove in each quadrant that corner unit closest to the center of S.

Then the entirety of S is tiled save for the original hole and the 3 units just removed. But those three units are adjacent and in an 'L' shape, so can be precisely covered with one 'L'-shaped tile. Therefore all of S (save for the hole) can be precisely tiled.



Conclude by re-stating that which you wish to prove (and which you have now proved). That allows the reader to verify that you have indeed completed a correct proof.


So as required, a square measuring 2^k+1 × 2^k+1 units with any one unit removed can be precisely tiled.



Now for the best part! You get to put down the little Q.E.D. (Latin:  quod erat demonstrandum — "which was to be demonstrated") tombstone signifying that your proof is done.


□



Final thoughts: In addition to being an inductive proof, this style is often called a constructive proof. This is because we have shown that something (a precise 'L' tiling) exists by demonstrating a method to construct it. This proof not only demonstrates that the 'L' tiling for a 2n × 2n square exists, but it shows what one such tiling is (e.g.: the resulting tiling for the example square used at the top): Next week I want to look some more at ways that a proof can go wrong.