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

This is continuation from Post 8. For readers who have read this, please do NOT post your solutions in the other post, instead post it in the comments below in THIS post. Thank you.

Hints \LARGE \text{Hints}

  1. Well, since we cannot spam this directly, consider working backwards. Clearly, Tom needs to ensure that the buckets have a1,,a51 a_1,\ldots,a_5\le 1 or else the bucket would overflow on Jerry's turn. Suppose then that Jerry adds w1,,w5 w_1,\ldots,w_5 to the buckets, where w1++w5=1 w_1+\cdots+w_5=1 . So if we think about it further, we can see that if there are 2 2 nonadjacent buckets (we are trying to make Jerry win now), Jerry wins if we have ai+wi>1 a_i + w_i > 1 and ai+2+wi+2>1 a_{i+2} + w_{i+2} > 1 . Tom needs to prevent Jerry from setting (wi,wi+2)=(1+ϵai,1+ϵai+2) (w_i,w_{i+2})=(1+\epsilon-a_i,1+\epsilon-a_{i+2}) , so all he does is to ensure that 2+2ϵaiai+2>1=w1++w5 2+2\epsilon-a_i-a_{i+2}>1=w_1+\cdots+w_5 for all ϵ>0ai+ai+21 \epsilon>0 \rightarrow a_i+a_{i+2}\le 1 . Now it is just your job to prove that these invariants hold at every step.

  2. There isn't a really detailed hint for this question. Remark first that: If we start with a point on the convex hull of S \mathcal{S} and a line \ell that is “tangent” to the convex hull then we will only iterate over the points from the convex hull. The key motivation behind the solution is the fact that in rotations there are some really important angles such as π,π2 \pi, \frac{\pi}{2} . Also think, if we draw a line \ell , then the plane is split into two sections and there is one point only on \ell , how do we know that we can iterate? Maybe we can see what happens if we swap the two sections? Do you see the invariance?

  3. Clearly we need to construct a monovariant. Think: Is 20132013 2013^{2013} purposely there to put you off? Try some small cases. It becomes apparent that we need an alternating odd even structure. Prove that this is possible. Try casework if everything else fails. We need a monovariance that looks something like: max{a,b,c}g(a,b,c) max\{ a,b,c \} - g(a,b,c) Here we define g(a,b,c)=# of a,b,c that are equal to max{a,b,c} g(a,b,c) = \text{\# of} \space a,b,c \space \text{that are equal to} \space \max \{ a,b,c \} . The alternating structure suggests strongly to use 3max{a,b,c}g(a,b,c) 3 max\{ a,b,c \} - g(a,b,c) . Use induction to prove that this invariance holds a every step.

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}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...