IMO 2024 Livesolve (Day 1)

(David here.) Recently, Sheldon and I attempted the IMO questions (with AYS and Aloysius making guest appearances along the way). I've tried to document some thought processes and some mishappenings - compared to the cleaned up solutions you'd see on the AoPS thread, this would be instead a messier look at how one might go about the problems.

$\newcommand\floor[1]{\lfloor #1\rfloor}$

Problem 1

(IMO 2024/1) Find all real number $\alpha,$ such that for any positive integer $n,$ $$\lfloor\alpha\rfloor +\lfloor 2\alpha\rfloor +\cdots +\lfloor n\alpha\rfloor$$ is a multiple of $n.$

1. We actually fakesolved this initially as follows: note that there are $n$ terms, and so the sum can only move $n$ terms at a time. But if we increase $\alpha$ slowly, the terms increase by at most 1, so to remain a multiple of $n$ they must all increase simultaneously, and hence $\alpha$ is an integer.

...except that we're not changing $\alpha$, we're changing $n$! Let's try again.

2. An initial instinct is that the sum is roughly $$\alpha \cdot \frac {n(n+1)}{2} - n/2$$ which is roughly because $\{\alpha\} + \{2\alpha\} + ... + \{n\alpha\} \approx n/2$. Well, this is correct for most irrational alpha and wrong for integer $\alpha$, somewhat wrong for half-integer alpha etc. But for our purposes, because the error is $O(n)$ it's not very useful.

3. But okay, one honest simplification we can do is to subtract an integer away from $\alpha$, so we'd have a very similar sum but using the fractional part of $\alpha$ instead: $$S_n := \floor{\{\alpha\}} + \floor{2\{\alpha\}} + ... + \floor{n\{\alpha\}} \equiv -\floor{\alpha}\cdot\frac{n(n+1)}{2} \pmod n$$

4. Clearly, $S_1=0$. If $\floor{\alpha}$ is even, then this sum is always $0$ mod $n$, but because each incremental term $S_n - S_{n-1}$ is smaller than $n$, so $\alpha\in \Z$.

5. What if it was odd? Then $S_n \equiv \frac{n(n+1)}{2} \pmod n$, which follows this periodic pattern: $$0, n/2, n/2, 0, 0, n/2, n/2, 0, \dots \pmod n$$ and by doing small cases one can see (using induction) that we're forced to have $\floor{n\{\alpha\}} = (n-1)$, which means that $1 > \{\alpha\}\ge \frac{n-1}{n}$ for all n, a contradiction!

Afterthought. In retrospect, probably the easier way to write this up is to compare this to a known sequence with this congruence: so instead note that $\sum_{i=1}^n (\floor{n\{\alpha\}} - n+1) \equiv 0 \pmod n$ and we have a similar finish as earlier in (3). Maybe this is more time efficient and less error prone for writing up instead of the inductive proof.

Problem 2

(IMO 2024/2) Find all positive integer pairs $(a,b),$ such that there exists positive integer $g,N,$ $$\gcd (a^n+b,b^n+a)=g$$ holds for all integer $n\ge N$

1. The first thing we tried was to cancel off one of the variables as follows: because $a^n + b | a^{kn} - (-b)^k$, we get $(-b)^k$ to cancel with $b^n$ to get $$(a^n + b, b^n + a) | \begin{cases} a^{n^2} - a & \text{ for $n$ odd}\\ a^{n^2} + a &\text{ for $n$ even}\end{cases}.$$

Then we realized that we could increase the exponent of any prime $p$ dividing some $a^{n^2} - a$. In particular, if $p|a^{n^2}-a$, then by LTE we have $p^3|a^{(pn)^2} - a$. But this is useless if we cannot force $p|a^2+b$.

2. So instead, we start with $p|a^n+b$. Actually, if $p|g$ then $p|a^n+b$ for all sufficiently large $n$ and by differencing adjacent terms we must get $$p|a^n(a-1)$$ which means that $p$ is small. Realizing that $a \equiv 0,1\pmod p$, and the same for $b$, except for the case $p=2$ we must have $p|a,b$. In our head, this means that $p$ is somewhat small.

3. Revisiting (1), we could try to force a large prime power to divide $a^n+b$ by using Hensel's lemma. Suppose that $p^k || a^n + b$, then one can pick $\ell\in \{1,2,...,p-1\}$ such that $p^{k+1} || a^{n+\ell p^k} + b$. Again, this is useless if $p$ doesn't already divide $b^n+a$. For that matter, even if we had the same power of $p$ dividing $b^n+a$, the $\ell$ we need might be different from the $\ell$ we'd need for $a^n+b$.

4. If $p$ divides both $a^n + b$ and $b^n + a$, then we have $a^n \equiv -b \pmod p$. $b^n \equiv -a \pmod p$.

Now we try to imagine if $a$ was a primitive root, then we'd have $b\equiv a^d$. Then we could phrase both conditions using powers of $a$: $$a^n \equiv a^{d+\frac{p-1}{2}}\pmod p,\qquad a^{nd}\equiv a^{\frac{p+1}{2}}\pmod p$$

and then we have somewhat of a quadratic condition in $d$ mod $(p-1)$... which is cool but didn't really go anywhere and felt too messy.

5. Suppose $p$ divided $a^n + b$, and we wanted this to divide $a^{N^2} - a$ (assuming for now that $p,n$ odd). Note that $p|a^n+b$ implies that $p|a^{n+k(p-1)} + b$, so if we set $k=n$ we get $p|a^{pn}+b$, while $p|a^{(pn)^2} - a$ by Fermat's Little Theorem.

Well, this is where we stopped in the livesolve. Turns out that was wrong and, honestly, too good to be true - we know that the exponent is periodic mod $p-1$.

6. But there's something in the idea of $n\mapsto n+(p-1)$: it means we can get from a small $n$ to a large one. This immediately means, for instance, that if $p|(a+b)$ then $p|g$. This starts to contrain $a$ and $b$ a lot, but it doesn't rule all of them out.

7. Now for the big brain idea: $n=-1$. So we have $p | a^{-1} + b = (ab+1)/a$ and $ p | a+b^{-1} = (ab+1)/b$, so $p | (ab+1)$ should imply that $p | g$. But this is bad, because $(ab+1)$ is coprime to $a$. So $\{a^n\}$ must be periodic mod $(ab+1)$, so $ab+1 | g \le \min\{a^2-a, b^2-b\}$, if they are both nonzero, which is a contradiction. So one of them has to be zero, and thus $a=1$ (and it's not hard to check that we must also have $b=1$).

Postmortem. It's easy to make embarrassing mistakes if you kind of forgot how the NT stuff usually goes. But the fact that $\{a^n\}$ has period $p-1$ mod $p$ for any $a$ coprime to $p$ is kind of a classic.

Our initial judgement was that this problem was going to be very easy, but a surprising number of things failed. Between (5) and (6), you needed a soft change in perspective - which was to give up forcing $p|a^n+b$ to divide $b^n+a$, because it just might not be possible. Instead, we opted for one such $p$ that already was divisible by both for a small $n$. If you held on to that approach, you would have been stuck.

Also, I have a soft spot for problems that require thinking about "invalid but valid" values - IMO 2005/4 also has this flavor.

Problem 3

(IMO 2024/3) Let $a_1, a_2, a_3, \dots$ be an infinite sequence of positive integers. Suppose that, for sufficiently large $n$, $a_n$ is equal to the number of times $a_{n-1}$ appears in the list $a_1, a_2, \dots, a_{n-1}$.

Prove that at least one of the sequence $a_1, a_3, a_5, \dots$ and $a_2, a_4, a_6, \dots$ is eventually periodic.

Disclaimer: we did not solve this, so this will mainly be our scratch work.

We tried a bunch of small cases:

1. Start from $1,1,2,2$:

$$1, 1, 2, 2, 2, 3, 1, 3, 2, 4, 1, 4, 2, 5, 1, 5, 2, 6, ...$$

2. Start from 6 1's.

$$1, 1, 1, 1, 1, 1, 6, 1, 7, 1, 8, 1, ...$$

3. We realized that the ordering of the initial numbers did not matter except for the last number.

4. Starting from $1,2,3,4,5$ gave a surprisingly long sequence before we found the "stable" state:

$$ 1, 2, 3, 4, 5, 1, 2, 2, 3, 2, 4, 2, 5, 2, 6, 1, 3, 3, 4, 3, 5, 3, 6, 2, 7, 1, 4, 4,$$ $$ 5, 4, 6, 3, 7, 2, 8, 1, 5, 5, 6, 4, 7, 3, 8, 2, 9, 1, 6, 5, 7, 4, 8, 3, 9, 2, 10, 1, $$ $$ 7, 5, 8, 4, 9, 3, 10, 2, 11, 1, ...$$

We also see some "equal sum" patterns (e.g. $5+4=6+3=7+2=8+1$).

5. Here's a visualization: drop a block at column $i$, then the next block should be dropped at the column with index equal to the height of the last column.

6. From looking at (4), we realize that at some point of time, we alternate between "big" numbers and "small" numbers. The big numbers increase by 1 after each "cycle", and the small numbers stay the same. The small numbers form the eventually periodic pattern.

7. Suppose that we're past the initial part (e.g. for $1,2,3,4,5$). Then if 10 appears 5 times, then 6, 7, 8, 9 also must have appeared 5 times. So the number of times $N$ appears (for large $N$) is non-increasing, hence is eventually constant or possibly all infinite. In the former case, we're also forced to alternate between big and small numbers.

8. More generally, consecutive $(m,n)$ can only appear once each and we have a "game of dominoes". $(m,n)$ must appear before $(m,n+1)$ (eventually) and $(m+1,n)$ must appear before $(m,n)$ (if $m$ is large enough).

9. Vaguely, we were missing a few pieces:

• Some way to figure out when the sequence split into large and small numbers. Our conjecture at this point was that the first number larger than everything provided initially should be good enough. (Turns out this is not quite sufficient.)
• Some explanation of "skips" e.g. in (2).
• Some way to rule out everything appearing infinitely often.
• Some way to force periodicity after the big-small split (we suspect some monovariant).

Postmortem. I think we sniffed out all the components but just couldn't flesh out the details within the timeframe. We'll defer more discussion to Glen's upcoming post (where he'll show us how he did it in an hour).