## 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.

C3. EXCUSE ME WHAT?

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

*

「沒事，我進來找朋友。」一把不能再熟悉的聲音從後響起。接著是一陣從遠到近的腳步聲，然後一隻手輕輕地搭在肩膀上：「小紅對不起，我來晚了。」卡羅一派輕鬆地說道。店員看我沒有反應便放下餐單隨他拉開椅子座下，他很快就點了自己想的東西。我沒有抬頭望他，只是死死盯著自己的咖啡，怕自己會被他像雷伊一般的眼神勾去。

「真是～好久沒見了呢。」

「好幾次問你是不是在跟著我你都說只是碰巧，這次被抓了吧。」

「真的沒有啦，你要聽聽看我的推理嗎？」

「我想你應該暫時不會去那些『我們』平時會去那個咖啡廳和機廳了吧。」他特別強調了我們兩個字：「機廳附近就這麼一家，所以我就從咖啡廳裡下手。從你對茶和其他飲料的喜好來看，你應該比較看重飲品的香氣。正好這家開張不久的店其實還有本店而我剛好去過，他們常設三四種豆供客人挑選這點我印象蠻深刻的。我在想說不定你會過來，於是就來碰碰運氣囉。怎樣？」

「……勉強說得通吧。我不介意你坐我對面，安靜吃完就滾吧。」

「不要這麼冷淡嘛，難得再會讓我請個客不是理所當然嗎？」

「謝謝，一杯咖啡我還是喝得起的。」

「真是……」他雙手枕在桌子上向前滑，那張臭帥臉還是出現在我的視野之內：「難道你完全不對我和她的過去感興趣嗎？那天當你得知我們是舊交以後你幾乎立即就跑掉了，總覺得你誤會了甚麼，所以我才一直想找你解釋一下。」

「哈？為甚麼我要對你們的私事感興趣？！？」

…………
………
……

「所以說我們真的不是你想關係。只要你能相信這一點，今天我就不枉此行了。」他一口氣把故事說完連忙拿起已經送到桌上的expresso猛灌一口，然後拿叉子把另外點的巴斯克芝士蛋糕割了一塊下來，叉子指向我道：「要不要試一口？」

「……就一塊，我自己來。」他居然剛好在我喝咖啡的時候開始描述蛋糕的口感，實在太可惡，我搶在他之前把叉子搶過來把蛋糕放入嘴裡。清爽的芝士加和藍莓乳酪的確十分相襯，不過乳類香味終究十分容易蓋過咖啡的花蜜香，我十分慶幸剛才沒追加甜點。

「當然，說沒有的話你也不會相信－－我是代表他們來問候你，看看我們有沒有能幫的上的地方。」他看準我在心情高點之際拋出這個敏感的話題。

「也沒有，單純開始覺得厭倦罷了。作為一個雙子，貪新厭舊也是十分正常的吧？」

「可是，我覺得你是被上次的活動養大了胃口？」

「啊哈哈怎會呢。那些活動獎勵我都還給Alex和熊熊了，我頂多就是個代打的。」

「我可是從他們口中聽到你硬要把活動紅利送給他們呢。或都說，你覺得再多的計謀在強大的課金力量前都不值一提吧？」

「……」

「應該就是這樣沒錯了。這也難怪你，難得找到喜愛一款遊戲的切入點卻被告知自己的努力其實毫無價值，這樣的打擊很大吧？」

「因為……大家都知道市場很小，一起上的話就變成大家都無利可圖了？」

「其實不用想太多。在我看來，要不要課金在於你怎樣看待這個遊戲而已。當初你覺得策略可以改變命運，於是拼命參加活動將所有東西精算到極致，這是你熱愛這遊戲的原因；後來你又覺得再多的策略也比不過金錢之力，改變命運之類的通通都是騙人，於是一瞬間失去所有興趣甚至變得抗拒，這也是十分自然的事。你應該問自己的是，這真的是你想法的全部嗎？」

－－「惡夢」吸血鬼。由遊戲主催之一、擔任過FF美術的繪師繪製。復古的畫風除了色色元素以外該有的威嚴和氣勢都有了。

「嗯沒錯，這張卡片是當時小雨托你的福衝進一千名拿到的獎勵。你來看看卡片的簡介？」

「以血為證，展現我的忠誠」－－

「開頭的句子跟人狼(Werewolf)一樣？」

「嗯，」他打開瀏覽器給我看：「你再看看同一張卡其他語言的版本。」

「血的誓言，血的契約」

「以血為證，展現我的忠誠」－－

「有沒有發現，每個版本都有一點差異呢？但如果你把卡片附上的故事打開就能發現，其實幾個版本都沒有錯。大概是不同地區的譯者選取了故事裡不同重點放進簡介裡面，就像寵物小精靈(Pokemon)不同版本對精靈也有不一樣的簡介互補。只要交叉檢查一下，就算不看故事也能大概知道其詳細背景，這也算是收集卡片的的樂趣之一吧。」

***