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.