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