Auswahlwettbewerb zur Internationalen Mathematik-Olympiade, 2022

Solution:

In the following we call a three-element subset $\{s, t, u\} \subset S$ a balanced triangle if the set $\{\mathrm{ggT}(s, t), \operatorname{ggT}(s, u), \operatorname{ggT}(t, u)\}$ has exactly two distinct elements. It is to be shown that there exists a balanced triangle.

Lemma. For pairwise distinct numbers $a, b, c, d \in S$ such that $\operatorname{ggT}(a, b)=\operatorname{ggT}(a, c) \neq \operatorname{ggT}(a, d)$ and $\operatorname{ggT}(b, d)=\operatorname{ggT}(c, d)$ hold, the set $\{a, b, c, d\}$ contains a balanced triangle.

Proof. If $\operatorname{ggT}(a, b)=\operatorname{ggT}(b, d)$, then $\{a, b, d\}$ is a balanced triangle. Otherwise, either $\operatorname{ggT}(a, d) \neq \operatorname{ggT}(a, b)$ or $\operatorname{ggT}(a, d) \neq \operatorname{ggT}(b, d)$ holds, so $\{a, b, c\}$ or $\{b, c, d\}$ is a balanced triangle.

For every element $a \in S$ let $S_{a}=\{\operatorname{ggT}(a, s) \mid s \in S, s \neq a\}$. Since this set contains only divisors of $a$, it is finite. From the hypothesis it follows that we can choose $a \in S$ such that $S_{a}$ contains at least two elements, since otherwise $\operatorname{ggT}(v, w)=\operatorname{ggT}(w, x)=\operatorname{ggT}(x, y)$ would hold.

By the pigeonhole principle we find an infinite subset $T \subset S$ such that $\operatorname{ggT}(a, t)$ is the same value $g$ for all $t \in T$. Now we choose a $d \in S \backslash(T \cup\{a\})$ such that $\operatorname{ggT}(a, d) \neq g$, which must exist because of $\left|S_{a}\right|>1$. Since $S_{d}$ is also finite, by the pigeonhole principle we find two distinct elements $b, c \in T$ such that $\operatorname{ggT}(b, d)=\operatorname{ggT}(c, d)$ holds. Then $a, b, c, d$ satisfy the hypotheses of the lemma, so indeed a balanced triangle exists.

Solution:

We may assume without loss of generality that no integer $g>1$ divides all numbers of $S$, since otherwise we could choose the largest such number $g$ and replace $S$ by the set $S^{\prime}=\{s / g \mid s \in S\}$: if the claim holds for $S^{\prime}$, then it also holds for $S$.

Suppose that for some prime $p$ the subset $S_{p} \subset S$ of all numbers divisible by $p$ were infinitely large, then we choose $a \in S \backslash S_{p}$, which is possible because of the preliminary consideration. Since the numbers $\operatorname{ggT}(a, s)$ for $s \in S_{p}$ are divisors of $c$, by the pigeonhole principle there exist distinct $b, c \in S_{p}$ with $\operatorname{ggT}(a, b)=\operatorname{ggT}(a, c)$. Since $b, c$ are both divisible by $p$, it also follows that $\operatorname{ggT}(b, c) \neq \operatorname{ggT}(a, c)$, hence the claim.

Thus we may assume that every prime divides only finitely many elements of $S$. Because of the hypothesis, we now find numbers $b, c \in S$ that are not coprime. There are only finitely many primes dividing $b$ or $c$, so $S$ also contains only finitely many elements that are not coprime to $b$ or $c$. Thus, since $|S|=\infty$, we can choose an element $a \in S$ that is coprime to both $b$ and $c$. Then $a, b, c$ satisfy the claim.