Shortlist 2021, C1¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Principe des tiroirs · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 26 (page 26 du PDF)
Énoncé¶
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)\).
Indices : les idées clés
- Principe des tiroirs (version infinie) : un entier n'a qu'un nombre fini de diviseurs, donc parmi une infinité de PGCD \(\gcd(\alpha, \beta)\), l'un des diviseurs de \(\alpha\) revient une infinité de fois.
- Divisibilité et PGCD : \(\gcd(\alpha, s)\) divise toujours \(\alpha\) ; c'est la seule propriété du PGCD utilisée.
- Traduction en graphe coloré : arêtes \(\{s, t\}\) coloriées par \(\gcd(s, t)\) ; on cherche un triangle bicolore.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution et une remarque).
Solution 1¶
Un sommet « riche ». Il existe \(\alpha \in S\) tel que l'ensemble \(\{\gcd(\alpha, s) \mid s \in S,\ s \neq \alpha\}\) contienne au moins deux éléments. (Sinon, pour chaque \(s\), tous les \(\gcd(s, t)\) seraient égaux à une même valeur \(v(s)\) ; avec \(\gcd(a,b) = v(a) = \gcd(a, c) = v(c) = \gcd(c, d)\), cela contredirait l'hypothèse.)
Un ensemble infini à PGCD constant. Chaque \(\gcd(\alpha, s)\) est un diviseur de \(\alpha\), et \(\alpha\) n'a qu'un nombre fini de diviseurs. Par le principe des tiroirs (une infinité d'éléments \(s \in S\) répartis dans un nombre fini de tiroirs), il existe \(d \mid \alpha\) tel que l'ensemble
soit infini.
Un troisième sommet. Choisissons \(\gamma \in S\) avec \(\gcd(\alpha, \gamma) \neq d\) (possible par le choix de \(\alpha\)). Les valeurs \(\gcd(\beta, \gamma)\) pour \(\beta \in B\) sont des diviseurs de \(\gamma\), en nombre fini ; comme \(B\) est infini, on peut choisir \(\beta_1 \neq \beta_2\) dans \(B\) (distincts de \(\gamma\)) avec
Conclusion.
- Si \(d = d'\) : alors \(\gcd(\alpha, \beta_1) = d = \gcd(\gamma, \beta_1) \neq \gcd(\alpha, \gamma)\). Le triplet \((x, y, z) = (\alpha, \beta_1, \gamma)\) convient.
- Si \(d \neq d'\) : la valeur \(\gcd(\beta_1, \beta_2)\) ne peut pas être égale à la fois à \(d\) et à \(d'\). Si \(\gcd(\beta_1, \beta_2) \neq d\), alors \(\gcd(\alpha, \beta_1) = \gcd(\alpha, \beta_2) = d \neq \gcd(\beta_1, \beta_2)\) et le triplet \((\beta_1, \alpha, \beta_2)\) convient. Sinon \(\gcd(\beta_1, \beta_2) \neq d'\), et \(\gcd(\gamma, \beta_1) = \gcd(\gamma, \beta_2) = d' \neq \gcd(\beta_1, \beta_2)\) : le triplet \((\beta_1, \gamma, \beta_2)\) convient. \(\blacksquare\)
Remarques¶
Remarque 1 (version « graphe »). On peut modéliser la situation par un graphe complet sur l'ensemble infini \(S\), chaque arête \(\{s, t\}\) étant coloriée par \(c(s, t) = \gcd(s, t)\). En chaque sommet, les arêtes incidentes ne portent qu'un nombre fini de couleurs, et l'énoncé garantit qu'au moins deux couleurs apparaissent. Il s'agit de trouver un triangle bicolore (dont les arêtes portent exactement deux couleurs). La preuve est la même : on prend un sommet \(v\) portant au moins deux couleurs, un sous-ensemble infini \(X\) avec \(c(v, x) = c_1\) pour tout \(x \in X\), un sommet \(y\) avec \(c(v, y) \neq c_1\), puis \(x_1, x_2 \in X\) avec \(c(y, x_1) = c(y, x_2) = c_2\). Si \(c_1 = c_2\), le triangle \(v, y, x_1\) est bicolore ; si \(c_1 \neq c_2\), l'un des triangles \(v, x_1, x_2\) ou \(y, x_1, x_2\) est bicolore.