IMO 2020 was an interesting one because it was completely virtual due to Covid-19. Personally, I would feel disappointed if I were a contestant because I would have loved to use this as an opportunity to visit Russia, which would have been a costly trip on its own.

The problems can be found on the imo-official website.

I tried the problems and this is the write up for my attempts and motivations.

# Day 1: Problem 1.

The symmetry of the problem suggests that we can just focus on one half and see if the intersection of the perpendicular bisector and the internal bisector of $ \angle ADP $ is some special point.

The ratio 1:2:3 was begging for some special points to be drawn. Trying a point X on AD such that $$ \angle XPA = \angle PAD = \alpha $$ reveals that XPD is an isosceles triangle, and that X is on the circumcircle of ABP. Hence, the angle bisector of ADP is actually the perpendicular bisector of XDP and meets the perpendicular bisector of ABP at the circumcenter. The same argument can be applied for the other equation.

I felt so good that I could still solve IMO Q1 after a decade.

# Day 1: Problem 2

$ a + 2b + 3c + 4d $ first hinted to me that some form of weighted AM-GM is worth trying. To get the inequality direction, I’m looking for some GM on the LHS. $ a^a b^b c^c d^d $ looks promising.

Rewriting that as the geometric mean of $ (a + b + c + d) $ terms: $$ a.a… a.b.b…b.c.c…c.d.d…d $$ and applying weighted AMGM, we get that to be less than $$ ((a^2 + b^2 + c^2 + d^2)/(a+b+c+d))^{1/(a+b+c+d)} = a^2 + b^2 + c^2 + d^2 $$

I got stuck here as I wasn’t sure if the bound was too loose and gave up. After a day, I decided to look up the solution and saw that I was just too afraid to get my hands dirty and expand out all the terms!

To complete the proof and the motivation for it, we can write the RHS as $ (a+b+c+d)^3 $ which has $ 4^3 = 64 $ terms, and notice that the LHS has 40 terms. Eliminating common terms is then a tractable solution requiring manipulation of up to 24 terms. In fact, if we do it lazily with a greedy algorithm for matching, we can arrive at the solution pretty quickly.

For example, the terms with $ a^2 $ on the RHS are $ a^2 \cdot 3(b+c+d) $ , and the LHS is $ a^2 \cdot (2b + 3c + 4d) $. We can use the original condition to prove this local inequality. This can be applied similarly for $ b^2 $, $ c^2 $, $ d^2 $.

At this point, we’ve accounted for all 40 terms on the left, and have shown them to be smaller than 40 of the terms on the right. So the remaining 24 terms on the RHS are definitely > 0

# Day 1: Problem 3

I considered induction first. From 4 pebbles of 1 colour to 8 pebbles of 2 colours. and it seemed plausible that in each group of 4, as long as the smallest and largest are in the same pile, it will work out. So perhaps we need an algorithm such that preserves the sum of the column in response to swapping two pebbles.

For example in the following starting set up, if we swap 7 and 2, we don’t need to do anything since the sum of the columns are the same. If we swap 7 and 1, then we can restore balance by swapping the columns in color 1.

A | B | Colour |
---|---|---|

1 | 2 | 1 |

4 | 3 | 1 |

5 | 6 | 2 |

8 | 7 | 2 |

Of course such a naive solution doesn’t work for a Q3 at the IMO level. At 3 colours, the swapping is no longer localized to the colours of the swapped pebbles. That is, if I swapped pebbles of colour 1 and 3, I might need to swap the columns of colour 2 to balance out.

I gave up after a while.

Looking at the solution later, it turns out it’s a pretty nice graph theory question in disguise! We can encode the initial state as n nodes to represent the n colours, and for each pair of numbers adding to $ \frac{4n+1}{2} $ (the average), we draw an edge joining the two nodes. The edges can form loops for the node. Note that we now have 2n directed edges.

Since each node has in degree and out degree of 2, we know that there must be an Eulerian circuit for the connected graphs.

If we color the edges in the circuit in alternate colors, say red and blue, and consider the directed half-edges (for a lack of terminology) connected to it, then we know that each node will have two red half-edges and two blue half-edges. An incoming red half-edge must have a corresponding outgoing blue half-edge.

If we collect all the red edges, and have the numbers be in the same pile, there will be exactly n edges. Since each pile has n edges and the “value” of edges are the same, each pile will sum to the same sum. Now looking at each node, since there are exactly 2 red and 2 blue half edges, each colour appears exactly twice in each pile.

# Day 2: Problem 1

The idea of posets and chains jumped at me because of the condition that a cable car that starts higher must end higher. The A and B represents colouring of the links of the chain. The dual of the problem posed is what is the maximum coloured links we can add to $ n^2 $ nodes such that we still satisfy the condition.

Exploring the idea a bit more, if we have $ k $ chains for company A, then, we’d expect there to be $ n^2 - k $ links. Because all nodes except the $ k $ starting node of the chains will be linked.

Company B must be the anti chains, similarly, $ k $ anti chains means there will be $ n^2 -k $ links. Due to the symmetry, it makes sense for it to be symmetrical. So let’s try a square with the most naive construct a grid. ie, $ k = n $

Turns out this works nicely! To prove that this is the maximum, add one more link. This causes the number of chains for A to decrease by 1, and by pigeon hole principle the minimal number of anti chain must be more than $ n $. This violates the condition for company B which needs to also have $ n - 1 $ anti chains.

# The rest

I ran out of stamina to attempt the rest. Maybe I’ll try it some other day.

A discussion of the solutions can be found on the AoPS forum.