Connecting problems

(Gabriel here) Occasionally, while I am solving a maths olympiad problem, I will be suddenly reminded of another problem I have done in the past before. I'm sure this has happened to many of you too. I think each of these connections presents valuable learning opportunities, and can help to make your subconscious intuition more concrete. In this post, I will give two examples from my own experience, and hopefully showcase some nice problems as well (if you haven't seen these problems before, I suggest trying them for a while first).

Problems with similar structure

There is not much to talk about this, if you have seen a question with a similar set-up before, it gives you an advantage over contestants who have to explore the structure from ground zero.

From experience, this happens surprisingly often, because proposers tend to converge on the more "natural" structures. My favourite example of this is how if you took parts of the solutions to IMO 16/6 (Geoff's frogs), EGMO 17/3 (Turbo the snail) and IberoAmerican 18/3, you can get a full, complete, 7-point solution to APMO 23/5.

Problems with similar key ideas

(Spoilers for IZhO 22/6)

Sometime last year I was given this problem in training:

(Cyberspace Mathematical Competition 20/8) Let $a_1, a_2,\dots$ be an infinite sequence of positive real numbers such that for each positive integer $n$ we have$$\frac{a_1+a_2+\cdots+a_n}n\geq\sqrt{\frac{a_1^2+a_2^2+\cdots+a_{n+1}^2}{n+1}}.$$Prove that the sequence $a_1,a_2,\dots$ is constant.

Let's first go through the solution.

Assume the contrary, that $a_x\ne a_y$. We define $b_n=\sqrt{\frac{a_1+\dots+a_n}{n}}$, then we can use QM-AM to get $b_n>\frac{a_1+\dots+a_n}{n}\ge b_{n+1}$. Thus, both $\{a_n\}$ and $\{b_n\}$ are strictly decreasing sequences of positive reals.

We wish to show this is impossible, and the easiest way to do so is to show that $b_n-b_{n+1}$ is "big". However, if we take $a_{n+1}=b_n$, then $b_n=b_{n+1}$. This means that the contradiction must come from showing $b_n-\frac{a_1+\dots+a_n}{n}=c_n$ is big (in particular, that $\sum c_i$ is unbounded). Squaring, $$n(a_1^2+\dots+a_n^2)=(a_1+\dots+a_n)^2+2nc_n(a_1+\dots+a_n)+n^2c_n^2.$$This simplifies to $$\sum(a_i-a_j)^2=2nc_n(a_1+\dots+a_n)+n^2c_n^2.$$We can bound $a_1+\dots+a_n\le na_1$, so $$n^2(c_n^2+2c_na_1)=n^2c_n^2+2n^2c_na_1\ge \sum (a_i-a_j)^2$$Note that this gives us the obvious bound $c_n\ge \frac{c}{n^2}$ for some constant $c$. However, this is not enough, as $\sum c_n=c\sum \frac{1}{n^2}$ is bounded. In order to make it unbounded, we will need $c_n\ge \frac{c}{n}$ instead.

This is not that hard: use the fact that $a_x\ne a_y$, which means that the distance from any $a_i$ to either one of them is "big", so that $\sum (a_i-a_j)^2\ge (n-2)\frac{(a_x-a_y)^2}{4}$.

While solving this, I was reminded of two different problems:

(IZhO 22/6) Do there exist two bounded sequences $a_1, a_2,\ldots$ and $b_1, b_2,\ldots$ such that for each positive integers $n$ and $m>n$ at least one of the two inequalities $|a_m-a_n|>1/\sqrt{n},$ and $|b_m-b_n|>1/\sqrt{n}$ holds?

Sketch: The condition is best written as $(a_m-a_n)^2+(b_m-b_n)^2\ge \frac{1}{n}$. If we plot the points $(a_i,b_i)$, then the points must be at least $\frac{1}{\sqrt{i}}$ apart. If we draw circles of radius $\frac{1}{2\sqrt{i}}$ around each point $(a_i,b_i)$, then no circles intersect. Now the sum of their areas is $\sum \frac{1}{4i}$, which is unbounded.

In fact, the power of $-\frac{1}{2}$ is tight. If we instead use the condition that $|a_m-a_n|>n^c$ where $c$ is less than $-\frac{1}{2}$, there is a bounded construction for the sequences.

The following is a bit more complicated:

(ISL 07/A5) Let $c > 2,$ and let $a(1), a(2), \ldots$ be a sequence of nonnegative real numbers such that $$ a(m + n) \leq 2 \cdot a(m) + 2 \cdot a(n) \text{ for all } m,n \geq 1,$$and $a(2^k)\leq \frac {1}{(k + 1)^c} \text{ for all } k \geq 0.$ Prove that the sequence $a(n)$ is bounded.

Sketch (exact bounds may be slightly off): If we express each integer in binary and bound using only $a(2^k)\le \frac{1}{(k+1)^c}$, we get the bound $$a\left(\sum_{i = 1}^m 2^{\alpha_i}\right) \leq \sum_{i = 1}^m \frac {2^i}{i^c}\text{ or }2m\sum_{i = 1}^m \frac {1}{i^c}.$$These are unfortunately unbounded. We can get the first bound by removing one power of two at a time, and the second by splitting the set of powers of two into halves each time. We want to remove the $2^i$ term from the first bound, and the $2m$ term from the second.

These two bounds seem to "cancel out". What if we use both of them? We can group the small $2m$ and big $2^i$ terms together so that they multiply to something bounded. Let $n=2^{\alpha_1}+2^{\alpha_2}+\dots+2^{\alpha_k}$. Take sets $$A_i=\{2^{\alpha_{m^{i-1}}},2^{\alpha_{m^{i-1}+1}},\dots,2^{\alpha_{m^i-1}}\}.$$We can bound $\sum \limits_{j\in A_i} a(j)$ using the second bound:$$\sum \limits_{j\in A_i} a(j)\le 2m^i\sum\frac{1}{\alpha_j^c}\le 2m^{2i}\frac{1}{\alpha_{m^{i-1}}^c}\le \frac{2m^{2i}}{m^{c(i-1)}}.$$We can then bound $a(n)=a(\sum A_i)$ using the first bound:$$a(n)\le \sum 2^ia(A_i)\le \sum 2^i\times \frac{2m^{2i}}{m^{c(i-1)}}=2m^c\sum \left(\frac{2}{m^{c-2}}\right)^i.$$By picking $m^{c-2}>2$, this will be finite, and we are done.

There are also many proofs that bound $a(n)$ by showing $\sum \frac{1}{i^{c/2}}$ is finite, and these explain why the condition $c>2$ is necessary.

After making the connection between the three solutions, we need to relook at the problems to understand why they all encourage the use of the idea that $r=1$ is the largest number for which $\sum \frac{1}{n^r}$ is unbounded.

• All questions involve a sequence, and whether or not it is bounded
• There is no obvious way of controlling the sequence, other than a size inequality.
• There is an obvious bound between successive terms of the sequence of the form $\frac{1}{n^\text{something}}$.
• If we can change this "something" by a bit, we are done.

With this realisation added to our problem solving toolbox, we are more ready to tackle questions that fall into the same category in the future. For example,

(USEMO 23/2) Each point in the plane is labeled with a real number. Show that there exist two distinct points $P$ and $Q$ whose labels differ by less than the distance from $P$ to $Q$.

Problems with similar "vibes"

(Spoilers for IMO 23/3)

I don't really know how to give a name to this, so I'll just give an example. Sometime in the past year, I did the following two questions:

(Baltic Way 22/10) A natural number $a$ is said to be contained in the natural number $b$ if it is possible to obtain a by erasing some digits from $b$ (in their decimal representations). For example, $123$ is contained in $901523$, but not contained in $3412$. Does there exist an infinite set of natural numbers such that no number in the set is contained in any other number from the set?

Sketch: Yes. In fact, there is an infinite subset for which $a_i$ is contained in $a_{i+1}$. Induct on the base $b$, with $b=1$ being obvious. (Motivation: try and solve for base 2 yourself.)

In base $n$, we construct the following subset: put $a_1$ inside, and as long as possible, put $a_{i+1}$ inside where $a_{i+1}$ contains $a_i$. Suppose we get stuck at some number $a_x=T$.

Let the digits of $T$ be $d_1,d_2,\dots, d_k$. For each of the remaining numbers, we highlight the following digits, scanning from left to right:

• The first occurrence of $d_1$,
• the first occurrence of $d_2$ after that,
• the first occurrence of $d_3$ after that, etc.

By assumption we never reach $a_k$. By pigeonhole there is some $m$ such that for infinitely many of these numbers we only highlight $m$ digits. These numbers must be in the form $.....d_1...d_2..........d_m......$.

The first dotted section has no $d_1$, the second has no $d_2$, etc, the last has no $d_{m+1}$. We can thus use the induction hypothesis to find an infinite sequence satisfying the condition in the first dotted section, and in that subset pick an infinite subset satisfying the condition in the second dotted section, etc.

(RMM 12/3) Each positive integer is coloured red or blue. A non-decreasing function $f$ from the set of positive integers to itself has the following property: if $x,y$ and $z$ are (not necessarily distinct) positive integers of the same colour and $x+y=z$, then $f(x)+f(y)=f(z)$.

Prove that there exists a positive number $a$ such that $f(x)\le ax$ for all positive integers $x$.

Sketch: Suppose there are arbitrary large red intervals. Then for any red $a,b$, we can find an interval $[n,n+ab]$ that is all red. This means that $f(n+ab)=f(n)+af(b)=f(n)+bf(a)$, so $f$ is linear over the reds.

If both colours have arbitrarily large monochromatic intervals, we are thus done. If only red has arbitrarily large monochromatic intervals, then we are also done with the non-decreasing condition (bound each blue by the next red). Hence, we are left with the case where the largest monochromatic interval is of size $C$, where $C$ is a constant.

Now, we consider the starts of these blocks, say $r_1,b_1,r_2,b_2,\dots$. Note that based on its colour, we can write $f(r_i+b_j-1)=f(r_i)+f(b_j-1)$ or $f(r_i-1)+f(b_j)$. Either ways, $f(r_i+b_j-1)\le f(r_i)+f(b_j)$. Now suppose $b_j>>C$. Then $$f(r_{i+1})\le f(r_i+b_j-1)\le f(r_i)+f(b_j).$$Since $f(b_j)$ is fixed, we are done.

For reasons I cannot comprehend, these two questions came into my mind while solving IMO 23/3:

(IMO 23/3) For each integer $k\geq 2$, determine all infinite sequences of positive integers $a_1$, $a_2$, $\ldots$ for which there exists a polynomial $P$ of the form$$ P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0,$$ where $c_0$, $c_1,\dots,c_{k-1}$ are non-negative integers, such that $$P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k} $$for every integer $n\geq 1$.

Why? These three questions want us to do the same thing: to find order in infinite chaos. The other two questions showed us that given enough terms, we are able to force nice properties even though the sequences (or their colours) appear random. In the case of the IMO question, this is done by taking successive infinite pigeonholes. Even though it may seem that (after we prove $a_n$ is increasing) we have to deal with $c^k$ possible sets of $a_{n+i}-a_n$, my experience taught me that we can ignore almost all the terms in this sequence and only focus on the ones that gives us what we need (in some way, that is motivation for why we want to show $a_n$ is increasing: because we know with finitely many cases to consider from there, the problem can definitely be solved).

And that's it! In the future, if a random problem comes to mind, there is usually some connection that your subconscious has made but you have yet to formalise (for example, "breaking symmetry"). Try and find it. You don't know how useful it can eventually be.

Oh and by the way, today's SMO Open Q4 reminded me of

(Malaysia TST 23/2) Let $a_1, a_2, \cdots, a_n$ be a sequence of real numbers with $a_1+a_2+\cdots+a_n=0$. Define the score $S(\sigma)$ of a permutation $\sigma=(b_1, \cdots b_n)$ of $(a_1, \cdots a_n)$ to be the minima of the sum $$(x_1-b_1)^2+\cdots+(x_n-b_n)^2$$ over all real numbers $x_1\le \cdots \le x_n$. Prove that $S(\sigma)$ attains the maxima over all permutations $\sigma$, if and only if for all $1\le k\le n$, $$b_1+b_2+\cdots+b_k\ge 0.$$

The brain works in mysterious ways.