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

For the sake of my reader, here are all the previous posts:

So this is the 8 8th and last post with the practice questions specially selected from the big pool of IMO problems for my reader. As such, it is advisable for the reader not to google for the solutions (which are readily available online) for reason of integrity and the fact that this is just a tiny test to see how well you have mastered the skills of finding an invariance. So do post your solutions in the comments \large \text{post your solutions in the comments} !

But firstly, the solution to the problem left to the reader in the previous post:

Consider a graph with mn mn vertices representing the markers. (This is motivated by considering adjacency graphs and the like) Intuitively, connect two vertices with an edge iff the markers are adjacent on the board. And as was mentioned in the post, label 1 -1 to each edge in the graph and also to each of the vertices which represent white markers. Now, we will also assign 1 1 to each of the vertices which represent black markers. I leave it to the reader to verify that the product of all the weights assigned (both vertices and edges included) is constant which we will denote as C \mathfrak{C} . Hint: Consider cases if the vertex representing the about-to-be-removed black marker is isolated and otherwise (if otherwise we can see why the edges also play an important role - they flip the signs).

Let us see what happens when we remove a marker. We remove the vertex representing it and also all the edges emanating from this vertex. Consider at the beginning of the procedure, it can be seen that there are (mn1)+[m(n1)+n(m1)] (mn-1) + [m(n-1) + n(m-1)] -1s on edges and vertices. The sum 3mnmn1 3mn-m-n-1 is odd, so C \mathfrak{C} is 1 -1 . Let us see why this leads to a contradiction. We would like a step which C=1 \mathfrak{C} = 1 , hmm, intuitively it would be generated if there were only 1 black marker left. But obviously we would need to reach such a state when we are removing the last marker. Therefore, we reach our desired contradiction. □

Problem set \LARGE \text{Problem set}

  1. Five identical empty buckets of 2 2 -liter capacity stand at the vertices of a regular pentagon. Next to the pentagon (this is in math world), there is a huge river of melted cheese. Jerry followed the smell of the cheese and entered math world. However, he forgot that Tom was following him secretly. Jerry and Tom then play the following game with Jerry trying to get as much cheese as possible: At the beginning of every round, Jerry takes one liter of cheese from the cheese river and distributes it randomly over the five buckets. Then Tom chooses a pair of neighbouring buckets, empties them to the river and puts them back. Then the next round begins. Obviously, Jerry's goal would be to make one of the bucket overflow. Tom's goal is to prevent this. Can Jerry ensure that a bucket would overflow?

  2. Let S S be a finite set of at least two points in the plane. Assume that no three points of S\mathcal S are collinear. A windmill is a process that starts with a line \ell going through a single point PS P \in \mathcal S The line rotates clockwise about the pivot P P until the first time that the line meets some other point belonging to S \mathcal S . This point, Q Q , takes over as the new pivot, and the line now rotates clockwise about Q Q , until it next meets a point of S \mathcal S . This process continues indefinitely. Show that we can choose a point P P in S \mathcal S and a line \ell going through P P such that the resulting windmill uses each point of S \mathcal S as a pivot infinitely many times.

  3. We write six nonnegative integers at the vertices of a regular hexagon with a sum of 20132013 2013^{2013} . Anqi is allowed to make moves of the following form: she will pick a certain vertex and replace that number with the absolute value of the difference between the numbers written at the two adjacent vertices. Prove that Anqi can make some moves, after which all the six vertices are 0 0 .

I still think that it is important for my readers to understand the motivation behind solving such problems, so I have included a Hints section. Please only click on the link if you have tried really hard and is desperate to stay on the right track. Also, do follow the rules as stated on the Hints page. Thank you.

A big thank you \Large \text{big thank you} to all my readers for following me through the huge and fantastic world of combinatorics (in particular, the invariance principle) and I hope you have learnt something :)

Note by Anqi Li
7 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×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}


Sort by:

Top Newest

Thanks for combining the posts at the start, as it makes them easier to find :)

The hints post is a great idea, since these problems do get into the hard range.

Calvin Lin Staff - 7 years, 5 months ago

Log in to reply

  1. Not really invariance, but I think this works. I spent a while proving things like that Tom can ensure the total amount of cheese is less than 1.51.5 after he empties two buckets. When I tried to finish the proof, I found that I didn't actually need that lemma, and did the following:

We claim that Jerry cannot cause a bucket to overflow.

Let b0b_0, b1b_1, b2b_2, b3b_3, and b4b_4 denote the buckets and the amount of cheese in each of the five buckets, depending on context, such that going around the pentagon, the buckets are in numerical order. Let a pair be two buckets bib_i and bi+2b_{i+2} such that bi+bi+2>1b_i+b_{i+2}>1, where indices are taken modulo 5. A pair is said to be broken if Tom empties one or more of the buckets in a pair.

Lemma: For Jerry to cause a bucket to overflow, there must have been an unbroken pair two rounds earlier, before Jerry adds a liter.

Proof: WLOG, b0b_0 overflows. It must have b0>1b_0>1 before Jerry adds a liter, and he can add the entire liter to this bucket. However, Tom knows this and he would empty this bucket. Then, another nonadjacent bucket, WLOG this is b2b_2, must have more than one liter of cheese. Two rounds previous, it must have been true that b0+b2>1b_0+b_2>1 before Jerry added a liter. \square

Tom knows this, and he would break the unbroken pair the round before. If there are multiple pairs, he might not be able to break all of them, and Jerry can cause one bucket to overflow.

Now, consider all the possible arrangements such that there are multiple pairs. If there are three buckets involved in the pairs, two must be adjacent, and Tom can break all pairs. If there are four buckets involved in the pairs, all four must be adjacent, and Tom can empty two other than the center two to break all pairs. Then, the only possible arrangement such that Jerry can keep an unbroken pair and cause a bucket to overflow is when all buckets are part of a pair after Jerry adds a liter, and every possible pair is a pair.

The previous round, before Jerry adds a liter, two buckets must be empty, and there must be no pair among the other three. WLOG, b3=b4=0b_3=b_4=0. Then, Jerry must add cheese such that b3+b0>1b_3+b_0>1 and b2+b4>1b_2+b_4>1. Adding, b0+b2+b3+b4>2b_0+b_2+b_3+b_4>2. However, since there was no pair, b0+b21b_0+b_2\le 1, and so b3+b4>1b_3+b_4>1, a contradiction, since Jerry only can add one liter. Hence, we conclude that Jerry cannot cause a bucket to overflow. \blacksquare

Daniel Chiu - 7 years, 5 months ago

Log in to reply

I have a three-four liner solution. It's basically almost the same idea as yours, but much streamlined. See whether you can find it. :)

Anqi Li - 7 years, 5 months ago

Log in to reply

Nope, have nothing!

Daniel Chiu - 7 years, 5 months ago

Log in to reply

Some work on #3:

Replacing the maximum number (choosing optimally) will always decrease the sum of all 6 numbers UNLESS there are 2 0's opposite each other and the other four numbers are the same. Now I just need to show that that position can be prevented from occurring.

Daniel Chiu - 7 years, 5 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...