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

tagtext tagtext

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:

tagtext tagtext

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:

tagtext tagtext

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:

tagtext tagtext

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
5 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...