SMO Open 2024 ??% Speedrun

 Hi! It's Glen again.

So I was supposed to write a post for next weekend, but I woke up this morning to pictures of this year's SMO Open Round 2 in my messages, and I figured I might as well give them a go. And then I figured that I should just release my solutions to beat everyone else to the chase. Hence, this blog post is a week early.

When I did last year's SMO Open, I tried typing my thoughts while also being timed, which was generally rather inefficient (especially the FE, ugh), so this time, I just wrote stuff down on paper. You'll see the scans below. The pictures are ginormous to say the least, so you might have to do a bit of scrolling to get to my thought process. Also, in the interest of this being a speedrun, I wrote down the bare minimum that might possibly be counted as a solution (in the sense that, in the IMO, I'd probably lose marks on everything until a longsuffering observer went into coordination and saved me). Writing things down as I did is highly unadvisable.

With all that out of the way, let's begin.

Question 1

In triangle $ABC$, $\angle B = 90 \degree$, $AB > BC$, and $P$ is the point such that $BP=PC$ and $\angle APB = 90\degree$ where $P$ and $C$ lie on the same side of $AB$. Let $Q$ be the point on $AB$ such that $AP=AQ$, and let $M$ be the midpoint of $QC$. Prove that the line through $M$ parallel to $AP$ passes through the midpoint of $AB$.

As usual, Q1 is geometry.

This doesn't remotely look like a standard configuration, which means you probably actually need to know geometry to be able to solve it. On the other hand, there are no circles, though there are conditions about lengths being equal, which suggests that it should be bashable. Since I'm allergic to angle-chasing, I decided to just coordinate bash this.

Coord geom is generally not great with length conditions because you have a decent chance of ending up with square roots. However, in this case, setting $\triangle BPC$ as your main triangle lets you encode $BP=BC$ immediately and you get $A$ very easily.

At this point, I realised that you needed $AQ=AP$ (I just dove into the bash without really thinking about every step of the bash - definitely not advisable if you are bashing!) and panicked for a moment. I considered doing a phantom point $Q(q,-aq+1)$ before realising that $Q$ had to lie on $x=a$, which was a relief.

The rest of the bash was fairly smooth, except I ended up with a sign error in the end. I then had to go back and fix the signs (this is why you see so many signs scribbled out), but it all worked out in the end.

All in all, this took 17 minutes. (I am so rusty...)

The points looked nice enough that I figured that I could just reverse-engineer the synthetic from them. The first observation was that $M$ was the circumcentre of $\triangle BPC$, which I recognised because I know from bashing a lot that the circumcentre of $(0,1), (a,0), (b,0)$ is $\left(\frac{a+b}2,\frac{1+ab}2\right)$. This is probably horrible motivation. Moreover, the earlier observation that $QP\perp CP$ along with $\angle QBC = 90\degree$ tells us that $Q$ is the antipode of $C$, which is nice.

I then set out to prove these observations. $PQ \perp CP$ is a short angle chase. It also took me absolutely forever. (Did I mention that I'm allergic to angle-chasing?) After that, $Q$ being the antipode of $C$ is clear, and so $M$ being the circumcentre of $\triangle BPC$.

From this point, basically anything works. I originally wanted to use midpoint theorem on $\triangle BPA$ to say that the line through $N$ and midpoint $BP$ was the line in question, but that seemed like too much effort. Homothety is faster.

This took me another 10 minutes.

(A brief aside on bashing: if you're allergic to angle-chasing like me, I highly recommend learning a method of bashing if you want to get into the SIMO National Team. SMO Open geometry problems are in general very coord geom-friendly if you know how to set up your coordinates properly, and if you can get the geometry problem out of the way, you're already halfway to qualifying to the National Team!)

Question 2

Find the minimum value of $$\frac{x_1^3 + \cdots + x_n^3}{x_1 + \cdots + x_n}$$ where $x_1,x_2,\ldots,x_n$ are distinct positive integers.

This question was pretty weird. The intuition is that cubes are big, so you just want to choose all of your $x_i$ to be as small as possible, i.e. $1$ to $n$. That's the computation in the first line.

After that, it's just a matter of showing that this is optimal. One way to do this would be to take some $x_i$ and try to adjust one of them smaller and show that the overall expression gets smaller. You can see me work through the computation there and you get some inequality which looks true and also very very loose.

Looking at that inequality, you want the small side ($a$) to be as small as possible, so you should pick the largest $x_k$ that can be adjusted lower. This forces everything larger than it to be $x_k+1,x_k+2,\ldots$, which is an incredibly strong condition.

However, it turns out that you don't even need it because of how loose the inequality is; the $b(3x_k^2-3x_k+1)$ term just kills the $a$ term.

This took me 9 minutes.

In hindsight, I could have saved myself a lot of pain by recalling one of my favourite facts about fractions: if $\frac{x}y < 1$ for $x,y >0$, then $\frac{x+c}{y+c} > \frac{x}y$ for any $c>0$. (I think of this as the Japanese Teacher Lemma, because when I was in year 1 or so my friends told me that their Japanese teacher gave them bonus marks for their homework if they submitted corrections, and she did so by adding 5 points to both the numerator and denominator of their scores. This is what led me to realise this amazing fact about fractions.) Anyway, suppose we've adjusted some $x_k$ down by $1$. Reversing the adjustment would mean adding more to the numerator than the denominator, which is of course larger than adding the same amount to the numerator than the denominator.

Question 3

Prove that for every positive integer $n$, there is a unique $n$-digit integer $A(n)$ which is a multiple of $5^n$ and whose digits are all odd.

(It's "a unique", not "an unique"! The word "unique" starts with a y (IPA: /j/) consonant sound!) 

At first I misread this and didn't see the part that $A(n)$ had to have $n$ digits, which confused me because surely uniqueness couldn't be true. I then went back and looked at it again and realised my error.

Anyway, you see me trying small cases. By $n=3$, I had realised that I wanted some number ending with $75$, and there could only be one such. It's clear that this method generalises, and one may just induct.

I think what I wrote is pretty clear so I'm not going to go into any more detail. Really, this is just an easier version of SMO Open 2018 Q3.

This problem took me 5 minutes.

Question 4

Alice and Bob play a game. Bob starts by picking a set $S$ consisting of $M$ vectors of length $n$ with entries either $0$ or $1$. Alice picks a sequence of numbers $y_1\le y_2\le \cdots \le y_n$ from the interval $[0,1]$, and a choice of real numbers $x_1,\ldots,x_n \in \mathbb{R}$. Bob wins if he can pick a vector $(z_1,\ldots,z_n)\in S$ such that $$\sum_{i=1}^n x_iy_i \le \sum_{i=1}^n x_iz_i,$$ otherwise Alice wins. Determine the minimum value of $M$ so that Bob can guarantee a win.

(Another olympiad grammar pet peeve of mine: Problem statements which end in "Determine..." or "Prove..." should end in a full stop, not a question mark.)

This problem was proposed by David Lin.

There's an obvious interpretation in terms of dot products of vectors, and this the condition just means that the projection of $\mathbf{z}$ onto $\mathbf{x}$ is longer (in terms of signed distance) than the projection of $\mathbf{y}$ onto $\mathbf{x}$.

You see me trying some small cases, and here I am very confused because I missed the condition that $y_1\le \cdots \le y_n$ - it seemed like I had to choose all $2^n$ vectors to make up $S$. I then asked the group chat whether I was misreading something, and Gabriel helpfully informed me that I was. (Thanks!)

But it turned out that I was still very much done: we instead want the set of legal $\mathbf{y}$ to be contained in the convex hull of $S$. I didn't write down the motivation for this at all, but this is just a (rather overkill) application of the geometric Hahn-Banach theorem. It turns out that you can get through this question with a lot less generality, which is what I did thereafter.

Anyway, I immediately recognised that the set of legal $\mathbf{y}$ formed a simplex (higher-dimensional analogue of a tetrahedron), because of some problem I did for my algebraic topology homework some years ago. In fact, it's not hard to guess what the $n+1$ vertices of this tetrahedron are. We can then check directly that choosing these $n+1$ points to be $S$ works, i.e. $M \le n+1$.

The rest of the proof is just me trying to avoid to having to appeal to Hahn-Banach. If you choose $n$ or fewer points, they lie on a common hyperplane $\mathbf{z}\cdot\mathbf{a} = c$ (think in 3D: you need at least $4$ points before they start not lying on the same plane. See also: Wee Kean's post on linear algebra.). On the other hand, a simplex, being "$n$-dimensional", can't lie in a hyperplane, which is "$(n-1)$-dimensional". Then, we can just pick $\mathbf{a}$ or $-\mathbf{a}$.

All in all, this took me 25 minutes. Turns out that undergraduate math is useful for olympiad math after all.

(Comparing this to the final comment of Gabriel's post, it seems like we had very different thought processes.)

Question 5

Let $p$ be a prime number. Determine the largest possible $n$ such that the following holds. It is possible to fill an $n\times n$ table with integers $a_{ik}$ in the $i$-th row and $k$-th column, for $1\le i,k\le n$, such that for any quadruple $i,j,k,l$ with $1\le i<j \le n$ and $1\le k<l \le n$, the number $a_{ik}a_{jl} - a_{il}a_{jk}$ is not divisible by $p$.

This problem was proposed by Lim Jeck.

So this was a disaster and should really have taken me a lot less time. Sigh. I am sorry that you had to scroll through 6 pages of faff to get here.

Anyway, it's clear that the funny condition was just a determinant, so you're really just thinking about vectors being linearly independent (and in fact, since we're looking at them pairwise, we just want them to not be multiples of each other). I wrote down a comment about $\mathbb{F}_p\mathbb{P}^2$; really, it should be $\mathbb{F}_p\mathbb{P}^1$, which is really just a fancy way of writing "the set of lines in $\mathbb{F}_p^2$". When we do projective geometry, we're working in $\mathbb{RP}^2$, which is $\mathbb{R}^2$ with a line at infinity; analogously, $\mathbb{F}_p\mathbb{P}^1$ is $\mathbb{F}_p$ with a point at infinity. But anyway, that's all very much overkill; it's easier to say that $(0,0)$ is not allowed, for each nonzero vector, there are $p-1$ nonzero vectors parallel to it (i.e. its multiples by $1, 2, \ldots, p-1$), and so there are $\frac{p^2-1}{p-1} = p+1$ possible directions.

We just need to construct the equality case, and boy oh boy this took me an eternity. The $p=2$ case is pretty easy, and you can get $p=3$ just by trial and error, and then it gets hard. At this point, I was fairly convinced that $p+1$ was the correct bound, since I'd just constructed a fairly nontrivial-looking equality case for $p=3$.

Trying to generalise it gave me several wrong guesses for $p=5$, and also reminded me of a similar problem: SMO Open 2016 Q3. (I really don't like this problem. Before 2016, I'd been consistently solving 2 questions per year in Open Round 2 before getting stuck, and if I hadn't randomly stumbled upon the construction for this question, 2016 might have just gone the same way. In my opinion, this is the only problem in that year whose solution doesn't really have a motivation.) For this problem, I used the fact that $\frac{n+1}n$ are all distinct mod $p$ for $n=1,\ldots,p-1$, which meant that you could probably do something like having $0,1,\ldots,p-1$ in a row and cycling. But obviously, that doesn't work because you want $p+1$ things in a row. My construction for $p=3$ led me to believe that I should try duplicating the $1$s, which didn't work.

I realised that valid constructions are not unique: we can multiply rows and columns by nonzero constants and everything still works (I didn't write down the reason, but you can look at the determinant expression and see that scaling a row just scales the determinant by the same factor). (We can also permute rows and columns, but I'd already been using that implicitly by putting $0$s down the diagonal - every row and column had to contain a $0$ for equality to happen.) I then tried toggling random rows and columns in my $p=3$ construction but I just couldn't get a generalisable construction. I tried toggling such that the first row and last column would be all $1$s, but that didn't seem to work. Also, I didn't know what to do with the first column and last row.

At some point, I began to doubt that my bound was tight, but I couldn't manage to tighten it, so I went back to guessing constructions.

After a lot of pain, I eventually realised that I had just missed the obvious: I could let the first row and first column be all $1$s (except for the top left entry, of course), and then the remaining $p\times p$ subgrid forms a magic square. Toggling the $p=3$ accordingly gave (at long last!) a generalisable construction, which - surprise surprise - is just putting in $0,1,\ldots,p-1$ and cycling, and it's not hard to check that this works.

This saga took me an hour and 40 minutes for a total of just under 3 hours. Not great, but at least I got through the whole paper this time!