IMO 2024 Day 1

A lot of spoilers below.

Stuck in camp, doing the entire paper on my Learnet. Here are the ramblings of a guy with insufficient sleep (may contain mistakes):

(0h0m) First thoughts:

Q1 looks very standard, like a mix between a junior olympiad question and a classical problem.
Q2 also looks pretty standard, although the "for sufficiently large" condition is interesting.
Is Q3 supposed to be combi? It looks more like algebra to me, and in that case is Day 1 only A and N?

(0h5m) We want $n\mid \lfloor \alpha \rfloor+\lfloor 2\alpha \rfloor+\dots+\lfloor n\alpha \rfloor$ for any positive integer $n$ .

$\alpha=2$ works. In fact any multiple of $2$ works. Perhaps we need to show that $\alpha$ is an integer, so suppose it is not. Also, $\alpha$ being negative can pose some problems.

Suppose $\alpha$ is a very small positive number. Then, consider the first $n$ such that $n\alpha\ge1$ . We must have $n\mid 1$ , a contradiction. In particular, this eliminates $0<\alpha<1$ .
If $\alpha$ is large, we can remove integers out of the floor function.
If $\alpha=m+r$ where $0<r<1$ , then $n\mid \lfloor r \rfloor +\lfloor 2r\rfloor+\dots \lfloor nr\rfloor+m\cdot\frac{n(n+1)}{2}.$
If $n$ is odd, then we are done as above.

What if the first $n$ such that $nr\ge1$ is even?

In this case, then $n\mid 1+m\cdot\frac{n(n+1)}{2}$ .
This can be rewritten as $2n\mid 2+mn(n+1)$ .
$\implies n\mid 2$ , hence $n=2$ , or $\frac{1}{2}\le r<1$ .
We have $3\mid 1+\lfloor 3r\rfloor$ , and thus $\lfloor 3r\rfloor=2$ . In particular $\frac23\le r<1$ .
Once again, $4\mid 3+\lfloor 4r\rfloor$ , and there are no solutions.

Oh no I bashed a Q1 😦

Anyways, this means that $\alpha$ is an integer, and the solution set is thus $\alpha=2k$ for some integer $k$ .

I think this is even easier than last year's P1, which many people were already calling trivial. I can't wait to read AoPS comments.

(0h25m) Time for Q2. We need $\gcd(a^n+b,b^n+a)=g$ to be constant for sufficiently large $n$ .

Another number theory, another divisibility condition, and another number theory that has a “this condition holds for all $n$ “? Interesting combination.

Anyways, we have $g\mid a^n+b$ and $g\mid b^n+a$ . This means that $a^{n^2}\equiv (-b)^n\equiv a(-1)^n\pmod{g}$ .
Let’s get the obvious out of the way. What if $\gcd(a,b)>1$ ? Nothing…
There exists $d$ such that $a^{n+d}\equiv a^n\pmod{g}$ for sufficiently large $n$ . I have no rigorous proof of this, just intuition, but it kinda makes sense. When $n$ is sufficiently large, then all the common factors of $g$ and $a$ are taken care of. We can then use Euler’s theorem.
There exists $d$ such that $a^{n+d}\equiv a^n$ and $b^{n+d}\equiv b^n$ for sufficiently large $n$ . We can multiply the periods.
If $p\nmid g,a,b$ and $p\mid a^n+b$ , we have $p\mid a^{n+k(p-1)}+b.$ Can we force $p\mid b^{n+k(p-1)}+a$ ? No. Oh no…
$g\mid a^n+b$ and $g\mid a^{n+1}+b$ . This means that $g\mid ab-b$ . We also have $g\mid ab-a$ , so $g\mid a-b$ . WLOG $a>b$ . We deal with $a=b$ later.
$g\mid a^n+a$ . Also, $g\mid a^{n+1}-a^n$ .

Can we force $g=\gcd(a,b)$ ?

Suppose $p\mid g$ but not $a,b$ . Then, $p\mid b(a-1)$ so $p\mid a-1$ and also $p\mid b-1$ . This means that $p\mid 1^n+1=2$ . Hence $p=2$ .
Can $4\mid g$ but not $a,b$ ? No. We can bash all 4 combinations of $a,b\pmod{4}$ .
Suppose $p\mid g,a$ but not $b$ . Then, $p\mid b-1$ . This means that $p\mid a^n+b\implies p\mid 1$ , a contradiction.
Finally, suppose $p\mid g,a,b$ . What happens if $v_p(g)>v_p(a)$ ? Then, $g\mid b^n+a$ fails for large $n$ .

Finally, progress. We must have $g=\gcd(a,b)$ or $2\gcd(a,b)$ (the latter if $a,b$ are both odd), This means that $g$ is the “obvious gcd “.

The contradiction, if it exist, must thus come from getting some $p$ such that $p\mid a^n+b$ and $b^n+a$ but somehow not $a$ or $b$ .

I just realised this line is useful:

“If $p\nmid g,a,b$ and $p\mid a^n+b$ , we have $p\mid a^{n+k(p-1)}+b.$ ”

This is because when $n=1$ , both $a^n+b$ and $b^n+a$ are the same!

Consider $p\mid a+b$ but $p\nmid a,b$ . Then, $p\mid a^{n+k(p-1)}+b$ and $p\mid b^{n+k(p-1)}+a$ . This is a contradiction.

Put another way, for $p\mid a+b$ , we must have $p\mid g\mid 2\gcd(a,b)$ . Hence either $p=2$ or $p\mid a,b$ .

What kind of $a,b$ does this leave us with?

If $a=dx$ , $b=dy$ , $\gcd(x,y)=1$ , then $p\mid x+y$ implies $p\mid dx$ , or $p\mid d$ . There’s nothing here…

(1h0m) I am deciding between pursuing $p\mid a^n+b$ and $p\mid b^n+a$ or looking further into the $n=1$ idea.

Does there exist $n>1$ such that $a+b\mid a^n+b$ ? In other words $a+b\mid a(a^n-1)$ . With the above notation, this means that $x+y\mid (dx)^n-1$ . Oops.
In $\pmod{4}$ . the pair $(3,3)$ dosent work. The rest do. Hence, any other contradiction comes from odd $p$ .
The pair $(a,b)\equiv (1,2)$ in $\pmod{3}$ dosen't work. Neither does $(2,2)$ .

(1h40m) I still feel that $p\mid a+b$ is the key. Note that $a^p\equiv a\pmod{p}$ . This means that $a^{p^n}\equiv a$ . Thus, $p\mid a^{p^n}+b$ and $b^{p^n}+a$ . Hence, $p\mid g$ . We do not need the $p\nmid a,b$ condition.

If $p^x\mid a+b$ , can we do the same? $a^k\equiv a\pmod{p^x}$ for some $k$ ? Well, not if $p\mid a$ .
Change of plans. If $p\mid a+b$ and $p\nmid a$ , let $p^k\mid a+b$ , then $p^k\mid a^{n(\varphi({p^k}))+1}+b$ .

Finally!! This means that $p^k\mid g$ . If $p$ is odd, then $p^k\mid \gcd(a,b)$ .

Express $x+y$ as its prime factorisation and apply the result to each prime power, $x+y\mid d$ .
Hence, we can parameterise: $a=kx(x+y)$ , $b=ky(x+y)$ .
Now, $d\mid a^n+b\implies d\mid k(x+y)[k^{n-1}(x+y)^{n-1}x^n+y]$ .

It suffices to find the $\gcd$ of the square bracket with its counterpart. Multiplying by $y^n$ (resp. $x^n$ ), the $\gcd$ must divide $y^{n+1}-x^{n+1}$ . Meh. Square 1.

(2h15m) Crazy thought, but if we can't jump upwards from $n=1$ , what about negative $n$ ? $p\mid \frac{1}{a}+b\implies p\mid 1+ab$ , which miraculously is symmetric in $a,b$ . Even better $p$ is coprime to $a$ and $b$ !!

Take $p\mid 1+ab$ , then by FLT $p\mid a^{k(p-1)-1}+b$ .
Hence, $p\mid g$ . Since $p$ is coprime to $a,b$ , this means that $p=2$ . Thus, $1+ab$ is a power of 2.
Can $4\mid 1+ab$ ? This would mean that $(a,b)\equiv (1,3)\pmod{4}$ , and by taking large odd $n$ we must have $4\mid g$ , a contradiction.

And out of nowhere we are done! $n=-1$ is such a hard step to see.

(2h30m) Seriously? Another $n>N$ ? We have that $a_n$ is the number of times $a_{n-1}$ appears already on the list, which is weird but probably on OEIS. Such a short problem statement for a P3, but let’s see…

If we start with $a_1=1$ , then the sequence is $1,1,2,1,3,1,4,1\dots$ .
Must there be an infinite number of $1$ s? If not, there are only finitely many numbers appearing, and one of them will appear infinitely many times, giving us more $1$ s. Hence, there are an infinite number of $1$ s.
This also means that there are arbitrarily big numbers. I guess all of them must belong to either the odds or evens?
Must it always end in $1,n,1,n+1,\dots$ ?
Let’s say we have a new biggest number $n$ , so it is $n,1$ . The next number will be the number of $1$ s, which may decrease.
Perhaps we need to prove that eventually there will be more $1$ s then every other number?
Let’s try another sequence: 3,5|1,1,2,1,3,2,2,3,3,4,1,4,2,4,3,5,2,5,3,6,1,5,4,4,5,5,6,2,6,3,7,1,6,4,6,5,7,2,7,3,8,1,7,4,7,5,8,2,8,3,9,…
Wow this one is complicated. The pattern is 2,3,1,4,5,1,2,3,1,4,5,… That is unexpected.
Must the periodic part consist of all different integers?

Can we prove that either the evens or odds must be bounded?

Must all 1s be of the same parity?
2|1,1,2,2,3,1,3,2,4,1,4,2,5,1,5,2…
Must the period only consist of those less than or equal to the starting numbers?
The pair $(a,b)$ can only appear once. Also, we cannot “skip” integers, so $a$ always appear before $a+1$ for sufficiently large $a$ .
At the point where $a$ first appears we can “start the count”. Are there always less $a+1$ s then $a$ s? Yes, because to reach $a+1$ we must first reach $a$ .

What does it mean if an integer $a$ appears infinitely many times? This means that every number has at least $a$ copies. If there are infinitely many integers that appear infinitely many times, then all integers must appear infinitely many times. Is this a contradiction?

Is the # of 1s always finitely behind the largest number? Yes, since every new largest number will lead to a $+1$ . So the sequence will go $n,1,n-c$ .
Must the next largest number appear finitely behind the previous?
Let’s say there is a large gap between the first occurrence of $n$ and the first occurrence of $n+1$ . The first occurrence of $n+1$ must be due to some “small number”. Small numbers are those $\le \max(a_1,\dots,a_N)=M$ since after that the count is decreasing.

(3h0m) Can we ever have $a,b$ where $a>M$ and $b>M$ ? Consider the first pair where this happens.

This pair must in fact be $M+1,M+1$ by the decreasing condition.
Can we force everything to be decreasing? I.e. after a certain point, #1s $\ge$ #2s $\ge$ #3 $\ge$ … No.
If we get $M+1,M+1$ , this means that $1$ to $M$ have all appeared $M+1$ times already. The last appearance of $M+1$ would have been $M+1,M$ . After this, how do you even get another $M+1$ ? You can't!

Hence, if $a_n>M$ , then $a_{n+1}\le M$ ! Progress!

Highlight everything that is $>M$ . Eventually, this will have period $2$ , i.e. either the odds or the evens are bounded by $M$ !
Ok now what. Both the odds and evens seem to influence each other in an indescribable way.
Can we show that any two $1$ are at least $M$ spaces apart?
Or maybe, can we show that #1s-#2s is bounded? If it is not, then there exists a lot of numbers that only appeared once. Let $n$ be the largest number that has appeared. Let the number before be $c$ . Nvm.
If we do end up showing that any # $a$ s-# $b$ s is bounded, then we can infinite pigeonhole to get the same "configuration" of the small numbers.
Holdup, pigeonhole seems promising, we can probably infinite pigeonhole on a massive pile of stuff, like the set of #a-#b, the current small number, the number of times "#a" has appeared, and everything can be determined from these.

It suffices to show that #1s-# $a$ s cannot be arbitrarily big

If we have the sequence $1,n$ and $n$ hasn't appeared before, we are done.
If we have too many $1$ s, we will eventually end up with $1,n$ ? Yep, I think we are done?

(3h50m) Let's try to formalise this. Suppose from $a_1,\dots,a_n$ , we have #1s-# $M$ s being very, very big. Then, there are many, many numbers that have appeared exactly once in the sequence. Thus, for large enough $k$ , the pair $1,k$ will come way before the pair $M,k$ . This means that the number after $1,k$ is $\le M-1$ . If this number, say $i$ , also satisfies that # $i$ s-# $m$ s can be very big, then we kind of have that the next number is $\le M-1$ as well. This means that eventually there are no more $M$ s in the sequence.

Hence, suppose #1s-# $M$ s is unbounded. Then, there exists $i$ such that # $i$ s-# $i+1$ s is unbounded.
Thus, for large enough $k$ , the pair $i,k$ will come way before the pair $i+1,k$ and $i+2,k$ up till $M,k$ .
After $i,k$ , we will thus have a number $\le i$ .
However, this number also satisfies the same property that $j,x$ will come way before $i+1,x$ , etc. Hence the next number after $x$ will also be $\le i-1$ . Repeating this, we get a contradiction.

(4h15m) Phew, done. Would I be able to submit full solutions if I didn't type all of these out? Maybe. I don't know. It'll definitely be clutch.

Closing remarks

OK. As it turns out, Q3 was pure combi. And it was nice combi too! It bears much resemblance to last year's Q3 as well, and I think only slightly harder. However, Q2 is hard. Although the solution is short, the rabbit hole of $p\mid a+b$ is a pretty crazy one. I think this will have about 170 solves only.

Q1 is just standard, nothing much to say about it, probably about the same number of solves as last year’s Q1. How many FCs? Probably about 30.

Contrary to my initial expectations, I actually like this paper. I think it is a good differentiator for both silver and gold – silver because Q2 is hard, and gold because if you don’t solve Q2 fast enough you will not solve Q3. Q1 being a “classical” training-style problem is also good, because it rewards good training in weaker countries.

CGA or GCA?

P.S. For anyone who needs more elaboration on my Q3 solution, I wrote a sketch on AoPS.

IMO 2024 Day 1

Closing remarks

Comments

Leave a comment Cancel reply