Skip to main content

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved!

To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal

These solutions were actually found by Atul, Pranjal, and Abhay during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!!



Okie Dokie, I think we should get started with the problems! Enjoy!

Problem 1: Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and $BQ = BC = CP$. Let $T$ be the circumcenter of triangle $APQ$, $H$ the orthocenter of triangle $ABC$, and $S$ the point of intersection of the lines $BQ$ and $CP$. Prove that $T$, $H$, and $S$ are collinear.

Motivation: A natural way to involve $T$ would be if it lies on some circle, and with a bit of angle chase, we see that it lies on $(PSQ)$, and then it suffices to show that $H$ is on the angle bisector of $BSC$. But then from the definition of $P,Q$ and trying to relate $H$ to them, we see that they're just reflections of vertices across the altitudes, and from there it's easy to finish. 

Solution: First, since $$\angle PSQ = 180 - \angle QBC - \angle PCB$$

$$ = 180 - (180 - 2C) - (180 - 2B) = 2(B+C)-180 = 180 - 2A = 180 - \angle PTQ$$ so $PTQS$ is cyclic and since $TP = TQ$, $ST$ is the angle bisector of $\angle PSQ$.

But also, since $BQ, CP$ are just reflections of $BC$ across $BH, CH$, we have that $H$ is the incenter of $\angle SBC$ and hence $H$ lies on the angle bisector of $\angle PSQ$ too. So $T,S,H$ are collinear, as desired. $\blacksquare$

Review:  My favourite from the test. I've always been a fan of when you have to notice that a particular point is a triangle centre by using the fact that it lies on two lines and then using the fact that it lies on the third. In this question, the key idea that S is incentre is exactly of this motif 

Problem 2: Let $\mathbb{N}=\{1, 2, 3, \dots\}$ be the set of all positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for any positive integers $a$ and $b$, the following two conditions hold:

(1) $f(ab) = f(a)f(b)$, and

(2) at least two of the numbers $f(a)$, $f(b)$, and $f(a+b)$ are equal.

Motivation: Since $f$ is multiplicative, it is essentially just defined on primes. Intuitively, if there are too many primes with $> 1$ values, then it seems hard to have two of $f(a), f(b), f(a+b)$ to be equal always, since we see having one or no bad primes is fine, we assume these are the only solutions. Taking the two smallest primes is motivated since otherwise its hard to deal with many bad primes dividing stuff, so if we look at small values, then only $p,q$ are going to divide them, making it more manageable.

Solution: First, taking $a = b = 1$, we see that $f(1) = 1$. Call a prime $p$ bad if $f(p) > 1$. If there are no bad primes, then $f(x) = 1$, which works, if there is one bad prime, then $f(x) = c^{v_p(x)}$, which can be checked to work too, so suppose there are at least $2$ bad primes, say $p$ and $q$ are the two smallest, wlog $q > p$

Taking $a = p, b = q-p$ in the second condition, we see that two of $f(p), f(q), f(q-p)$ must be equal, but $q-p < q$ and not divisible by $p$, so $f(q-p) = 1$, so we must have $$f(p) = f(q),$$ say its equal to $c$.

If $q > p^2$, then taking $p,q^2 - p$, we get two of $f(p), f(q - p^2), f(q^2)$ are equal, not possible since $$f(q-p^2) = 1, f(p) = c, f(q^2) = c^2.$$ Let $t$ be a positive integer such that $q > p^2 - qt > 0$, so taking $qt, p^2 - qt$, we have two of $f(qt), f(p^2 - qt), f(p^2)$ are equal, again impossible since they're equal to $c, 1, c^2$ respectively, so we're done. $\blacksquare$

Review: A non-standard FE. I thought this seemed a bit difficult for its position, but I'm told there are easier solutions

Problem 3: An infinite sequence of positive integers $a_1, a_2, \dots$ is called $good$ if

(1) $a_1$ is a perfect square, and

(2) for any integer $n \ge 2$, $a_n$ is the smallest positive integer such that$$na_1 + (n-1)a_2 + \dots + 2a_{n-1} + a_n$$is a perfect square.

Prove that for any good sequence $a_1, a_2, \dots$, there exists a positive integer $k$ such that $a_n=a_k$ for all integers $n \ge k$.

Motivation: Letting $b_i = na_1 + \cdots + a_n$, its natural to look at $b_i - b_{i-1}$, which is just $a_1 + a_2 + \cdots + a_n$, which can again be written as difference of some previous terms, so we can essentially throw away the $a_i$ and deal only in the $b_i$, since they're squares, let $d_i = \sqrt{b_i}$. Since we want to show $a_i$ is eventually constant, we can check that its equivalent to showing that $b_i$ is the square of a linear polynomial, so we just want $d_i$ to be eventually linear, and the rest is just checking details work out.

Solution: Let $$d_n = \sqrt{na_1 + (n-1)a_2 + \cdots + a_n},$$ the problem says $$d_{n}^2 - d_{n-1}^2 = a_1 + a_2 + \cdots + a_{n} = a_{n} + d_{n-1}^2 - d_{n-2}^2$$, so $d_n$ is defined as the smallest number greater than $d_{n-1}$ such that $$d_n^2 > 2d_{n-1}^2 - d_{n-2}^2$$

Note that by AM-GM, taking $$d_{n+1} = 2d_n - d_{n-1}$$ satisfies the inequality and hence we have $d_{n+1} \le 2d_n - d_{n-1}$ always, or $$d_{n+1} - d_n \le d_{n} - d_{n-1}$$this implies that the sequence $d_{n+1} - d_n$ is nonincreasing and so must stabilize at some value, say $m$. Then substituting this back, we obtain that sufficiently large $a_i$ are forced to be just $2m^2$, so we're done. $\blacksquare$

Review: One of my least favourite problems from the test. There does not seem to be an elegant olympiad-Esque main idea as such and the solution feels more like long details than an elegant idea.

Problem 4: Given a positive integer $n \ge 2$, determine the largest positive integer $N$ for which there exist $N+1$ real numbers $a_0, a_1, \dots, a_N$ such that

$(1) \ $ $a_0+a_1 = -\frac{1}{n},$ and

$(2) \ $ $(a_k+a_{k-1})(a_k+a_{k+1})=a_{k-1}-a_{k+1}$ for $1 \le k \le N-1$.

Motivation: Seeing the abundance of terms of the form $a_i + a_{i+1}$ motivates defining the $b_i$ sequence, after which the problem solves itself.

Solution: Let $b_i = \frac{1}{a_{i-1} + a_i}$ whenever defined, so $b_1 = -n$ and the recursion rewrites as $b_{i+1} = b_i + 1$ and this can go on until we reach $b_n = -1$ and then we can't have $b_{n+1} = 0$ since this would cause $a_i$ to not be defined, conversely, we can recreate the $a_i$ from the $b_i$ by picking $a_0$ arbitarily and then recursively pick the $a_i$, so since the sequence goes on to at most $n$ terms, we have $N = n$. $\blacksquare$.

Review: Again, not a problem I was a big fan of. The statement seems kind of contrived. It seems built to have only one solution


Problem 5: For all positive integers $n$, $k$, let $f(n, 2k)$ be the number of ways an $n \times 2k$ board can be fully covered by $nk$ dominoes of size $2 \times 1$. (For example, $f(2, 2)=2$ and $f(3, 2)=3$.) Find all positive integers $n$ such that for every positive integer $k$, the number $f(n, 2k)$ is odd.

Motivation: Since we're only looking at the number of ways $\pmod 2$, we are motivated to consider pairing up stuff, so we try and exploit any symmetry possible, which gives us the $n \rightarrow \frac{n-1}{2}$ observation. To deal with even $n$, since we want symmetry, we pick the board to be a square, when we can use the diagonal as symmetry.

Solution: The answer is all $\boxed{n = 2^m - 1}.$ To see this, observe the following:

If $n$ is even, say $n = 2s$, then taking $k = s$ makes it fail since in a square board, we can pair any tiling of dominoes with its reflection across the diagonal and since there are no "symmetric" tilings, $f(2m, 2m)$ is even.

If $n$ odd works, then so does $\frac{n-1}{2}$. Once again, say $n = 2s+1$ and consider reflecting the tiling across the $s+1$st row. Since this generates an even number of things, we must have an odd number of "symmetric" tilings, but all of these must have the $s+1$st row having dominoes horizontally, which splits the board into two $s \times 2k$ boards so we must have that $s$ works too if $2s+1$ does. 

So from any number that works, we can repeatedly do $n \rightarrow \frac{n-1}{2}$, since we can't end up with an even number, it must end at $1$, so retracing out path, going from $n \rightarrow 2n+1$, we see that the only $n$ that work are $n$ of the form $\boxed{2^m - 1}$, as claimed. $\blacksquare$.

Review: EGMO continues its domino trend. I liked the problem. The solution idea is somewhat standard but still slick.

Problem 6: Let $ABCD$ be a cyclic quadrilateral with circumcenter $O$. Let the internal angle bisectors at $A$ and $B$ meet at $X$, the internal angle bisectors at $B$ and $C$ meet at $Y$, the internal angle bisectors at $C$ and $D$ meet at $Z$, and the internal angle bisectors at $D$ and $A$ meet at $W$. Further, let $AC$ and $BD$ meet at $P$. Suppose that the points $X$, $Y$, $Z$, $W$, $O$, and $P$ are distinct.

Prove that $O$, $X$, $Y$ $Z$, $W$ lie on the same circle if and only if $P$, $X$, $Y$, $Z$, and $W$ lie on the same circle.

Motivation: Since we see a bunch of angle bisectors, we are motivated to add in $K,L$ to create incenters and excenters. Then, angle chasing gives us the cyclic quadrilaterals.

The main step of the solution is really motivated by miquel inversion and the fact that $\Phi_1, \Phi_2$ both fix $(WXYZ)$ due to the cyclic quadrilaterals and that $P,O$ swap under miquel invert.

Solution:  First, since $$\angle XYZ = 180 - \frac{B+C}{2} = \frac{C+D}{2} = 180 - \angle XWZ$$ so $XYZW$ is cyclic.

Let $K = AD \cap BC$ and $L = AB \cap CD$ and $M$ be the miquel point of $ABCD$.  Note that $X$ is the incenter of $KAB$ and $Z$ is the excenter of $KCD$, so $K,X,Z$ are collinear on the $K$ angle bisector, similarly, $L,W,Y$ are also collinear. So since $$\angle KXB = 90 + \frac{A}{2} = \angle ZCK,$$ we have $BCZX$ is cyclic.

Let $\Phi_1$ be the inversion centred at $K$ that swaps $A,D$, $\Phi_2$ be the inversion centred at $L$ that swaps $A,B$ and let $\Phi_M$ be the inversion at $M$ with radius $\sqrt{MB.MD}$ followed by reflecting across the angle bisector of $\angle AMC$. 

Claim: $\Phi_1(\Phi_2) = \Phi_M$

Proof: Let $J$ be an arbitrary point, let $J' = JL \cap (DCJ)$ and $J'' = J'K \cap (BCJ')$, so $\Phi_1(\Phi_2(J)) = \Phi_1(J') = J''$. But $J''$ is just the clawson-schmidt conjugate of $J$, so $\Phi_1(\Phi_2)$ just sends every point to its clawson schmidt conjugate, which is also what $\Phi_M$, the miquel inversion does. $\square$

To finish, see that both $\Phi_1, \Phi_2$ fix $(WXYZ)$ and hence $\Phi_M$ does too by the above claim, but $\Phi_M$ also swaps $O,P$ so if one of them was on $(WXYZ)$, the other must be too, so we're done. $\blacksquare$ 

Review: An unconventional geometry problem. While the problem statement is not very appealing, the solution is extremely novel. I don't think I've ever double inverted like this in any other geometry problem.

Phew! These were all the solutions, motivations, and reviews! If you are interested in learning the thought process of the guys while solving these problems, do check out the youtube video!

 We would end with the famous quote by Abhay!

" How did they survive day 1 without any combi?"

Do math!

Your favourite blogger
Sunaina 🍀 

Comments

Post a Comment

Popular posts from this blog

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong