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 55 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×n 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×3 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 X cover tile Ys Y's "hole", then necessarily tile Y Y also cover the "hole" of tile X X . We have the following 2 2 pairs:

tagtext tagtext

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

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

Now, let us summarise what we have:

  • 12mn 12 \mid mn

  • 4m 4 \mid m

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

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

(ii) If 12m 12 \mid m and by point 3 3 , m6 m \geq 6 then by a simple induction we can show that m m can be represented in the form 3a+4b 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×4 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 a strips of 3×m 3 \times m and b b strips of 4×m 4 \times m which both can be tiled. □


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

Note by Anqi Li
5 years, 8 months ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   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 </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...