Waste less time on Facebook — follow Brilliant.

Elementary Techniques used in the IMO (International Mathematical Olympiad) - Invariants

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 \(5 \)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 \( m\times n \) 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 \( 2 \times 3 \) 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 \( X \) cover tile \( Y's \) "hole", then necessarily tile \( Y \) also cover the "hole" of tile \( X \). We have the following \( 2 \) pairs:



We have our first breakthrough for this problem: \( 12 \mid mn \). Consider a \( 2 \times 6 \) board. Clearly we cannot tile it with the pairs of tiles. However, we can obviously tile a \( 4 \times 6 \) board. We might now conjecture that we must have (WLOG) that \( 4 \mid m \).

Let us consider the case where they are both even but \( 4 \nmid m,n \). So we want to find a colouring that makes use of the divisibility by \( 4 \) condition. Well, the most direct way of incorporating it this is to add a \( 1 \) to each cell of the board that belongs to a column or row divisible by \( 4 \). 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 \( 1 \). (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 \( 1 \) by doing a simple case-bashing (I leave the reader to convince himself). So there must be an even number of tile \( \rightarrow \) \( 4 \mid m \) (WLOG).

Now, let us summarise what we have:

  • \( 12 \mid mn \)

  • \( 4 \mid m \)

  • \( m,n \neq 1,2,5 \) (do you see why?)

(i) So if \( 3 \mid n \) then we can clearly tile the whole board using the \( 3 \times 4 \) rectangles formed from the pair of hooks.

(ii) If \( 12 \mid m \) and by point \( 3 \), \( m \geq 6 \) then by a simple induction we can show that \( m \) can be represented in the form \( 3a + 4b \). 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 \( 3 \times 4 \) rectangles is more predictable than the second kind of pairing. Then all we do is that we split up the board into \( a \) strips of \( 3 \times m \) and \( b \) strips of \( 4 \times m \) which both can be tiled. □

Look forward to the next post, in roughly \( 1 \) and a half weeks time, for more on colouring!

Note by Anqi Li
2 years, 10 months ago

No vote yet
1 vote


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...