Aller au contenu

Shortlist 2008, C3

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Principe des tiroirs · Principe extrémal

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 24 (page 25 du PDF)

Énoncé

Dans le plan muni d'un repère, on considère l'ensemble \(S\) des points à coordonnées entières. Pour un entier \(k\) strictement positif, deux points distincts \(A, B \in S\) sont dits \(k\)-amis s'il existe un point \(C \in S\) tel que l'aire du triangle \(ABC\) soit égale à \(k\). Un ensemble \(T \subset S\) est appelé une \(k\)-clique si deux points quelconques de \(T\) sont \(k\)-amis. Trouver le plus petit entier \(k\) strictement positif pour lequel il existe une \(k\)-clique de plus de \(200\) éléments.

Énoncé original (anglais)

In the coordinate plane consider the set \(S\) of all points with integer coordinates. For a positive integer \(k\), two distinct points \(A, B \in S\) will be called \(k\)-friends if there is a point \(C \in S\) such that the area of the triangle \(ABC\) is equal to \(k\). A set \(T \subset S\) will be called a \(k\)-clique if every two points in \(T\) are \(k\)-friends. Find the least positive integer \(k\) for which there exists a \(k\)-clique with more than \(200\) elements.

Indices : les idées clés
  • Caractérisation : \(A = (s, t)\) et \(B = (u, v)\) sont \(k\)-amis si et seulement si \(\gcd(u - s, v - t)\) divise \(2k\) (identité de Bézout).
  • Taille maximale : avec \(M(k)\) le plus petit entier ne divisant pas \(2k\), une \(k\)-clique a au plus \(M(k)^2\) points par les tiroirs (classes modulo \(M(k)\)), et le carré \(M(k) \times M(k)\) en est une.
  • Optimisation : il faut \(M(k) \geq 15\) ; \(M(k) = 15\) est impossible, \(M(k) = 16\) donne \(k = \operatorname{ppcm}(1, \ldots, 15)/2 = 180180\), et \(M(k) \geq 17\) donne plus grand.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).

Réponse : \(k = 180180\).

Solution

Décrivons d'abord les points \(B \in S\) qui sont \(k\)-amis du point \((0, 0)\). Par définition, \(B = (u, v)\) vérifie cette condition si et seulement s'il existe un point \(C = (x, y) \in S\) tel que \(\frac{1}{2}\lvert uy - vx \rvert = k\). (C'est la formule bien connue de l'aire du triangle \(ABC\) quand \(A\) est l'origine.)

Dire qu'il existe des entiers \(x\), \(y\) tels que \(\lvert uy - vx \rvert = 2k\) revient à dire que le plus grand diviseur commun de \(u\) et \(v\) divise aussi \(2k\). En résumé, un point \(B = (u, v) \in S\) est \(k\)-ami de \((0, 0)\) si et seulement si \(\gcd(u, v)\) divise \(2k\).

Une translation par un vecteur à coordonnées entières n'affecte pas la relation d'amitié : si deux points sont \(k\)-amis, leurs translatés le sont aussi. Il s'ensuit que deux points \(A, B \in S\), \(A = (s, t)\), \(B = (u, v)\), sont \(k\)-amis si et seulement si le point \((u - s, v - t)\) est \(k\)-ami de \((0, 0)\), c'est-à-dire si \(\gcd(u - s, v - t) \mid 2k\).

Soit \(n\) un entier strictement positif qui ne divise pas \(2k\). Montrons qu'une \(k\)-clique ne peut pas avoir plus de \(n^2\) éléments.

En effet, tous les points \((x, y) \in S\) se répartissent en \(n^2\) classes, déterminées par les restes de \(x\) et \(y\) dans la division par \(n\). Si un ensemble \(T\) a plus de \(n^2\) éléments, deux points \(A, B \in T\), \(A = (s, t)\), \(B = (u, v)\), tombent nécessairement dans la même classe. Cela signifie que \(n \mid u - s\) et \(n \mid v - t\). Donc \(n \mid d\), où \(d = \gcd(u - s, v - t)\). Et comme \(n\) ne divise pas \(2k\), \(d\) ne divise pas non plus \(2k\). Donc \(A\) et \(B\) ne sont pas \(k\)-amis, et l'ensemble \(T\) n'est pas une \(k\)-clique.

Soit maintenant \(M(k)\) le plus petit entier strictement positif qui ne divise pas \(2k\). Notons provisoirement \(M(k) = m\), et considérons l'ensemble \(T\) de tous les points \((x, y)\) avec \(0 \leq x, y < m\). Il y en a \(m^2\). Si \(A = (s, t)\), \(B = (u, v)\) sont deux points distincts de \(T\), alors les deux différences \(\lvert u - s \rvert\), \(\lvert v - t \rvert\) sont des entiers inférieurs à \(m\), et l'une au moins est strictement positive. Par définition de \(m\), tout entier strictement positif inférieur à \(m\) divise \(2k\). Donc \(u - s\) (s'il est non nul) divise \(2k\), et de même pour \(v - t\). Ainsi \(2k\) est divisible par \(\gcd(u - s, v - t)\), ce qui signifie que \(A\) et \(B\) sont \(k\)-amis. Donc \(T\) est une \(k\)-clique.

Il s'ensuit que la taille maximale d'une \(k\)-clique est \(M(k)^2\), avec \(M(k)\) défini ci-dessus. On cherche le plus petit \(k\) tel que \(M(k)^2 > 200\).

Par définition de \(M(k)\), \(2k\) est divisible par les nombres \(1, 2, \ldots, M(k) - 1\), mais pas par \(M(k)\) lui-même. Si \(M(k)^2 > 200\), alors \(M(k) \geq 15\). En essayant d'obtenir \(M(k) = 15\), on aboutit immédiatement à une contradiction (\(2k\) devrait être divisible par \(3\) et par \(5\), mais pas par \(15\)).

Essayons donc \(M(k) = 16\). Alors \(2k\) est divisible par les nombres \(1, 2, \ldots, 15\), donc aussi par leur plus petit commun multiple \(L\), mais pas par \(16\). Et comme \(L\) n'est pas un multiple de \(16\), on en déduit que \(k = L/2\) est le plus petit \(k\) tel que \(M(k) = 16\).

Enfin, remarquons que si \(M(k) \geq 17\), alors \(2k\) doit être divisible par le plus petit commun multiple de \(1, 2, \ldots, 16\), qui vaut \(2L\). Alors \(2k \geq 2L\), d'où \(k > L/2\).

En conclusion, le plus petit \(k\) ayant la propriété voulue est \(L/2 = 180180\). \(\blacksquare\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2020 N3 ★★☆☆☆ · OIM P5 : Une suite non constante peut-elle avoir chaque moyenne arithmétique de deux termes égale à une moyenne géométrique de termes ?
  • 2020 C5 ★★★☆☆ : On colorie \(1, \ldots, N\) en deux couleurs : une fraction \(a/p\) n'est jamais atteinte par la proportion de rouges.
  • 2011 N5 ★★★☆☆ · OIM P5 : Si \(f(m - n)\) divise \(f(m) - f(n)\), alors les valeurs de \(f\) se divisent les unes les autres par ordre de taille.
  • 2021 N7 ★★★★☆ : Si \(a_{n+2m}\) divise \(a_n + a_{n+m}\), la suite finit par être périodique.