Some CTST rewrites

(David here.) Here's a more frivolous topic for this week: have you ever read a problem and just felt like it was way too convoluted?

Well, me too. In my memory, the biggest offenders were often the contests coming out from China, especially the Chinese TST. At the same time, there are often some very interesting ideas hidden beneath in the solutions that are worth exploring. So for this article I decided I was going to look at the 2024 Chinese TST and rewrite and try my best to rescue rewrite the problems as best as I can.

So what makes a "good problem"?

There are many dimensions to this question, but primarily we'll consider the aesthetics here, since our original complaint was about convoluted-sounding problems. (And hence "frivolous", because this doesn't really affect the problem solving itself.)

I'll boil it down to three questions:

• Is the problem too complex for me to hold in my head?
• Does the statement present as either natural/surprising, or is it unclear?
• Does the statement naturally conclude from the proof?

Needless to say, these aren't going to always hold (for example, it's approximately social convention at this point that geometry questions are just glorified puzzles of some sort and don't have to be "mathematically interesting" for the most part), but they're useful working principles as we tear up rewrite the problems.

2024 CTST Q1

Q1. It is known that each vertex of the convex polyhedron $P$ belongs to three different faces, and each vertex of $P$ can be dyed black and white, so that the two endpoints of each edge of $P$ are different colors. Proof: The interior of each edge of $P$ can be dyed red, yellow, and blue, so that the colors of the three edges connected to each vertex are different, and each face contains two colors of edges.

The first purely aesthetic change I would do is to use graph-theoretic language, since it's really contributing to the wording bloat.

V1. A convex polyhedron $P$ has three faces meeting at each vertex. Suppose that the edges form a bipartite graph. Prove that the edges can be properly 3-colored such that each face only has two colors of edges along its boundary.

Well, we can imporve this slightly, by noticing that the bipartiteness of the edge graph is quite easily equivalent to each face having an even number of sides. And we can equivalently color the faces by coloring it the same as the edge "opposite" to it.

V2. A convex polyhedron $P$ has three faces meeting at each vertex, and each of its faces has an even number of sides. Show that the faces can be properly 3-colored.

According to an AoPS user on the thread, this is a result of Steinberg 1993 ("Any cubic map where each region has an even number of neighbors can be colored using 3 colors.")

I think I'm happy with the problem at this point, even though maybe it has become slightly easier with the simplifications.

CTST 2024 Q3

Q3. Given positive integer $M.$ For any $n\in\mathbb N_+,$ let $h(n)$ be the number of elements in $[n]$ that are coprime to $M.$ Define $\beta :=\frac {h(M)}M.$ Proof: there are at least $\frac M3$ elements $n$ in $[M],$ satisfy $$\left| h(n)-\beta n\right|\le\sqrt{\beta\cdot 2^{\omega(M)-3}}+1.$$ Here $[n]:=\{1,2,\ldots ,n\}$ for all positive integer $n.$

Can we do better? Maybe it looks nicer using the asymptotic form? Using the fact that $2^{\omega(M)} \ll N^\epsilon$, we could write

V1. Let $M$ be a positive integer, and let $\beta = \frac{\varphi(M)}{M}$. We say that $n$ is good if the number of integers between 1 to $n$ coprime to $M$ is within $M^{0.01}$ of $\beta n$.

For all sufficiently large $M$, show that at least 0.99 of the numbers between 1 and $M$ are good.

Actually the solution proceeds by a probabilistic-like argument to compute the second moment identity

$$ \frac{1}{M}\sum_{n=1}^{M}\left(h\left(n\right)-\beta n\right)^2=\left(\frac{1}{12}2^{\omega\left(M\right)}\beta+\frac{\beta^2}{6}\right) $$

This means that for a uniformly selected $n\in [1, M]$, $\varphi(n)$ "concentrates" around $\beta n$.

We might as well go for the "probabilistic" allegory with this:

V2. Let $M$ be a positive integer. If $h(n)$ is the number of integers between $1$ to $n$ which are coprime to $M$, show that $$\max_{n\le M} \left|h(n) -\frac{\varphi(M)}{M}\cdot n\right| \le M^{0.51}$$ for all sufficiently large $M$.

For comparison, if $h(n)$ was instead the partial sum of random $\pm 1$ variables, this would be $\tilde\Theta(M^{1/2})$ with high probability (that is, within logarithmic factors of $M^{1/2}$).

We can push this number a bit lower by also observing that $h(n)-(\varphi(M)/M)\cdot n$ can only change by less than $n$, so we can in fact get the RHS bound down to $M^{1/3 + \epsilon}$. But really, we should be able to do a much better job because we know roughly what the structure of the problem is. For example, suppose we replace $M$ with $M^2$. Then, because the coprimeness repeats between $[1,M]$ and $[M+1,2M]$ and so on, we should really expect that this maximum doesn't go up.

Maybe it's suprising in the first place that this value can deviate significantly in the first place.

V3. Let $M$ be a positive integer. If $h(n)$ is the number of integers between $1$ to $n$ which are coprime to $M$, show that $$\max_{n\le M} \left|h(n) -\frac{\varphi(M)}{M}\cdot n\right|$$ is unbounded in $M$.

I suppose this variant can probably be done inductively without directly computing the second moment, so it's probably way easier now.

Certainly, if I knew that this maximum was at most $c\cdot \sqrt{2^{\omega(M)}\beta}$, I would propose that instead of V2, but I haven't managed to prove it.

CTST 2024 Q12

Q12. Given positive odd number $m$ and integer ${a}.$ Proof: For any real number $c,$ $$\#\left\{x\in\mathbb Z\cap [c,c+\sqrt m]\mid x^2\equiv a\pmod m\right\}\le 2+\log_2m.$$

This one's easy: we use actual words.

V. We call a number $x$ a square root of $a$ modulo $m$ if $x^2 \equiv a \pmod m$. Show that for any integer $a$ and odd $m$, among any $\sqrt{m}$ consecutive numbers there are at most $2+\log_2 m$ square roots of $a$.

I saw a pretty incredible proof in the forum thread - apparently, the $\log$ term comes from geometric facts!

CTST 2024 Q23

Q23. $P(z)=a_nz^n+\dots+a_1z+z_0$, with $a_n\neq 0$ is a polynomial with complex coefficients, such that when $|z|=1$, $|P(z)|\leq 1$. Prove that for any $0\leq k\leq n-1$, $|a_k|\leq 1-|a_n|^2$.

The first trick used is actually to flip the problem around, which makes for a 100% more natural problem anyway.

V1. Let $P$ be a polynomial with absolute value at most 1 on the complex unit circle. Prove that except for the constant term, every other coefficient of $P$ has modulus at most $1-|P(0)|^2$.

There are a few ways to play around with the statement here. One of them is the scaling of $P$ (i.e. we explicitly use $C = \max_{|z|=1} |P(z)|$ to make the result "homogeneous"). However, this is really weird because we end up with quadratic terms.

Another idea is to consider $\lambda P + (1-\lambda)Q$ for a different polynomial $Q$ which is also absolute value $\le 1$ on the complex unit circle, but we won't get anything interesting with this, since if the coefficients are $P(z) = c_0 + c_1z + c_2z^2 + ...$, then $|c_0|^2 + |c_k|$ is a convex function of the coeffficients.

A final remark is that this is actually "tight"! Consider $$P(z) = \frac{z^n + c_0}{1 + \overline{c_0} z^n} = c_0 + (1-|c_0|^2)z^n + ...$$

which can be checked to be at most 1 whenever $|z|\le 1$. So really this fact can be chalked up to a certain conformal transforms that preserve the unit circle. (Which is a pretty crazy thing to see in an olympiad problem!)

If that's too much, we can also just peg $P(0) = 0$:

V1. Let $P$ be a polynomial with absolute value at most 1 on the complex unit circle and $P(0) = 0$. Prove every coefficient of $P$ has modulus at most $1$.

but this ends up being a 1-trick problem (where the trick is extracting coefficients from values of the polynomial along the unit circle).

Epilogue

I'm pleasantly surprised by some of the solutions - the CTST this year seems to try to incorporate many of ideas from math in general.

To be honest, I don't think any of these rewrites so far took much of effort to do, so maybe this year's CTST is actually decent. On the other hand, some of the really bad ones require really looking at the solution or solving the problem myself (e.g. Q14, which has a double quantifier), which I didn't have time to get into. Maybe doing CTST 2015 might have been more interesting for this purpose.

I once had a grand fantasy where we would be able to curate and rewrite most country olympiads so that we can get a larger question base. Of course, that's ambitious, but I think from this little exercise we see that it should be possible to get tons of semi-original problems for various purposes (ahem SMO).

To other x-men: maybe we can have a livesolve/rewrite session sometime soon? Stay tuned!