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é

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\)