Saturday, 18 January 2025

Simon Marais 2024 Impression 2 + solution comments

Not sure when but they finally decided to announce the result altogether with the full problem set. As a tradition allow me to first comment on paper C which I did not get my hands on without looking at the solution, then we will wrap up with my comments to the solution.


C1. This is actually a good Q1. Algebraically less trivial but easy once you understand nature of the question. 

One direction is simply by rotational symmetry (how long since you last hear this term in college+ maths?) plus origin. The other direction? Let's cheat. All lattice points have a rational x-y ratio. Now if we rotate the square so that the slope of the sides are irrational, it is going to takes the lattice points one at a time each quadrant.

C2. uhhh...factorization?

If this is an IMO question I am 100% sure those 'bulls' would have factorize it without any problem. $f(f(r))-r$ is a polynomial of degree 9 with a very simple factor $(r-1)$. If, assuming in good will, that there are other factors in $\mathbb{R}[r]$, it should be in $\mathbb{Z}[r]$ as well. 

The leading coefficient is 8 and the constant is 25, giving us pretty restricted scope of searching. Linear coefficients didn't work, but searching the quadratic quickly gives $(2r^2-4r+1)(2r^2-4r+5)$, and the remaining polynomial clearly has no real root. 

Admittedly this is painful. So what? It really boils down to instinct -- if you draw the graph of $f(r)$ you can see it looks pretty *rotational* symmetric around $r = 1$, and substitution would verify that guess. With that in mind, we perform a substitution of $r = s + 1$ and finds the much, much simpler formula of
$f(f(r)) - r = \frac{1}{8}s(2s^2-1)(2s^2+3)(2s^4+s^2+2)$.

Notice the complete lack of odd degrees - this is a nicely odd function!

C3. A classic question? Not that I have seen it before, but certainly feels like so. 

If you know Sierpinski's triangle fractal, everything is about reciting that back onto your answer sheet because you can compute all $a_n$'s explicitly for the sum. I've only got 2 side comments:

First, do you remember the convergence in power series test at the boundary case? This is quite important in this question because you have to handle that as well. Many year 1 students don't do that, oh my.

Second, when did I first came across to the Sierpinski's triangle? Not in competitive training nor in fractal or chaos theory, but in a general education math course I had to take to fulfill graduation requirement, and I still feel guilty about taking the course and claiming the first in class.

C4. Oh GENERATING FUNCTION HELLO AGAIN.

I made a comment last year that they should stop making generating function questions as it has become a tradition and is overly predictable. On top of that once you know you use generating function there is only one way to solve the problem with no surprise at all.

Take this question for example. Would you be surprised that the ratio converges? Even without using generating functions I would not doubt about that the slightest bit. This is just not fun as a Q4.

The updated list of generating functions are now 18A4, 22C3, 23B2 and 24C4. Two damn question 4 among them. Just wow.

***

Wow when I look at the problem proposers I saw a few familiar names, more than one of them private friend of mine. But I am not going to point them out because you know, some Simon Marais questions are really bad, right?

A1. Overly trivial to comment.

A2. As pointed out, this is a simplified version of a question from a high school MO (junior level even). While the full version requires an in-depth bashing around base 3 numbers, the small parameter here does not require that. Students could simply count case by case without difficulty, and both provided solutions here did exactly that.

A3. Nice analysis assignment as I said, but thank you for laying out all the details...like an assignment handed in.

A4. Hmm. Round of applaud to this solution because it avoids my criticism against PNT related skill checking. Although the solution still uses the 'well-known' fact of $\prod (1-p^{-1})$ converging to zero which I am not sure given the level of this tournament. 

The nature of this question is that as long as the subset of integers (prime numbers here) is not sparse enough the probability will be 1. But the next question is how tight is the bound? Clearly the product $\prod (1-a_n^{-1})$ could converge to zero for some increasing integer sequence $(a_n)$. Cooperating that we might have a proper B4 level open question...

B1. Shame on me who got it wrong, and I was wrong because I didn't know I have to tap one more time at the end for the correct answer! Yes you need 4 taps to know the two boxes that contain coins, then one more tap to kill the game.

B2. Yup standard.

B3. This is the kind of abstract problem we would expect in Putnam, and nice to see that here. I wish we have more of that in the future. It's also nice to have some further comments from the proposer since it really links to higher maths...

B4. Error correcting codes! The world of coding using linear algebra and finite field has been mesmerizing, despite that everyone's onto turbo codes now days...

C1. Yes yes yes. I am glad the 'cheat' is indeed the way to go. Is it possible to construct a square that contains exactly $4n+1$ lattice points for each $n$? Possibly yes but more hassle involved. Do you remember counting lattice points from the sum $\sum [px/q]$ from the proof of quadratic reciprocity? You can do the same here although it's again faster to reside back to the slope argument: pick $(p,q)$ primes both larger than $n$, then the edge would not coincide multiple lattice points at a time (in a single quadrant) before we obtain a square containing exactly $4n+1$ lattice points. An irrational slope is just like the ratio of two infinitely large primes that does the job for arbitrary $n$.

C2. I am also aware that $f$ is increasing hence the fix point approach, but that didn't come to my mind when I typed the my impressions on C1-C4 in 30 minutes. 

I know it doesn't make sense to factorize a degree 9 polynomial, even with intuition, but I believe my second approach is sensible enough, especially when you realize that $f(f(r))-r = rg(r^2)$ for some $g \in \mathbb{Z}[r]$.

Nothing much to talk about C3. And for C4 the average score is higher than A4 and B4, and my bold guess is that a group of schools knows precisely they will get generating functions, trained well and get rewarded. 

***

And that's it!

It's been 3 months since the tournament and 2 months since I posted my first impression on paper A and B, making it very difficult for me to give a general comment.

The scope has not been changing much. We still get lots of analysis, some linear algebra (this time well-hidden like in B4), probability and game theory. I miss the calculus/numerical questions sometimes. And when are we getting true combinatorics or graph theory questions? How about geometry?

Difficulty has always been a complaint but I like the questions this year actually, B3 and C3 in particular. I really wish they put more questions like this because more often than not this is the question that separates the elites from the 'middle class', which is essential in tournaments like this.

Alas, we will see again in 9 months of time when Simon Marais 2025 arrives!

Tuesday, 14 January 2025

網絡隨心巡記(1): GDQ→片翼の田代

相信不少人都有過漫無目的在網上瀏覽的經驗吧?中文的「瀏覽」或許不夠精確,我更喜歡用英文的surf--在茫茫大海中為甚麼你就選擇了這條航線呢?我記得FBI還是CIA還是哪個組織其中一個背景測試是給你五十張字卡,要求你盡快不經過思考地說你從字卡聯想到的事物。網絡瀏覽其實有點相似,你的下一步比起深思熟慮後的淚定更像是腦袋靈光一現的連結。當你開始隨心在網絡隨波逐流,那瀏覽軌跡其實反映了更深層次的「你」。

比如說我,開古早遊戲BGM巡遊這個系列就是想懷舊。每一首挑出來的BGM都是一種連結,把過去一些回憶片段給串連起來。可是在那個系列裡面BGM畢竟是主角,我沒法扯得太遠。如果BGM不是主角,主角又會是誰呢?不是「古早」,那就只能是巡遊本身了。我決定開一個新的雜談系列,把焦點從BGM移到巡遊上面。這個系列會比古早遊戲BGM巡遊更簡短,會由一連串的瀏覽關鍵詞和這些關鍵詞的簡短雜談組成。開首結尾也省去了,隨心的行為根本不需要也不應該鋪陳。

*

1) AGDQ

每年兩次的speedrunning馬拉松。

很久以前這是我每年兩次熬夜全看的節目,可是我現在越來越懶只會補看那些我感興趣的遊戲了。一方面是因為我極少會追新遊戲,拋開我不用steam也沒PS和XBOX這點,上一次我買遊戲是西瓜遊戲、再上一次已是洛克人EXE這超級冷飯。我想看的多半是我認識的遊戲或其相關作,但很少遊戲可以出現超過一次。先不算Metroid這種GDQ傳統節目,其他遊戲只會在玩法/展示方法取得突破才會再次登場。今年就有用單一畫面直播四人同時速通SMB1的節目,這轉播技術前年就有,但這次明顯更順滑也更多花樣;類似的例子還有對應今年推出TGM4而重現江湖的TGM showblock。

2) Gimmick2

太久沒追新遊戲所以完全不知道。這他媽32年前的遊戲也能出續作啊?Gimmick是紅白機時代的傳奇,以私嵌音樂晶片達成超高質遊戲音樂加上超高難度的獨特玩法著名。也因為私嵌音樂晶片所以只在日本和北歐發行過,中文圈玩家聽過這遊戲多半是因為某過氣網紅吧?

3) Gimmick2 reactions

到底有多少人真的為這遊戲出續作而雀躍呢?……看來並沒有很多。

老任有幫這遊戲發了一個trailer。這個會是從Nintendo Direct裡面剪出來的嗎?五個月前的28/8/2024正好是Nintendo Direct Indie World的播放日子,用來介紹這遊戲再適合不過了。可惜的是我找遍日版和美版ND都沒有這遊戲,看來這trailer是單獨發出來的。不在ND上面,自然也不會有reactions。

4) Sephiroth reactions

可是我無論如何就是想看reactions,印象中印象最深刻的就是smash bros新角色登場reactions系列,當中我又在Sora和賽菲羅斯之中選了後者。

我沒有完整打過FF7,但這的確是代表我們年代的遊戲。這出場方式也太帥氣,如果有機會可以讓賽菲羅斯用刀把你挑到半空上,大概沒人會拒絕的吧?

5) One Winged Angel

說到賽菲羅斯,有人可能會記得那完美的身材和霸總般的眼神,但更多人記得的應該是片翼之天使這首主題曲。

讓我來說的話很可能要開一篇完整的古早遊戲BGM巡遊才行,在此我只說一點。那個賽菲羅斯在大亂鬥中登場的reaction mashup裡面,那些人是從甚麼時候認出賽菲羅斯的呢?沒錯,就是One Winged Angel響起之時。

6) 片翼の田代

田中是誰?別問我,問就是flash黃金時代。可以確定的是記得這位的可不只有我一位:


我小時候接觸到的flash仿太鼓遊戲系列有兩個,而且幸運地兩個都被收錄進Web Archive裡面。其中一個系列選曲明顯來自那些知名flash動畫,我記得的就是這首從One Winged Angel改編而來的One Winged Tashiro,這大概是我初次接觸One Winged Angel的契機吧。看看那精美的影片編號,1字頭的五位數耶!這是2007年上傳的,flash版本則可能五年十年前就有了。中古網絡時代留下來的痕跡已經越來越少,也就Web Archive和最最最早的串流影音還剩下來一點點。如果現在不先記錄下來的話,未來還有沒有機會突然想起翻出來還很難說呢。

*

以上就是我一次十分鐘的隨心瀏覽記錄。類似這樣的隨心瀏覽天天都有,但值得寫下來的不多。有機會的話我會繼續寫的,大概。