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