Friday 20 October 2023

Simon Marais 2023

Another year, another set of Simon Marais problems. Let's go! *Last edited 24/10/23 -- I added my comment on B4 which turned out nicely.

A1. Simple. The coordinates of the final point can be calculated as limit of geometric series.

A2. Quite confusing that you might waste time thinking about plane partitioning problem (aka cake cutting problem), but it's much simpler. The function $g(n)$ must be of the form of piecewisely glued $f_i(x)$. Since $f_i$'s are linear functions (or affine they call not to be confused with linear in the operator sense) it is easier to interpret convexity with positive second derivative almost everywhere. 

That is, whenever we switch from $f_i$ to $f_j$, the slope value must have gone higher for the sake of convexity. In the ideal case we can have linear functions $f_i$ with increasing slopes so that the $n-1$ intersection points between $f_i$ and $f_{i+1}$ has a natural increasing order. And to construct such example is easy: just take tangent lines from a parabola (because we are taking about positive second derivative). 

The last thing we need to show is that in such case we can skip one of the linear function and the rest could retain such structure. More precisely, suppose $f_i,f_{i+1}, f_{i+2}$ are in increasing slope. Let $(x_i,f_i(x_i))$ and $(x_{i+1}, f_{i+1}(x_{i+1}))$ be the intersection points of $f_i,f_{i+1}$ and $f_{i+1}, f_{i+2}$ respectively. Then the intersection between $f_i$ and $f_{i+2}$ is $(x,f_i(x))$ where $x\in (x_i,x_{i+1})$. This is clear because everything is continuous and almost everywhere differentiable.

The weird thing is that the question asks for smallest possible value as well...isn't it 1 unless I didn't read properly?

A3. Instinctive guess: the smallest $2k$ (or $2k+1$) such that $C(2k,k) \geq n$ (or $C(2k+1,k)$). Why? Try to look at the poset $(n,\geq)$. If you choose an element then everything above AND below it would be banned, so it's a really powerful restriction. The best choice is to choose everything from the same level. That says, we can already fit $C(2k,k)$ sets with a total of $2k$ elements. The only thing that is left to show is that we can't make $C(2k,k)+1$ such sets.

What I am thinking is much stronger: given $A_1,...,A_n$ using $k$ elements and suppose that $C(k,r)\geq n$ for some $r$. Then there exists valid sets $A'_1,...,A'_n$ so that each $A'_i$ is either a subset or superset of $A_i$, each of size $r$. Is it really possible? Probably takes pages to prove.

A4. The focus is the function $f_n(x) = \frac{(n^2+1)x^2}{x^3+n^2}$. We want to split the sequence into two parts: $n=0,1$ and the rest because the function behaves more steadily for $n\geq 2$. 

The first two iterations are simple: $a_1 = a_0^{-1}$ and $a_2 = 2a_1^2(a_1^3+1)^{-1}$, so we get $a_2 = 2a_0(1+a_0^3)^{-1}$. What's so special about this formula? Well, we claim that if $a_2>1$ then the sequence diverges. If the above claim is true then the rest is easy: $x^3-2x+1=0$ has two positive roots: $\phi -1$ and $1$, so that is the range of divergence!

The proof of the claim is also about bashing the function $f$ like $f_n(x)$ peaks at $x_n = (2n^2)^{1/3}$ and $f'_n(x)>1$ between 1 and halfway to $x_n$...complicated, but not hard.

But then I figured out the significance of $a_2$ and the perturbation $\phi -1$ only using computers but participants have to do it by hand! As for difficulty of A4 it somehow makes sense but it's a bit sad to see questions like this being the 'boss' of a paper.

B1. We have seen questions of similar style for many, many times in this competition: simple question with simple solution, worded in an abstract way to confuse people. In my words it would be like "find largest possible $|| \sum v_i||/2$". Do you understand now?

B2. Notice that the whole schedule is decided before tournament. For example the first 2-bracket is always player 1 (ranked 1st) vs 2 (let's call that 1v2). The first 4-bracket (first 2 rounds) is always 1v2, 3v4 and the winner of 1v2 plays the winner of 3v4. The same goes for 8-bracket, 16-bracket and so on. The thing is, if the expected rank of winner of the first 4-bracket is $r$, then the expected rank of the winner of the second 4-bracket is $r+4$. Since the winner of the first 4-bracket is always ranked higher than that from the second 4-bracket, we can calculate the expected rank for the winner of the first 8-bracket as well. Similar calculation repeats till the 8th round aka the final.

I don't mind repeating the calculation 8 times for 1/8 of total credits in a college math competition. But it's not fun.

B3. An intuitively true statement in linear algebra. 

WLOG assume that $A,B$ have basis $e_1,...,e_n$ and $e_{n+1},...,e_{2n}$ respectively. Since $A,B$ share no non-trivial intersection, $(e_j)$ is a basis for the whole space. For a basis $v_1,...,v_n$ for $C$, we can write $v_i = \sum a_{ij}e_j$ for each $i$. Now we look at the rank of the matrix $M = (a_{ij})_{i,j=1,...n}$ and similarly $N = (a_{ij})_{i=1,...,n, j=n+1,...,2n}$. If $M$ does not have full rank, that means a linear combination of $c_i$ is in $B$ causing contradiction. Similarly $N$ must have full rank as well. That is, we can take $c_i$'s component in $A$ as the basis for $A$ and the same for $B$. Call that $a_i$ and $b_i$ respectively then we have $a_i+b_i=c_i$ for each $i$, hence the linear dependence.

Linear algebra is just that elegant.

B4. (EDIT 24/10/23) Ok I am back to solve B4 when my friend pings me back for discussion.

Obviously, every $a=b$ pair is a solution because you can easily make up $r = (n-\sqrt{n})^{1/a}$. Next, if $(a,b)$ is a solution then so as its multiples $(ka,kb)$ because you can take $r' = r^{1/k}$. 

As a result we can now assume that $a,b$ are coprime. As $r^a, r^b \in \mathbb{Q}[\sqrt{n}]$, we know that $r\in \mathbb{Q}[\sqrt{n}]$ as well. I think this is well known -- but in case that is not, think about Euclidean algorithm (recall that a field is Euclidean...or even simpler the algorithm where you find gcd) that you can divide each other until you reach $r^1 = r$. 

For the rest see my updated post.

C1. Cover most cup by adjusting the modulo offset. No quick way to solution but to check 30 combinations...or 15.

C2. Quite disgusting in my view...but not super hard. The following should be clear once you draw the diagram:

Here red and blue are not the underlying colors but for easier reading. For odd $2n+1$, you can along the axis draw consecutive triangles, exactly half of it colored blue and half red. Above those triangles are parallelograms with slopes 1 and $(k-1)/(k+1)$ (below the diagonal line, reflect to the other side for similar result), covering both colors half each.

And for even $n$, I think similar argument gives a no but I didn't write down concretely.


Well I know most unis do not put inequalities in standard materials but this is an insult to those with competitive exposure.

Rewrite sequence as product so that we minimize $\sum x_i$ where $\prod x_i = 2$. AM-GM gives the answer $n2^{1/n}$ and it suffices to take the limit. Write $2^{1/n} = e^{\log (2)/n} = 1 + \log (2) /n + \log ^2(2)/(2n^2) + ...$ we clearly sees that $n2^{1/n}-n \to \log 2$.

Easiest of all.

C4. Hmmm chess and game theory, gonna skip this one unless I want my puzzle rating falls further tonight.


If they are not going to change their way of drafting questions it does not make sense for me to criticize from the perspective of comparing against Putnam and other major competitions. Instead I shall compare this year's problems to that from the previous years.

Q1 is what I called the "7 points to everyone" or "free points so that they come back next year" question. That's fine. All three of them serves as an appropriate free question this year.

Q2 is the warm up question. B2 is perhaps a bit too straightforward but A2 and C2 brings abstractness to quite a level. In terms of difficulty they are consistent with previous Q2s.

Q3 is the real deal usually involving very long but reasonable (cf. Q4 being overly fancy) answers. I think A3 is up to that level (or slightly lower than if we go back to the graph problems few years ago). B3 is clearly not at Q3 level and C3 is a joke.

Q4 is the really hard question. A4 is nice (the "non open question Q4 being easier"), B4 looks very niche and C4 is crazy. All three are typical.

In overall it's quite consistent against past tests all in terms of scope, difficulty, and problems that are completely messed up, although I don't have full confident on my solutions for those Q3 and 4s that I have solved given how shockingly short it is. Surely this won't be the Pacific Putnam in another 50 years, but we can at least expect a few nice problems every year.

See you in 2024.

Friday 13 October 2023

夢.十夜 (9) Fatigue






這張七星對應的是現在的爬塔活動妖精之森(The Elder Tree),顧名思義這就是一直爬塔闖關的活動。每一層都有隨機生成的怪物或寶箱,每十層和百層都有對應的中BOSS和大BOSS。此外還有一些特殊規則比如收集一些碎片通往隱藏樓層有不同的掉落和分數加成等,但其實核心玩法就是訓練活動那樣。跟訓練活動一樣每爬一層都會消耗若干體力,不同的是這裡打輸了的話玩家會掉到下一層,怪物會保持殘血而重試的時候可以呼叫好友支援。










重點是在活動七星的加持下,整個活動變成了可以無腦刷下去就能贏的遊戲。不只這樣,這活動同時也是無課玩家絕對贏不了的遊戲。縱然有複雜的遊戲機制掩護,這仍然是赤裸的P2W(Pay to Win)活動。













咖啡廳以黑色為基調將店面分割成一個個小空間,每個空間裡都以黑色金屬椅搭配木製桌子,這種對比予人一種頗為自在的感覺。縱使店裡坐了不少兩人以上的顧客,坐在獨立空間裡面我也能毫不在意地享受自己獨處的時間。店裡播放的音樂是鋼琴版的Speak Softly, Love,原曲的那種厚重感被爵士節奏重構成一首輕快的小曲。不過能認出這首的顧客應該不多,大概是店主或者店員的口味吧?


我一邊一小口一小口地品著咖啡,一邊百無聊賴地在手機上滑著。如果不玩逆戰幻想,那我還可以玩甚麼呢?把Play Store裡面的營收排行榜拉出來看,逆戰幻想排在第五名。除它以外榜上並沒有太多社交式網遊,更多的是靠著社交平台傳播但本身沒有社交功能的小遊戲。比如某個把三消糖果的闖關遊戲,只要在facebook上求助就能收到體力的設計深得中年大叔大嬸的喜愛,輕鬆讓他們真的很需要過關時掏出錢包買那些貴死人的道具。又比如那個推銀機,單是可以不用錢在家裡玩這點已經吸引無數玩家,然而他們不知道的是他們所看的廣告已經讓開發者賺得盆滿砵滿了。


































回到主人身邊 等待第二朝的到來




祭典之後 百年之約即將完成
在血池之中 等待第二朝的到來









首先一個倒了的遊戲(連遊戲公司都改行了)實在沒甚麼好忌諱的,當然我不認為裡面有甚麼冒犯性的內容。對整個遊戲的評價我留到整篇收尾再講,但我想起坂口博信講到FF當初命名問題的報導:當初的FF本來是想叫Fighting Fantasy,後來因為商標問題而只能改成Final Fantasy卻造就一代經典。這個遊戲的中文名字逆戰幻想直譯自日文,好端端地硬要改成終戰也太奇怪了。



第一、「草藥獵人」瑪喬(Marjoram)這張卡,其實是我私心加進這個活動裡的卡片。在現實中它屬於「Mandragora March!」的活動卡片,這個是「萬聖Parade」外另一個帶我進坑和認識miso老師的訓練活動。不過章節所限我已經沒地方寫這個活動了,所以決定以這個形式把這張卡插進來。




最後說到那些刷榜玩家我想起一個類似的例子:偶像大師星光舞台(Im@s Cinderella Girl Starlight Stage)。不知是哪個喪心病狂發明了打音遊刷分的活動,而且稱號之類的獎勵只限前三甚麼的,於是激起了玩家之間慘烈的競爭……前幾名幾乎是七天二十四小時刷分,刷分的歌曲難度高但準確度不能掉。這種刷分法連Osu分數榜的觸手(望)都甘拜下風好嗎?最後他們通通筋膜炎入院就是。