I am planning to do at least one ISL every day so that I do not lose my Olympiad touch (and also they are fun to think about!). Today, I tried the 2021 IMO shortlist C1.
(2021 ISL C1)
Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.
Suppose not. Then any $3$ elements $x,y,z\in S$ will be $(x,y)=(y,z)=(x,z)$ or $(x,y)\ne (y,z)\ne (x,z)$.
There exists an infinite set $T$ such that $\forall x,y\in T,(x,y)=d,$ where $d$ is constant.
Fix a random element $a$. Note that $(x,a)|a$. So $(x,a)\le a$.Since there are infinite elements and finite many possibilities for the gcd (atmost $a$). So $\exists$ set $T$ which is infinite such that $\forall b_1,b_2\in T$ $$(a,b_1)=(a,b_2)=d.$$ Note that if
$(b_1,b_2)\ne d$ then we get a contradiction as we get a set satisfying the problem statement. So in $T,$ $$\forall x,y\in T,(x,y)=d.$$
Note that $T\ne S$. As, if $T=S$ then we get all elements having same $gcd$ which is a contradiction. So $\exists b\in S$ such that $(a,b)\ne d$.Say $d_2$. But now consider $T$ and $b$ again. We get another infinite set $R$ such that $$\forall r_1,r_2\in R,(r_1,b)=(r_2,b)=d_3.$$And $R\subset T$. Note that $(r_1,r_2)=d$
Now, we give the following constructions: If $d\ne d_3$. Then note that $(x,y,z)=(b,r_1,r_2)$ works. Contradiction. If $d=d_3$. Then note that $(x,y,z)=(b,r_1,a)$ works. Contradiction. So we must have $3$ elements $x,y,z\in S$ such that $(x,y)=(y,z)\ne(x,z)$.
I think the main motivation was that infinite sets are too good to not use. The $\gcd$ condition gives us the infinite sets. And then seeing how the infinite sets are actually an infinite clique. Really nice.
Will see you all tomorrow with a new combinatorics problem!
~Sunaina (Jan 12,2024)
Comments
Post a Comment