Whew it's finally arrived.
The tournament was on Oct 11 but I tried not to disclose the problems before I could find them somewhere else on the net. Last year it was quick as someone uploaded part of it to AoPS, but that didn't happen this year. Perhaps it's due to low popularity for the questions posted? I don't know. When I tried to write comments almost 3 weeks later I find it quite difficult when I have forgotten everything.
Welcome to my brief comments 2025 edition. Expect that to be brief, focusing on my thoughts more than the problem/solutions themselves as I tried to wrote everything in like 60 minutes...
A1. A well-received intro question. We don't really need those ordinary computational question, we need questions that truly takes a bit of mathematical essence to solve (but not too much). What is the essence we need for this question?
Growth rate.
Since all functions are positive here (do not matter too much actually), a higher degree polynomial will always outrun lower ones eventually regardless of the coefficients. Since $f = O(x)$, we know that it can only be matched piecewisely by linear functions, but the curve of $x^2$ cannot be reproduced by piecewise linear functions (proof? That's exercise).
A2. Well I am confused here. What do you mean by average? Are you sampling uniformly or what? In that case I think it shouldn't be too hard since matrix like that is all over classic coding theory. I can't give a detailed comment just because I do not bother to delve deeper with the question written so badly.
A3. Wow. At the first glance I thought $A^k$ retains the one row at the bottom -- in that case it should be a straightforward simple induction problem. But fortunately no, this is as hard as an A3 should be. To show that $f,g$ has full distinct real root I tried of Sturm's theorem, but that turns out to be troublesome when you can't even verify if the polynomials are square free. I was so desperate but then I looked at the recurrence relation again: $f_{k+1} = (2+t)f_k - f_{k-1}$
Che...by...shev...?
I remember this guy('s polynomial) only because I wrote about elementary trig limit squeezing one month ago when I tried to expand $\sin nx$, but I am ultra surprised to be able to use that again so soon, just like how I used Galois twice in a row.
More precisely, we can transform the recurrence relation of $f$ into the standard form for Chebyshev polynomial of $T_{n+1} = 2xT_n - T_{n-1}$ with proper initial values. With $T_{k}$ associated with trigonometric function of frequency $\frac{2k+1}{2}$, it is not surprising that it yields full distinct real roots. On the other hand, $g$ can be resolved similarly into another trigonometric expression, then the existence of full distinct real roots plus the ordering is clear immediately.
I wonder if there are other solutions. Chebyshev sounds like too nasty as the only trick forward...
A4. Fourier?!? Everything screams about Fourier approach when it is frequency related. I thought for a while but couldn't come up with a solution in that way, so let's head back to the key element of the problem: finite dimensional space.
Think about the algebraic basis (i.e. allowing infinite linear combination) of $\left\{ 1, x, x^2, ...\right\}$ which we call a Taylor expansion. What if we double the frequency? It sends $x^n \mapsto 2^n x^n$. If a non-polynomial function $g$ admits a Taylor series then the set $\left\{ T^ig \right\}$ *might* have infinite dimension. Of course we would run into the rabbit hole by expanding the *might* argument going through argument involving infinite, so the best approach is to work on the other side instead. That is, to play with finiteness.
Let $T\in L(V)$ be the frequency doubling operator. We know that $T$ is a bijection. Since $V$ is finite dimensional, $T$ has a matrix representation with respect to a given basis. More importantly we can use Cayley-Hamiltion so that there exists coefficients $c_i$ such that $\sum c_iT^i = 0$. That says for every $g\in V$, $\sum c_iT^ig = \sum c_i g(2^{i-1}x) = 0$. That alone, proves that $g$ has to be a polynomial -- the Taylor series of $g$ solves $c_i$ since $[g]_{V\to V}$ for canonical basis $V$ defines $g$. Using growth rate again one eliminates the tail and confirms the claim.
B1. Surprisingly 'complicated' as a Q1 with how it was worded. For once I thought that it should be possible for all $n$, but more detailed investigation proved otherwise. Focus on the jam when non-coprime numbers are forced to map to the same number. What are the largest possible non-coprime pair given $n$? It should be simple enough from here.
B2. Remember how a triangle is defined by two vectors? Any polygon can be triangulated and decomposed into these vectors. Convexity is important to ensure validity of the triangulation which in this case is given. You don't even need to know much about affine geometry, even simple vector calculus would do.
I wonder why is it not for convex $n$-gon. A quadrilateral is certainly too easy for a Q2.
B3. Nice problem on linear algebra and complex number. It looks really scary with all the powers, but it's not that bad if you calm down. To me, B1, B2 and B4a (see below) are really manageable, meaning you get 2 hours+ for B3. Even better, there isn't much calculation or bashing -- you realized it's impossible to expand those brackets anyway. Everything is so symmetric and neat, all you need is the right idea.
Since the determinant is zero, there exists a non-zero (real) linear combination $\sum c_k (z_j - \omega ^k)^n = 0$ for each $j$. That is, the polynomial $f(z) = \sum c_k (z - \omega ^k)^n$ has $n$ distinct roots $z_i$. Since $f$ is of degree $n$ we know these are all the roots with $\sum c_i \neq 0$, but we need to ensure that $f$ is non-zero.
Suppose $f = 0$. That means the coefficients of $1,x,...,x^{n-1}$ gives $\sum c_k \omega ^{kr} = 0$ for $r = 0,...,n-1$. Notice that this is equivalent to the linear combination of rows in the Vandermonde matrix that sums to zero. Since the Vandermonde matrix is invertible, that means $(c_i) = 0$, a contradiction.
Now, by factor theorem we conclude that $f(z) = (\sum c_k)\prod (z-z_k)$. Comparing the constant term at $f(0)$ we get $\sum c_k(-\omega ^k)^n = (\sum c_k) \prod (-z_k)$, hence $\prod z_i = 1$.
See? Almost zero calculation. Grab the essence of linear algebra and you will reach the conclusion easily.
I am actually quite surprised that the root of unity is only used at the Vandermonde argument as well as the vanishing part at the end. Is it possible to generalize this beautiful result?
B4a. I would rate this at Q2 difficulty, but this is consistent vs past B4a problems.
First of all, $q = 1$ is the trivial case, yet very easy to miss out. After that we look into higher order solutions.
Assume $q \geq 3$. Notice that $(x+1, x^2+1) = 2$, meaning that they do not share any other prime factors. This is extremely powerful because now you know they must contain high prime powers on their own, which is very difficult.
Suppose $(x+1, x^2+1) = 1$, then $x+1 = a^q, x^2+1 = b^q$ for some $(a,b) = 1$. But then we know $(a^2)^q - b^q = a^q$. The difference between two q-th power cannot be that small. Some simple bounding gives the conclusion of no solution. Similarly for the $(x+1, x^2+1) = 2$ we know that $\nu _2(x^2+1) = 1$ by checking mod 8 so all other factors of 2 were on the $x+1$ side, and we get the same conclusion similarly.
b. Well the structure of on the LHS is completely broken in the generalized case. The structure of (a) completely relies on the factorization, or equivalently the factoring or $n+1$. Are there even results that are general across all $n$?
Interestingly (a) didn't ask about the case $q = 2$, but then you realized they didn't forget about that, instead asking that in (b). Perhaps the committee believes that the case for odd $q$ (or simply, $q = 1$ and $q \geq 3$) is enough for 7 marks in Q4a?
The case $q = 2$ is where you can actually get solution via Pell's equation which is rather standard. One may argue as above that you do not get solution due to wide gap for large $x$, and below the bound there are two solutions $(x,y) = (1,2), (7,20)$.
C1. Oh a partition problem! Not the NP-complete one you would have expected, this partition is very straightforward.
C2. It sounds like the difficult variant of B4 (by the way, the variant of B4 for rational solution sounds really interesting although I believe the answer is still no solution for $q \geq 3$...), but no. This is a monovariant quartic equation. All you need is to check the determinant so this is not very fun.
A funnier question would be: which one fits better as a Q1 problem, C1 or C2?
C3. Answer must be no right? I'd imagine a very simple expression should the answer be yes. Kind of a typical scope defining question. It should be doable as long as you extract some invariant among all possible angelic expressions. For example the change in slope? For the monovariant case you can define the change in slope by $\lim _{x \to a^-} f'(x) - \lim _{x\to a^+}f'(x)$. For example, the change in slope of $|x|$ is 2 at $x = 0$ and zero everywhere else. This is unchanged by applying any other operations. You may think about $|x|+x = 2\max (0,x)$ but no, the change in slope is still 2 -- don't forget constants and division are not allowed here!
And, we just need to generalize the above to higher dimensional and work very carefully. Perhaps the oscillating measurement $osc(x) = \lim _{r\to 0} \max _{u,v \in B_r(x)} \| \Delta f(u) - \Delta f(v)\|$? I feel like there are lots of traps here, but it's not extremely difficult.
Still harder than the insulting 24A3 and 23C3 though.
C4. The old skill checking problem is back.
If this is a question on a convex analysis course, it would have been a standard tutorial or assignment question with answer within 5-10 lines using convex conjugate and infimal convolusion. For those without exposure to convex analysis result? Well, good luck. I have zero idea how to do that without it.
I have exposures to convex analysis because, out of all, I call myself an analysis specialist. I spent time on convex functions from topics related to harmonic functions. On the other hand, I can hardly imagine anyone else, let alone just undergraduates, to run into such topic. Who the hell's going to study convex analysis out of nowhere?!?
***
Man I feel much better about the problems this year. Less fancy but stupid intro questions, more actual problems that are precise and elegant, demanding depth rather than plain bashing. This is also a year without generating function finally lol.
Yet I still feel like something is off. It is so analysis biased, and I am saying that as an analysis guy. Any algebra and probability (other than the so absurd A2)? Any actual calculus? Graph theory, combinatorics and game? I am always amazed by how Putnam comes up with questions with such short description and solution yet so deep that almost no one solves it. Simon Marais is making good progress towards that.
An additional remark about LLM performances. Gemini and GPT managed to solve most of them but both with obvious gaps occasionally. Grok is so messed up even with the ability to cheat (search online). Below are some quick comments about their performances:
A3. The bad habit of assuming pattern is exposed in A3 where they assume something is true after looking at a few lower cases, they can only answer after you instruct them to solve a single specific step -- to solve the recurrence relation of $f_k$ in this problem.
A4. This is very hard. They can come up with the linear combination $\sum c_i T^i = 0$ but the rest is a huge hurdle. It is not easy to set up an analytical goal then to solve it.
B3. Well done without much problem, guess this is pretty standard.
B4. Similar to A3, easily purged conditions that are far from clear. Only one of them managed to get multiple solutions for $q = 2$.
C3. Unsurprisingly worst of all. Expression type of problem are usually much deeper than how they are defined, and clearly the LLMs are merely scratching the surface. They exhaust obvious cases, but none of them even got close.
C4. Since this is a skill check, if you know the trick then you can solve without problem. Clearly one or two model know the trick, and the rest do not.
What can we learn from the LLM performances? Well, they can calculate and prove quite well, but they really suck at inventing new tools to deal with existing problems. At least up to now.
And that's another year of the tourney! What do you think about the problems? Please tell me with comments below and we will see again in 2026/when answer's out!
