SMO Open 2025 ??% Speedrun

Glen & Sheldon here.

At last, our schedules aligned enough for us to try this year's SMO Open together. Here's an outline of our thought process while solving the problems, featuring some screenshots from our Cocreate whiteboard.

Problem 1

In the triangle $ABC$, $\angle B>90^\circ$, the incircle touches the sides $BC$ and $CA$ at $D$ and $E$, respectively. The lines $ED$ and $AB$ intersect at $P$. The incircle of the triangle $AEP$ touches the sides $PE$ and $AP$ at $D_1$ and $E_1$, respectively. The lines $E_1D_1$ and $AE$ intersect at $P_1$. Suppose $P,C,E,B$ are concyclic. Prove that $BE$ is parallel to $PP_1$.

• Weird-looking problem.
• The concyclic condition means $\angle ABC = \angle AED$.
• Maybe it could be less weird if we write it in terms of the angles of the triangle, $\angle ABC = 90^\circ + \frac{\angle ACB}2$.
• Actually, the equal angles imply $\triangle ABC \sim \triangle AEP$.
• The parallel condition is equivalent to $\frac{AB}{AE} = \frac{AP}{AP_1}$, and the similarity tells us that the LHS is equal to $\frac{AC}{AP}$.
• Oh, notice that actually the configuration $ABCEDP$ is similar to $AEPE_1D_1P_1$ (so that's why the points are named $E_1,D_1,P_1$...), so $\triangle AEP \sim \triangle AE_1P_1$ by the same ratio.
  
  
• The result follows.

Time taken: 8 minutes

Problem 2

Consider the polynomial $P(x)=x(x-1)\dots(x-2024)$. Show that $P^{(n)}(x)=2025$ has $2025^n$ distinct real roots, where $n$ is any positive integer and $P^{(n)}(x)=P(P(\dots(P(x)\dots)).$

Proposed by Yap Jit Wu

In the SMO, this was printed as $2024^n$, but $2025^n$ is what the question was supposed to say.

• Here's a picture:
  
  
• When $n=1$, we can use the Intermediate Value Theorem by setting $x$ to be odd multiples of $\frac12$. This gives us some super loose inequality around the order of like $1000! > 2025$.
• Then we can just induct. All the roots of $P(x) = 2025$ are between $0$ and $2024.5 < 2025$, so we're drawing horizontal lines between those two lines there, with each giving rise to $2025$ distinct roots between $0$ and $2025$. Repeat.

Time taken: 2 minutes

Problem 3

For any 4-digit positive integer $n$, define $f(n)=(a+b)^2$, where $a,b$ are the numbers formed by the first two and last two digits of $n$, respectively (leading zeros are allowed). For instance, $$f(2025) = (20+25)^2 = 45^2 = 2025.$$ Find all 4-digit positive integers $n$ such that $f(n)=n$.

Proposed by Ang Yan Sheng

• We want to solve $100a+b = (a+b)^2$.
• What can we do other than just directly bashing out all the squares.
• Try mods? Mod 4 gives $b\equiv 0,1 \pmod 4$.
• Mod 3 gives $a+b \equiv 0,1 \pmod 3$.
• Actually, mod 9 gives $a+b \equiv 0,1 \pmod 9$ since $a+b, a+b-1$ are coprime.
• Can we just bash? We've cut it down to like 20% of the original number of cases.
• The mod 4 one doesn't actually reduce the number of cases, but it also tells us that $a$ is even, which sort of does.
• Ok, let's bash. We just need to care about $32 \le a+b < 100$ where $a+b\equiv 0,1\pmod 9$.
  
  

  

  
• The ones with the first two digits underlined failed because $a$ is odd. So we have $2025,3025,9801$.

Time taken: 10 minutes

• There's probably a nice solution because the solution set is just this? Whatever, moving on.

Problem 4

(ISL 2017 N6) Find the smallest positive integer $n$ or show no such $n$ exists, with the following property: there are infinitely many distinct $n$-tuples of positive rational numbers $(a_1, a_2, \ldots, a_n)$ such that both $$a_1+a_2+\dots +a_n \quad \text{and} \quad \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_n}$$are integers.

Proposed by Ang Yan Sheng, Lim Jeck & Yap Jit Wu, c. 8 years ago

• Some general complaining that an N6 reappeared in SMO, so now we have to do it. Also, we can't remember what the answer was.
• $n=3$ seems like it should be possible - you have lots of degrees of freedom.
• Maybe let your three numbers be $\frac{a_1a_2}{b_1b_2}, \frac{a_1a_3}{b_1b_3}, \frac{a_2a_3}{b_2b_3}$ and try to solve for that?
• You end up requiring $a_1,b_1 | a_2b_3 + b_2a_3$ and the symmetric equivalents, which doesn't seem that bad but we don't know how to solve this.
• Maybe put in $a_1=2,a_2=3,a_3=5$? We still get a cursed-looking system of 6 divisibility relations.
• Can we show that $n=2$ fails? Yeah, multiply the two things so we have $2 + \frac{a}b + \frac{b}a$, which isn't an integer unless $a=b$. In that case, we must have $a=b=1$ or $a=b=2$.
• Do there exist infinitely many $a,b$ such that $a^2\equiv -1 \pmod{b}$ and $b^2\equiv -1 \pmod{a}$? If so, $\frac{a}b, \frac{b}a, ab, \frac1{ab}$ work.
• We just need $ab|a^2+b^2+1$, for which we can Vieta jump from $(1,1)$.
• So $n=4$ works.
• Does $n=3$ work? We try and fail for a while to prove either possibility.
• Observe: for $n=3$, this works:
  
  
• Maybe this can be generalised. Try $\frac45$, then the next has to be $\frac4{23}$, and then we have (help we can't do arithmetic) $\frac{3}{115}$, which is bad.
• Ok, maybe try $\frac34$. Then we have $\frac3{14}$, and $\frac1{28}$, which works. Hmm.
• In general, our first two things should be $\frac{n}{n+1}, \frac{n}{n(n+1) + (n-1)} = \frac{n}{n^2+2n-1}$, which leaves...(help we can't do algebra) $\frac{n-1}{(n+1)(n^2+2n-1)}$. Oh, that basically only works for $n=2,3$. Sad.
• Clearly we should just give ourselves more degrees of freedom. Put $\frac{n}{n+a},\frac{n}{n+b}$, where we require $n|a+b$. Then the last thing should be $\frac{ab-n^2}{(n+a)(n+b)}$. We need the top to divide the bottom, so we should just force the top to be $1$.
• We have $n|a+b, ab=n^2+1$. Looks like Vieta jumping. Here's a solution: $(a,b,n) = (2,13,5)$. So we should probably Vieta jump on $a+b=3n, ab = n^2+1$.
• How does that work again? Uh...just put in other values:
  
  
• In general, if $(a,b,n)$ works, we want to jump to $(n,3b-n,b)$. Indeed, $n+(3b-n) = 3b$, and $n(3b-n) = 3bn-n^2 = 3bn-ab+1 = b^2+1$. Then the usual Vieta jumping arguments tell us that we have infinitely many solutions.

Time taken: 52 minutes

• Actually, notice that those numbers we wrote above are Fibonacci numbers.
• Is this Fibonacci identity part of the intended solution?

Problem 5

Alice starts out with some coins in a box. On the $n^{\text{th}}$ minute (for $n=1,2,3,\dots$), she can choose to put an additional coin into the box or do nothing, and then she writes the number $2c^2-n^2$ on the board where $c$ is the number of coins in the box. Show that for any positive integer $m$, there will eventually be two numbers on the board that sum to a multiple of $m$.

Proposed by Ma Zhao Yu & Dylan Toh

• Work mod $m$, so there are finitely many $(n,c)$. So if we can always avoid a multiple of $m$, then we may WLOG assume that the construction is periodic.
• What happens when $c$ is constant? Oh, then you eventually explode. (Can't remember what our reasoning here was.)
• Let's try to bash a case, say $m=5$ and starting from $c=1$, and say we don't allow ourselves to hit $0,2,4$. That...eventually fails.
  
• How does $2c^2-n^2$ change with each move? It goes up by $-(2n+1)$ plus maybe $2(2m+1)$. Doesn't seem useful.
• We can think of this as follows: suppose we disallow one of $k,-k$ for each $1\le k \le \left\lfloor\frac{m}2\right\rfloor$, then can we find a path of $(n,c)$ that loops to itself?
• Each time, $c$ goes up by $0$ or $1$, so you're probably not going to loop back in $m$, but some multiple of $m$.
• If this is the case, then we should get some point where $n=c$. Can we find some sort of contradiction? Doesn't seem like it.
• Not sure how to control for the banned numbers in general.
• Bashing the case tree for $m=5$ again, we see that we would have run into problems at $m=5$ even if we started with another number.
  
• Does something go wrong at $m$ each time? Seems unlikely.

After about half an hour the intersection of our free time ended, so we continued the next week.

• Looking back at that last picture, maybe we can do something about eliminating the "middle" numbers? Suppose we want to solve this for $m$ odd:
  
  
  
• That reduces to $m|1-n^2-n'^2$, whose solutions include $(0,\pm 1)$. So if $c=\frac{m\pm1}2$ when $n=0$ then something goes wrong:

  

  
  
• We can repeat the argument for the even case to show that it can't be $\frac{m^2}2$. But in general...the same thing shows that if we have $(n,c) = \left(0,\frac{m\pm a}2\right)$ for some $a$ then we can't have $(n,c) = \left(\pm a,\frac{m\pm a}2\right)$, which isn't super useful.
• Actually, how did we show that $c$ can't be constant again? Uh, if it is, then $2c^2-n^2$ takes at least $\left\lceil\frac{m}2\right\rceil$ different values, which is bad. That's not very helpful.
• Wait, it's even simpler: $(0,c)$ and $(2c,c)$ give $\pm 2c^2$.
• Ah, so we can't ever have $(0,c)$ and $(\pm 2c, c)$. Actually, this is just what we did above, but with the variables changed.
• Let's look at $(c,c)$ again. If we have that, then we also can't have $(3c,2c)$. Can we generalise this? We want to solve $2a^2-b^2=1$...help how do Pell's equations work again? Something about expanding $(1-\sqrt{2})^n$. We next get $(7c,5c)$ which gives the same value as $(c,c)$, so the next one should also be banned...doesn't actually seem useful - no matter what you calculate, you are only ever going to find at most two banned values in each row and column, which probably isn't enough.
• Maybe induct? But on what?
• Sadness :(

After about another hour we gave up and complained to Zhao Yu that the problem was too hard. He gave us a hint:

• Okay, so we probably want to show that if we hit $(n,c)$, then there's something we can't hit which is linear in $n,c$. Something like $(n+c,n-c)$? That doesn't work; the cross-term doesn't vanish. $(2c+n,c+n)$ works. What now? Well, we can keep iterating...but that's useless for the same reason why finding all the Pell's solutions is useless.
• If we take the inverse, do we get a nicer formula? It should be $(2c-n, n-c)$, which isn't that great either.
• Wait, but we also have to go from $(n,c)$ to $(n+1,c+1)$ or $(n+1,c)$. How do the banned things change? Let's do the one with minuses because it will probably look nicer. In the first case, $(2c-n,n-c)$ becomes $(2c-n+1,n-c)$ while in the second, it becomes $(2c-n-1, n-c+1)$. So we should have chains of banned squares like this:
  
• But the second chain can be passed through by our path when we go from $(n,c)$ to $(n+1,c+1)$, which is not great.
• We could also try the $(2c+n,c+n)$ ones. But we get things like $(2c+n+1,c+n+2)$, which has even bigger holes.
• Wait, but we could just flip a sign and look at $(2c-n,c-n)$ instead, so now our possible directions both can't be crossed by our path.
  
• Surely, we have to be done somehow. Consider the path we take plus the banned path. Is it possible for them to always go around and not intersect each other? (Squiggle = taken path, zigzag = banned path)

  
• Let's look at $(n,c)$ and $(2c-n,c-n)$. Throughout the period, $n$ increases by $1$ on average for each move, and $c$ by some $k<1$. Then $c-n$ increases by $-(1-k)$ on average and $2c-n$ by $-(1-2k)$. These average gradients are not equal, because even if they have the same sign, $k<1$ but $1-k > 1-2k$.

  

  
  
• This is now a standard problem about two loops on a torus of two different average gradients having to intersect.

  
• There's an overkill way to do this which involves applying some linear transformation so one of the loops instead has average gradient $0$, but there's also an easier way: expanding to the plane, the banned path is sandwiched between two paths of average gradient $k$, so taking the limit to infinity, it must also have average gradient $k$.
• Whew.

Time taken: ~2 hours in total