High School Olympiads, Part 1

Published Jun 1, 2024

Here are some math olympiad problems I solved in high school, sometimes with remarks and commentary. This is part one, I will publish more problems and solutions over time. There might be a lot of parts… These are mostly solved during 2021-2024, and I will somewhat publish problems in chronological order of when I solved them but not really.

Problem 1, USAMTS 4/1/31

A group of $100$ friends stands in a circle. Initially, one person has $2019$ mangoes, and no one else has mangoes. The friends split the mangoes according to the following rules: sharing: to share, a friend passes two mangoes to the left and one mango to the right. eating: the mangoes must also be eaten and enjoyed. However, no friend wants to be selfish and eat too many mangoes. Every time a person eats a mango, they must also pass another mango to the right. A person may only share if they have at least three mangoes, and they may only eat if they have at least two mangoes. The friends continue sharing and eating, until so many mangoes have been eaten that no one is able to share or eat anymore. Show that there are exactly eight people stuck with mangoes, which can no longer be shared or eaten.

—USAMTS 4/1/31

Solution 1

Index the friends from 0 to 99 clockwise around the circle and let $f_{m, i}$ denote the amount of mangoes the $i$th friend has after $m$ moves of sharing or eating. WLOG $f_{0, 0} = 2019$.

Lemma

For any nonnegative integer $m$, $\sum_{i = 0}^{99} 2^i f_{m, i} \equiv 2019 \pmod{2^{100} - 1}$.

Proof of Lemma. We proceed by induction. The base case $m = 0$ is trivial. Consider having friend $a \in \{0, 1, \dots, 99 \}$ share or eat their mangoes on the $m$th move. If they share, (here in any term $2^i f_{m, i}$ we always take $i$ modulo 100)

If they eat,

We need the modulo $2^{100} - 1$ to account for boundary conditions when $a \in \{0, 99\}$. And thus the lemma is true after move $m$. $\square$

Now, if no one is able to eat or share after move $n$, everyone must have exactly one or zero mangoes.

Where $f_{n, i} \in \{0, 1\}$. Clearly then $S = 2019$. The base 2 repesentation of $2019$ contains 8 digit ones. Hence there must be exactly eight people with mangoes as desired. $\blacksquare$

Remark 1

I remember spending a lot of time on this and was very satisfied with finding the idea.

Problem 2, 1999 Romania TST P4

Let $x_1, \dots, x_n > 0$ be positive reals satisfying $x_1 \dots x_n = 1$. Prove that

$$\frac{1}{n - 1 + x_1} + \frac{1}{n - 1 + x_2} + \dots + \frac{1}{n - 1 + x_n} \le 1.$$

—1999 Romania TST Problem 4

Solution 2

$n = 1$ is trivial. Henceforth we assume $n \geq 2$. This looks like $\sum f(x_i)$ and ideal for Jensen/Karamata, but unfortunately we don’t have $\sum x_i$ as a condition, but $\prod x_i$ instead.

Let’s force a sum condition by taking logarithms! Write $y_i = \ln(x_i)$ and $f(x) = \frac{1}{n - 1 + e^x}$. Then we wish to prove, subject to $\sum y_i = 0$,

Of course, we now consider the convexity of $f$.

$f$ has only one inflection point, namely $x = \ln(n - 1)$. We are in perfect condition to apply the $n - 1$ EV principle. We prove that there exist reals $z_1 = z_2 = \dots = z_{n - 1}$, $z_n$ also satisfying $\sum z_i = 0$ such that $\sum f(y_i) \le f(z_i)$.

If one or less of $y_i$ lie in $(\ln(n - 1), \infty)$, we are done by Jensen’s Inequality on the rest of $y_i$. Then assume for $k \geq 2$ and $y_i$ nonincreasing, exactly $y_1, y_2, \dots, y_k$ lie in $(\ln(n - 1), \infty)$, where $f$ is convex. Set $t_n = y_1 + y_2 + \dots + y_k - (k - 1)\ln(n - 1)$ and $t_1 = t_2 = \dots = t_{k - 1} = \ln(n - 1)$. Note $(t_n, t_1, t_2, \dots, t_{k - 1}) \succ (y_1, y_2, \dots, y_k)$ and by Karamata’s Inequality,

Hence by Jensen’s,

So we are done setting $z_n$ accordingly.

Now without loss of generality, we may assume $y = y_1 = y_2 = \dots = y_{n - 1}$, and note $y_n = -(n - 1)y$. It remains to prove

Which is immediately obvious by Weighted Power Mean. $\blacksquare$

Problem 3, ISL 2004 A5

If $a$, $b$, $c$ are three positive real numbers such that $ab+bc+ca = 1$, prove that

$$\sqrt[3]{ \frac{1}{a} + 6b} + \sqrt[3]{\frac{1}{b} + 6c} + \sqrt[3]{\frac{1}{c} + 6a} \le \frac{1}{abc}.$$

—IMO Shortlist 2004 A5

Solution 3

We wish to prove

By Cauchy’s,

By Holder’s,

It remains to prove $(abc)^3(a + b + c) \leq \frac{1}{81}$ Which is clear by the identities $(abc)^2 \leq (\frac{ab + bc + ca}{3})^3$ and $3abc(a + b + c) \leq (ab + bc + ca)^2$. $\blacksquare$

Remark 3

I remember being really tired but doing this in 10 minutes on my bed somehow. It’s a good problem to test algebraic intuition, maybe kind of easy for A5.

Problem 4, CMO 2018 P3

Two positive integers $a$ and $b$ are prime-related if either $a/b$ or $b/a$ is prime. Find all positive integers $n$ with at least three divisors for which it’s possible to arrange all the divisors of $n$ in a circle, so that any two adjacent divisors are prime-related.

—Canada MO 2018 Problem 3

Solution 4

We claim that the solution set is all positive integers $n$ not a perfect square or a prime power. Call a valid configuration of $n$ a circle expansion of $n$, a tuple $(d_0, d_1, \dots d_m)$ going clockwise around the circle where $d_i$ are the distinct divisors of $n$ and $\frac{d_{i + 1 \mod m + 1}}{d_i} \in \{p, \frac{1}{p}\}$ for all $i \in \{0, 1, \dots, m\}$.

We first show that $n = p^a$ is not circle expandable for some prime $p$ and positive integer $a \geq 2$. Consider $1$ on the circle. WLOG $p$ is adjacent to $1$ in the clockwise direction. Then note, $p^2$ must be adjacent to $p$, and in general $p^k$ is adjacent to $p^{k - 1}$ in the clockwise direction. However, that means $p^a$, after wrapping around the circle, is adjacent to $1$. Contradiction. We also show that $n = \prod_{i = 1}^k p_i^{a_i}$, for distinct primes $p_i$ and positive integers $a_i$, fails when $2 \mid a_i$ for all $a_i$. Note that there are an odd amount of divisors on the circle, each $\prod_{i = 1}^k p_i^{b_i}$ for some distinct tuple of nonnegative integers $(b_i)_{i = 1}^k$. Then consider $\sum_{i = 1}^k b_i$. Starting at $1$, the sum is 0, and increases or decreases by 1 for each clockwise adjacent divisor. Since there are an odd number of divisors, the divisor adjacent to 1 counterclockwise must have an even $b_i$ sum, impossible if it is a prime, contradiction.\ \ Now we prove that all $n$ with more than one prime divisor and not a perfect square works. Then we can write $n = p^a \cdot k$, for some prime $p$, odd integer $a$, and positive integer $k \geq 2$ such that $p \nmid k$.

Lemma

Any positive integer $k \geq 2$ can be weak circle expanded, or have its divisors be written as a tuple $(d_0, d_1, \dots d_m)$ where $\frac{d_{i + 1 \mod m + 1}}{d_i} \in \{p, \frac{1}{p}\}$ for all $i \in \{0, 1, \dots, m - 1\}$.

Proof of Lemma. Note we can weakly circle expand $q^b$ for prime $q$ and positive integer $b$ into $(1, q, q^2, \dots, q^b)$. Now assume we can weakly circle expand $k$ and we prove that we can also weakly circle expand $k q^b$ where $q \nmid k$, which will finish the proof by the Fundamental Theorem of Algebra. Consider a weak circle expansion $A = (1, \dots)$ of $k$ and let $B = (\dots, 1)$ be $A$ reversed. Note $A + qB + q^2 A + \dots + q^b X$ is a valid weak circle expansion, where $+$ denotes tuple concatenation, multiplication denotes tuple scaling, and $X$ is $A$ or $B$ when $b$ is even or odd, respectively. $\square$

Then weakly circle expand $k$ into $(1, \dots)$ and let $A = (\dots)$ denote the expansion without the 1 (note the expansion of $k$ contains two or more divisors), let $B$ be $A$ reversed, and note that

Is a valid circle expansion, where $+$ denotes tuple concatenation, and multiplication denotes tuple scaling. $\blacksquare$

Problem 5, China MO 2019 P1

For real numbers $a,b,c,d,e \ge -1$ satisfying $a+b+c+d+e = 5$, determine the minimum and maximum possible values of

$$S = (a+b)(b+c)(c+d)(d+e)(e+a)$$

—China MO 2019 Problem 1

Solution 5

The maximum is 288 and the minimum is $-512$, with equality at $(-1, -1, -1, -1, 9)$ and $(-1, -1, -1, 4, 4)$ respectively. Let $(x_1, x_2, x_3, x_4, x_5) = (a + b, c + d, e + a, b + c, d + e)$. The conditions become $\sum x_i = 10$ and $x_i + x_{i + 1} \leq 6$ (cyclically), where $\prod x_i = S$. We can assume none of $x_i$ are zero. First we prove that

We only need to consider the cases where an even number of $x_i$ are negative. If it is zero,

If it is two, note that $x_i \geq -2$. There must be two cyclically consecutive positive $x_i$, so that their sum is at most 6 and product thus at most 9. The last $x_i$ is clearly at most $8$, since $x_i + \leq 6 - x_{i + 1} \leq 6 - (-2)$. Hence,

If four are negative, the last one is at most 8, and $\prod x_i \leq (-2)^4 \cdot 8 < 288$ Now to prove the lower bound, we only consider when one or three of $x_i$ are negative (five is impossible). If it is one, WLOG $x_1 < 0$,

If it is three, each of the other two $x_i$ are at most 8,

And we are done. $\blacksquare$

Remark 5

I remember someone saying “least contrived chinese inequality:” on the AoPS thread. I cannot agree more.

Problem 6, TSTST 2018 P8

For which positive integers $b > 2$ do there exist infinitely many positive integers $n$ such that $n^2$ divides $b^n+1$?

—USA Team Selection Test Selection Test Problem 8

Solution 6

The answer is all $b$ such $b + 1$ is not a power of 2. We first prove that such $b$ work. We prove that if $n$ works, then there exists odd prime $p \nmid n$ so that $pn$ works. By Zsigmondy’s theorem, there exists odd prime $p$ such $\text{ord}_p(b) = 2n$. Note that $p \nmid n$ and $p \nmid b$. Now,

And by lifting the exponent lemma,

So we are done (note $b^{pn} + 1 \equiv 0 \pmod {n^2}$). We also easily have at least one such $n$, simply find an odd prime $p$ such $p \mid b + 1$, and note $v_p(b^p + 1) = v_p(b + 1) + 1 \geq 2$. Now we prove that $b = 2^t - 1$ fail. Consider some $n > 1$ that works, and its smallest prime factor $p$. Note $n$ must be odd, and $p > 2$ (otherwise contradiction modulo 4).

Also, $\text{ord}_p(b) \nmid n$, so $\text{ord}_p(b) = 2$. So,

Which implies $\text{ord}_p(b) = 1$, contradiction. $\blacksquare$