I know this is much for a day, but I will be going overseas tomorrow for a long time, so I thought that It be best for me to post all the instalments and that my reader can pace himself/herself when reading through these posts.
This is the th instalment, following the 4th.
At the request of Priyansh Sangule, we will do some colouring proofs today.
Example 4: (IMO 2004) Define a hook to be a figure made up of 6 unit squares as shown in the diagram
or any of the tiles by applying rotations and reflections to the diagram. Determine all rectangles that can covered be hooks such that:
the rectangle is covered with hooks and no overlaps
no part of the hook covers an area outside the rectangle.
Solution: Yet again, do not fret that we are about to attempt a considerably recent IMO problem.
We hate hooks because they are in a way disjoint. We like tiles that are nice rectangles or things of the sort. So it is pretty motivated to consider pairs of hooks due to the hole, as marked out (with a black dot) in the following diagram:
So necessarily if tile cover tile "hole", then necessarily tile also cover the "hole" of tile . We have the following pairs:
We have our first breakthrough for this problem: . Consider a board. Clearly we cannot tile it with the pairs of tiles. However, we can obviously tile a board. We might now conjecture that we must have (WLOG) that .
Let us consider the case where they are both even but . So we want to find a colouring that makes use of the divisibility by condition. Well, the most direct way of incorporating it this is to add a to each cell of the board that belongs to a column or row divisible by . Basically what we want to do next can then be simplified to proving that each of the pairs of hook only cover an odd number of . (Do you see why this is sufficient?). Anyways, here's the board with the labelling:
So each pair of hook clearly can only cover an odd number of by doing a simple case-bashing (I leave the reader to convince himself). So there must be an even number of tile (WLOG).
Now, let us summarise what we have:
(do you see why?)
(i) So if then we can clearly tile the whole board using the rectangles formed from the pair of hooks.
(ii) If and by point , then by a simple induction we can show that can be represented in the form . The motivation behind this step is that we want to be able to split up the board into smaller sections of case (i) above, because intuitively the rectangles is more predictable than the second kind of pairing. Then all we do is that we split up the board into strips of and strips of which both can be tiled. □
Look forward to the next post, in roughly and a half weeks time, for more on colouring!