## Sunday 18 August 2024

### IMO 2024 quick thoughts

Wow I thought IMO is in August. Is that a sign showing high school math is no longer in my range?

Q1. I don't expect anyone else to notice that floor function related problems is one of the most frequent type of questions appearing on this site but this is indeed a fact, so naturally I like this question a lot.

The integral case is clear: $\sum i\alpha = \alpha n(n+1)/2$, so it works for even integral $\alpha$ but not odd -- note that it must hold for all $n$. Now what about the decimal case? Well, notice that there are $n$ floor functions which means the summands is at most $n$ away from $\alpha n(n+1)/2$. If we choose $n$ so that $\alpha (n+1)/2 \approx m$ is almost an integer -- some fractional approximation here -- we can show that
$|mn - \sum [i\alpha]|\leq |mn - \alpha n(n+1)/2| + |\sum (i\alpha - [i\alpha])| \leq \varepsilon + (n-1/2)$.

Scrolling through the AoPS solutions I feel like my approach is overly analytical (which again, is natural), because it is actually easy to find an explicit $n$ for that.

Q2. Oh...number theory that I can solve. It is fun that both Q1 and Q2 contain conditions to hold for all large enough parameters, then the key is to pick the critical number that actually works.

This is a nicely constructed question, but the "key" is clear when the motivation is grabbed: you want to reduce the power into something $n$-irrelevant. There are a few choices like reducing it to (1) power one but that is trivial (2) power zero which does not help... and (3) power minus 1. In that case we are looking at $(1/a+b, 1/b+a)$ which gives a common denominator of $ab+1$ where a nice characterization arises from here.

Many solutions started immediately proceed to show that $ab+1$ is a power of 2. It works of course but only in the refined final answer. To me it is still easier to start from the traditional Archimedean approach.

Consider a simpler version where $(a,b) = 1$. The key step is to notice that we can actually tweek the gcd terms as follows:
$(a^n + b, b^n + a) = (a^{n+1}+ab, b^n+a) = (a^{n+1}+ab, b^{n+1}+ab)$.
And now, the terms are ready to be subtracted each other:
$(a^{n+1}+ab, b^{n+1}+ab) = (a^{n+1}-b^{n+1}, b^{n+1}+ab)$.

Suppose the above equals $g$ for large enough $n$ and $g$ admits a prime factor $p$. The first term implies $a=b$ mod $p$. For the second term, choosing $n+1 = 2$ mod $p-1$ gives $b^2+ab = a+b = 0$ mod $p$. Since $(a,b) = 1$ the only possibility is $p=2$ with $a,b = 1$ mod 2.

We now know that $g = 2^r$. i.e., $(a^n-b^n, b^n-ab) = 2^r$ for all large enough $n$, but that sounds counter intuitive because we could certainly expect some coincidences where the gcd is more than $2^r$, say $2^{r+1}$.

It turns out that you do not need to go very far away because mod 4 is enough. If $4\mid g$ we know that $a = b = 3$ mod 4 but then the GCD clearly oscillates between 2 and 4, so $g$ must be 1 or 2. From here the term $ab+1$ kicks in. Take $n = k\varphi (ab+1)-1$ which is of minimum 2, it follows that $ab+1=2$ and so $a=b=1$ is the only solution. The case where $(a,b)\neq 1$ is similar.

I really wonder if there is a reasonable solution without the use of $ab+1$. One possible approach is to argue mod $2^r$ for all $r$ to force $a=b=1$ mod $2^r$ for any $r$ which would lock them at $a=b=1$. Some field theory would be handy, but certainly not expected at this level.

The author says that the problem arose from a CS assignment. Although we do not observe any higher insight behind this is still an elegant number theory problem.

*Update: I suddenly realized my attempt of using alternate powers is not too bad at all. Taking $n = k\varphi (a+b)+1$ we actually reduced $a^n+b$ and $b^n+a$ to $a+b$ -- using the same argument we show that it must be a multiple of $a+b$ which is at least 2, locking $a=b=1$! Is that too clever to be correct...?

Q3. Wow, a combinatorial question hidden behind algebra. This is an interesting one and is probably the third question in a row I said that. The solution given in AoPS by mapping it on $\mathbb{N}^2$ to show boundedness hence periodicity is as elegant as you can get, and I managed to write down full solution the second I saw that. Anyone else?

Q4. Ohoho. A geometry Q1/4 means 7 less points for me.

Reading through the solutions I do have chance if I stare at the problem for 1 hour plus, but this is not going to happen right now. Complex bashing is still good up to this level of geometry questions...but what about harder ones?

Q5. I can't decide whether this is a combinatorial/game theory problem or just an algo problem, really. It lacks the taste of past questions where you find invariants/intrinsic structures that solves the problem. The question really is about finding a single, simple algorithm that works. It takes me longer to find prove lower bound than to find a solution.

It reminds me of SIMC which is also algo heavy but man this is IMO...

Q6. Functional equation is always amusing...and this time it returns stronger and harder. A family of functions based on an "OR" condition, and the question asks about a harsh character of the family. Definitely exceeds my ability to solve in a few hours, but this is something I am willing to try -- so no comment here I guess ;)

In overall I would say my solvable problems are very much to my taste and strength, but I would like to see a more balanced/classical setup.

I asked for a NT Q6 but that did not happen in 2024 either -- even worse we are hit by a truckload of "easier" NT-algebra problems. I don't know what others might think but easier NT problems are usually disappointing than anything. Q5 is a huge upset, I entirely do not expect such question in IMO.

Oh well, we will see again in 2025.

## Wednesday 7 August 2024

### 6/8/2024: Crossover

「我知道你連chromatic bust和Lightspeed都可以這樣硬過啦～可是你HyperTwist不就只能開random過了嗎？到時候你要打Paranoia Revolution怎麼辦？Over The Period呢？你現在刷13 Flare IX這麼痛苦不就是因為一碰到要交互的譜面就自亂陣腳了嗎？」這一通連珠砲發下來，少年只得照做。本來習慣了各種17連發的他只好回去從12和13打起。

12等的譜面不代表譜面沒有交互，只是沒有十六分的交互而已。相反譜面作者可能覺得八分音可以逐個打沒有交互的必要，這樣做出來的交互反而更多。或者這樣想：要堅持用交互的話不但可以在12等找到交互，在7和8找到交互也不奇怪。

「你好歹也是老玩家了，這種事就不能變通一下嗎？交互是希望盡可能讓兩隻腳輪流打，可是轉不過來的時候也沒辦法呢。如果硬要全交互的話一個譜面的打法從一開始已經固定了，但如果放棄一兩個交互可以打得更輕鬆的話為甚麼不這樣打呢？」少女這樣說道。

「只有實戰才能把這些刻進你的肌肉裡面。等你可以三首Flare V打進Extra Stage再說吧！」

「那下次我就要看著你能不能打過量子海和New Millennium了。每次都說自己要全清18可是自WORLD出來了以後你就只顧著刷分數都把這個目標拋到腦後了不是嗎？」

「哼哼，現在是精度的天下呢。要不這樣吧，我從15 EX開始打，我每過一首就換你練一道交互如何？」

「這根本不公平吧！！」

NEPHILIM DELTA、TRIP MACHINE EVOLUTION、ラキラキ……每一首平時打到滾瓜爛熟的老圖，此刻打起來又有著新的感受。

***