## Sunday, 25 July 2021

### Thoughts on IMO2021 Q2

IMO 2021 is finally over. As usual I skimmed through the question and focus on the inequality problem where I usually perform the best. It was Q2 this year, but it is not an average Q2.

It turned out to be as hard as Q3 (mean score 0.375 against Q3's 0.372, but Q2 gives out more partial scores and more zeros), both harder than this year's Q6 (mean 0.481). Possibly one of the most controversial Q2 in IMO history. What makes it so interesting? Here are my thoughts.

First let us look at the question.

Problem. Show that
$\sum _{i,j} \sqrt{|x_i-x_j|} \leq \sum _{i,j} \sqrt{|x_i+x_j|}$
for all real numbers $x_1,...,x_n$.

If you have already spent time onto this problem, here is the solution. This is similar to the solution mentioned by TheUltimate123 in the AoPS thread.

Claim 1. The case $n = 0,1$ is trivial.

Claim 2. LHS is invariant upon shifting all $x_i$ by a constant (let us simply call that "shifting" for the rest of the solution)

Claim 3. If $x_k = 0$ for some $k$ then the $x_i$-related terms on both sides are the same which is
$2\sum _{i\neq k} \sqrt{|x_i|}$. Therefore we now WLOG assume that all terms are non-zero.

Claim 4. If $x_k+x_l=0$ for some $k\neq l$ then the $x_k$ or $x_l$-related terms on both sides are also the same, which is $2\sqrt{2|x_k|} + \sum _{i\neq k,l}(\sqrt{|x_i-x_k|}+\sqrt{|x_i+x_k|})$.

Claim 5. RHS is not minimal upon shifting unless $x_k+x_l=0$ for some $k,l$.

Proof: Jensen gives that
$\sqrt{|x+y+\varepsilon|} + \sqrt{|x+y-\varepsilon|} \leq 2\sqrt{|x+y|}$
for $x+y\neq 0$ and $\varepsilon \leq |x+y|$.
Summing over all $x_i$ gives
$\sum _{i,j} (\sqrt{|x_i+x_j+\varepsilon|} + \sqrt{|x_i+x_j-\varepsilon|}) \leq 2\sqrt{|x_i+x_j|}$.
for sufficiently small $\varepsilon$. Therefore a shift of either $\varepsilon /2$ or $-\varepsilon /2$ would give a smaller RHS while having LHS fixed.

Note that $x_k+x_l\neq 0$ is required to maintain convexity of $\sqrt{|x+y|}$.

Therefore the induction is completed. If $x_k=0$ for some $k$ then we reduce to the $n-1$ case by claim 3. Otherwise shift until $x_k+x_l=0$ for some $k,l$, then reduce to the $n-2$ case by claim 4.

The above also gives the equality case in full. Firstly adding arbitrarily many zero terms does not affect the sum. If we assume non-zero terms then the only instance where RHS decreases is by shifting, so in order to obtain equality the terms must be canceled pair by pair without the need of shifting. We therefore conclude that equality holds if and only if the terms are symmetric along zero.

*

There are alternative solutions using completely different approaches like the use of integral to prove the more generalized case $E|X+Y|^{1/2} \geq E|X-Y|^{1/2}$ for random variables $X,Y$. Even more fascinating, one used the integral
$\sqrt{|a+b|}-\sqrt{|a-b|} = \frac{1}{\sqrt{2\pi}}\int ^{\infty}_0 x^{-3/2}(\cos (a-b)x-\cos (a+b)x)dx$
$= \frac{1}{\sqrt{2\pi}}\int ^{\infty}_0 2 x^{-3/2} \sin ax \sin bx dx$.

It is also note worthy that the original problem uses the exponential $\alpha = 1/2$. The statement holds for all $\alpha \in (0,2]$. Convexity works all the way up to $\alpha = 1$ but college techniques is absolutely necessary for higher $\alpha$. One approach is to use linear algebra and binomial theorem for non-integer exponents, and the other is a generalization of that integral identity (with the help of gamma function).

You might have noticed something here already: the abundance of calculus solutions, the clear generalization to something famous and common in undergraduate maths, and the flexibility in exponential (cf. most $a,b,c$ type inequalities that you saw in 2000s-2010s IMOs), all suggests that this is a very good question for undergraduate contests.

However if we consider IMO to be the pool of the most talented math students in the world (even better than those participating undergraduate contests on average), why is this a hard problem to them? And why did they perform poorly at the end?

I figured out the solution almost immediately, like within 15 minutes, and the flow of thoughts is as follows: the shift is clear immediately. Then I tried to solve the case $n=2$, which is not easy already. By using the parametrization $x_2 = rx_1$, it is found that the equality is tight if $r=-1$. Putting back to the inequality with $x_1$ and $x_2$, it can be found that when $x_1=-x_2$ the terms on both sides are equal. The cancellation trick is soon found to be working with larger $n$. We now know that induction may work as long as we can reduce to these cases. (I missed the case $x_k=0$ when I first solved the question, so I didn't get a 7 in that sense...)

By reducing to these case, we must show that shifting to these case gives a smaller RHS, and this is what we need to prove. We applied Jensen and showed that we can always get smaller as long as $x_k+x_l \neq 0$ so we are done.

...or not?

You might have spotted the problem already. The hard bit of the question is the indirect relation between the fact that you can shift to reduce RHS and the goal that you can shift to a smaller RHS that $x_k+x_l=0$.

It goes through only if you have a calculus sense, or else it could trap you forever.

For starter let us consider to shift by the maximum possible distance $\pm\min |x_i+x_j|/2 = \pm t$ so that we reached a singular point (where $x_k+x_l=0$...). The problem is: we only know that a either a shift of $+t$ or $-t$ gives a smaller RHS but not necessarily both. If you shift to the point where $x_k+x_l=0$ you are not guaranteed a smaller RHS.

Or, if you shift little by little to reduce RHS, can you guarantee that you end up with a singular point?

These are never a problem if you know calculus argument, and they can only be understood via calculus argument.

From a global point of view, the sum is definitely increasing with large enough shifts. Since the sum is also bounded below and is continuous, there must be a global minimum. Since the minimum does not occur at the smooth part it must be at one of the singular point. We can shift directly to that point to complete the induction.

To shift gradually you may argue that the derivative between two singular points do not change signs so one of the two neighboring singular point must be a local minimum [or even weaker, a local minimum with respect to the closed interval bounded by the two singular points]. Alternatively, since we know that $(\sqrt{x})' = 1/(2\sqrt{x})$ which rockets as $x\to 0$, we argue that the derivative of $\sqrt{|x_k+x_l|}$ overwhelms all other terms as we shift $x_k+x_l\to 0$, so that must incur a minimum [hence even singular point is a local minimum].

And how can you argue that by "elementary means"? Probably not, unless the official solution suggests something spectacular.

If you check everything else in the solution they are pretty standard. induction of course, simple special case ($x_k=0$) and a more complicated special case ($x_k+x_l=0$), substitution [in fact, instead of a shift, we may apply the substitution $x_i = y_i+t$ to achieve the same] to hold one side invariant, Jensen on convex functions --- these are all standard tricks in IMO. It is the final link that completes the solution, is hard to realize and that link is, regrettably unavoidable.

It is a beautiful and insightful inequality. Again quoting someone in the thread -- the beauty of this problem is that $n=2$ provides everything you need: minimal condition and the shifting. (Although to be fair, $n=2$ hides the technical problem as described above, and you will only meet that at $n\geq 3$.) It simply requires Jensen (or even just elementary comparison because it is just square root) in a two line calculation. We do not need 30 lines of machinery like other IMO inequalities did.

We can continue the list and praise the problem in many more different ways. The only criticism is that the problem unfortunately does not belong to IMO.

*

I last wrote about IMO problems in 2006, before this blog opened. I wrote that in my previous blog, a site that is long abolished (at least I do not have to worry about Blogger closing soon...yet).

I was of course, too immature to understand what happened -- I copied someone else's solution and put it on my blog. For whatever reason that post received tons of comments out of nowhere: recalling that discussion now I believe that those people are truly qualified to do these IMO problems. It is still a mystery up to now how did they found my post (out of a blog that never talked about advanced mathematics otherwise) and open a contextful discussion there, but this is the beauty of Internet in the 2000s.

Without running into a nostalgic loop, let me finish with that particular IMO problem that I discussed back in 2006. That problem was 2001 Q2 -- another Q2, another inequality, and another problem that allows elegant solution using Jensen's inequality.

Problem. Prove that for all positive real $a,b,c$ the inequality $\sum _{cyc} \frac{a}{\sqrt{a^2+8bc}} \geq 1$ holds.

## Friday, 23 July 2021

### 被青梅竹馬抓來(略) (2)：別人十年磨一劍，你一年磨一劍已經非常快了

"優雅な午後"
Character design: @kuonyuu, Illust: @茶桜みゅ commissioned by forretrio. Pixiv
Editing and re-posting are prohibited // 無断転載、無断使用禁止です

*

「大家早安～歡迎來到國立魔法學園，也歡迎大家成為魔法科的一分子。再次自我介紹一次，我是庫里斯，將會擔任魔法科的導師一職。特長是風魔法－－嗯，相信在座各位已經充分理解這一點了吧？」台下立刻傳來殺人般的目光。

「哎呀，真是危險～」庫里斯從講台上跳下來，水桶在他的操控下飛到他的面前：「我看看……裡面裝的居然是冰？這樣砸到頭肯定要進醫院呢。老師我可以接受水桶，但是冰桶有點過份了喔，克萊伊同學。」他特地把水桶裡面展示給同學看，只見裡面的水已經結成一整塊冰。

「嘛，老師的確不知道誰把水桶放上去，不過我看到你嘗試用魔法把水桶推下來呢。這樣遠距離操作其實很顯眼，我建議你下次準備好觸發性的魔法陣喔。」

「在此之前，我希望你們想一下－－你們來到這裡，是希望得到甚麼呢？既然你們進入了魔法科，那就代表你們的能力已經遠超常人，甚至已經可以成為即戰力了。這樣的話為甚麼要浪費三年在這裡再聽一次你們以前很可能已經聽過的知識呢？」

「如果你們是貴族的話，在這裡就讀就只是一個過程而已。身為貴族擁有一定的魔法能力就足夠了，過份強大只會讓人懼怕。你們大部分人畢業都會接過家業，在帝都舒適地生活著，這樣魔法再好又有甚麼用呢？」

「對於平民入學的你們，我要恭喜你們：進入魔法科代表通往帝都頂層的大門已經為你們躺開，你們是受益最大的一群。不過你們也可以想一下，進了這裡就一定要從事魔法相關的職業嗎？很多人都覺得身為魔法師可以當冒險者發大財，可是你們知道正是因為魔法師的折損率是冒險者之間最高的一群所以才這麼值錢的嗎？」

「我沒有要勸大家別當冒險者的意思，相反我很樂意以過來人的身份幫助你們。不過我想你們既然有能力進入這個班級，自然也有餘裕考慮標準課程以外的興趣－－你們應該不會只對冒險有興趣吧？」

「我的想法是讓你們花時間找出你們希望學習的東西，然後由我或者其他人來指導。我會花三分一的時間講解標準課程內容裡面比較有用的東西，剩下的就作為課題交給你們了。」

「至於另外三分二的時間就是個別指導的時間了。唔－－具體時間要怎樣分配主要還是看你們的興趣在哪個方面。對魔法或者戰鬥有興趣的話可以一起去地下城冒險；就算是鍊金術或者商業這些東西我也可以找我朋友幫忙。當然你們想要找我過招的話只要別偷襲，我隨時都歡迎哦。畢竟－－」

「為師我，不討厭打架呢。」

*

「庫里斯老師你好。」公主殿下首先打了個招呼她的名字是菲莉，是帝國正室的次公主。本人是頭腦派，體質一般所以成為了唯一一個沒有參加跟老師對戰的魔法科學生。不過她也繼承了優秀的血統，可以使出強力的水跟光魔法。

「菲莉公主您好，」他稍鞠一躬：「雖然公主您沒有參與比試，不過我早就聽說過您是一位優秀的光魔法師。有機會讓我指導您是我的榮幸才對。」

「老師過獎了。聽說老師作為冒險者十分活躍，這些實戰經驗對我們學生來說是非常寶貴的呢。不過－－」她稍微頓了一下：「我只是有一丁點擔心，那件事會影響老師你與貴族的關係嗎？」

「嗯。」她不置可否地點了下頭然後呼喚伊雅娜道：「其實今天想找老師你的是她才對。伊雅娜～你有東西想問吧？」

「嗯？」

「我問過父親，他也認同你的看法。不過他也說了只有對上很強的對手時才有犧牲威力而加強隱蔽性和速度的價值。即便是這樣，老師也會建議我這樣朝這個方向鍛練嗎？」

「非常好的問題呢。這樣說好了，對你來說電光劍到底是常規招式，還是保命的底牌呢？」

「嗯……算是底牌？我的魔力本來就沒法一直在劍上附魔，上次我也是最後才把這招掏出來。」

「作為底牌的招式沒有一擊必殺的能力就沒有意義了。在高階的戰鬥中，所有常規套路都是為了那一兩招殺著而準備的。你想一想，作為殺著到底是可能打不到高階對手的超強力攻擊，還是稍弱一點但是很穩的攻擊更好呢？」

「老師的意思是，對上一般的對手不用全力的電光劍也能贏，所以練習加速版電光劍應付高手更好嗎？」

「這個思考方向沒錯，不過讓我來選的話我覺得兩招同樣重要。全力的電光劍並不是一無用處－－跟不上那速度但擁有優秀防御能力的人和魔物多的是，那招作為破防非常實用。反正底牌又沒人規定只能有一張，都一起練就好了嘛。」

「……」伊雅娜同學有點無言。他是把底牌招式當成甚麼了，以為這是回家練一個星期就能熟練地使出來的招式嗎？為了讓魔法效力與她往前突刺的動作同步，她花了半年多的時間才算小成，期間魔力失控電到自己等意外更是不計其數。

「要我說的話，你甚至可以考慮再加練一招－－將輸出的魔力壓制到可以在格劍時隨時使出來的程度。我保證這招由主修物理劍術的妳使出來的話絕對能嚇到對手的。」

「老師……你是不是忘記了一件事……」

「嗯？怎樣了？」庫里斯擺出燦爛的笑容。

「咳唔，所以你這個學期的第一個課題已經決定好了－－」他清了一下喉嚨道：「我希望你花點時間研究一下在劍上附魔的不同方法。在你對兵器附魔有一定了解以後我們再來討論吧。

「好……好吧。」伊雅娜並不相信老師真的可以幫她練出電光劍的變種，但是作為學習的課題的話還是可以接受。圖書館應該有相關的書籍吧？

……才怪。

「別人十年磨一劍，你一年磨一劍已經非常快了呢！」老師帶著一貫的笑容這樣應道。當下她真的想一拳灌在老師的帥臉上，不過她覺得這一拳打在風盾上使她骨折的機會更大，所以她才忍住沒有出手。

=============

## Sunday, 4 July 2021

### 04/07/2021: Game optimization patterns

Two notable events in the world of competitive gaming.

Rolling has been a viable style in classic Tetris and we found Cheez breezing through loads of world records. The way he broke the 100 line speedrun so casually when the previously newly set record was made upon multiple extreme optimization is simply spectacular. Rolling allows one to input above 20Hz edging close to the hardware limit (30Hz for the on-off cycle). The problem now is about consistency and flexibility, and we will know more in upcoming CTM and of course CTWC.

The SMB1 Any% record has been broken once again, this time entering the last possible second at 4:54. The human sum of best is merely a few frames slower than TAS. This is probably the closest against TAS in gaming history after dragster.

They represent the frontline of game optimization: it reaches the realm where inputs are almost impossible to humans, which is a mechanical problem rather than a software problem. This matches the spiral theory where software and mechanical optimizations take the role in turns.

Fortunately we also developed more tools during the years using science. Taking SMB1 as an example, in early days people experimented different tricks and do whatever is the fastest. We knew that there are shortcuts (e.g. 4-2 clips) but we didn't know how that worked but to take that as pure luck. As time passed, we started to use TAS first to get a route that works. We then refine that to "humanly possible" tricks -- after that it's speedrunners' job to execute those "humanly possible" tricks. And how refining works? Well the science of NES games and SMB1 itself is very well established, so people can calculate all the subpixels bit by bit for the possible route. If we take subpixels as a chaotic parameter as affected by the dynamics of the character, we may perform exhaustive searches around the possible routes until we found one that works for players.

Since I mentioned the science behind speedrunning, I should mention the Youtuber that does a great job on the matter. In fact, everything I wrote above is just a set up for one of my favourite comment that mentions 4 great youtubers, three of which make videos that I would watch at highest priority. Here is the comment from this video...

Remember people:
* Summoning Salt for History
* Bismuth for Science
* FlibidyDibidy for Technology
* Karl Jobst for Social Sciences