Aller au contenu

Shortlist 2015, C3

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Ukraine

Concepts : Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2015 (avec solutions), p. 29 (page 30 du PDF)

Énoncé

Pour un ensemble fini \(A\) d'entiers strictement positifs, on dit qu'une partition de \(A\) en deux parties disjointes non vides \(A_1\) et \(A_2\) est bonne si le plus petit commun multiple des éléments de \(A_1\) est égal au plus grand commun diviseur des éléments de \(A_2\). Déterminer la plus petite valeur de \(n\) pour laquelle il existe un ensemble de \(n\) entiers strictement positifs ayant exactement \(2015\) bonnes partitions.

Énoncé original (anglais)

For a finite set \(A\) of positive integers, we call a partition of \(A\) into two disjoint nonempty subsets \(A_1\) and \(A_2\) good if the least common multiple of the elements in \(A_1\) is equal to the greatest common divisor of the elements in \(A_2\). Determine the minimum value of \(n\) such that there exists a set of \(n\) positive integers with exactly \(2015\) good partitions.

Indices : les idées clés
  • Une bonne partition est une coupure : si \(\operatorname{ppcm} A_1 = d = \operatorname{pgcd} A_2\), tout élément de \(A_1\) est \(\leq d\) et tout élément de \(A_2\) est \(\geq d\) ; une bonne partition est donc déterminée par un indice de coupure \(k\) dans la liste ordonnée.
  • Divisibilité, PGCD et algorithme d'Euclide : deux coupures consécutives imposent \(g_{k-1} = g_k = a_k\), d'où l'impossibilité de trois coupures consécutives (et de deux aux extrémités).
  • Compter puis construire : ces contraintes donnent au plus \(\lceil 2(n-2)/3 \rceil\) bonnes partitions ; un ensemble formé de \(2 \cdot 6^i\), \(3 \cdot 6^i\), \(6^{i+1}\) atteint la borne.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2015 (une solution et une remarque).

Réponse. \(n = 3024\).

Solution

Soit \(A = \{a_1, a_2, \ldots, a_n\}\) avec \(a_1 < a_2 < \cdots < a_n\). Pour un ensemble fini non vide \(B\) d'entiers positifs, notons \(\operatorname{ppcm} B\) et \(\operatorname{pgcd} B\) le PPCM et le PGCD de ses éléments.

Soit \((A_1, A_2)\) une bonne partition : \(\operatorname{ppcm} A_1 = d = \operatorname{pgcd} A_2\). Pour \(a_i \in A_1\) et \(a_j \in A_2\), on a \(a_i \leq d \leq a_j\) (car \(a_i \mid d\) et \(d \mid a_j\)). Donc \(A_1 = \{a_1, \ldots, a_k\}\) et \(A_2 = \{a_{k+1}, \ldots, a_n\}\) pour un \(k\) avec \(1 \leq k < n\) : chaque bonne partition est déterminée par un élément \(a_k\), \(1 \leq k < n\), qu'on dit séparateur. Posons, pour \(1 \leq k \leq n-1\),

\[\ell_k = \operatorname{ppcm}(a_1, \ldots, a_k), \qquad g_k = \operatorname{pgcd}(a_{k+1}, \ldots, a_n).\]

Ainsi \(a_k\) est séparateur si et seulement si \(\ell_k = g_k\).

Affirmation. Si \(a_{k-1}\) et \(a_k\) sont séparateurs (\(2 \leq k \leq n-1\)), alors \(g_{k-1} = g_k = a_k\).

Preuve. Comme \(\ell_{k-1} = g_{k-1}\) et \(g_{k-1} \mid a_k\), on a \(\ell_{k-1} \mid a_k\). Donc \(g_k = \ell_k = \operatorname{ppcm}(\ell_{k-1}, a_k) = a_k\), puis \(g_{k-1} = \operatorname{pgcd}(a_k, g_k) = a_k\). \(\square\)

Propriété 1. Pour \(k = 2, \ldots, n-2\), l'un au moins de \(a_{k-1}, a_k, a_{k+1}\) n'est pas séparateur.

Preuve. Sinon, l'affirmation (appliquée à \((a_{k-1}, a_k)\) puis à \((a_k, a_{k+1})\)) donne \(a_{k+1} = g_k = a_k\), contradiction. \(\square\)

Propriété 2. \(a_1\) et \(a_2\) ne sont pas tous deux séparateurs ; \(a_{n-2}\) et \(a_{n-1}\) non plus.

Preuve. Si \(a_1\) et \(a_2\) le sont, l'affirmation donne \(a_2 = g_1 = \ell_1 = a_1\), contradiction. Si \(a_{n-2}\) et \(a_{n-1}\) le sont, elle donne \(a_{n-1} = g_{n-1} = \operatorname{pgcd}(a_n) = a_n\), contradiction. \(\square\)

Minoration. Soit \(A\) un ensemble à \(n\) éléments ayant exactement \(2015\) bonnes partitions ; clairement \(n \geq 5\). Par la propriété 2, il y a au plus un séparateur dans \(\{a_1, a_2\}\) et au plus un dans \(\{a_{n-2}, a_{n-1}\}\). Par la propriété 1, chaque bloc de trois éléments consécutifs de \(\{a_3, \ldots, a_{n-3}\}\) (qui en compte \(n-5\)) contient un non-séparateur, donc il y a au moins \(\lfloor (n-5)/3 \rfloor\) non-séparateurs. Le nombre de séparateurs est donc au plus

\[(n-1) - 2 - \left\lfloor \frac{n-5}{3} \right\rfloor = \left\lceil \frac{2(n-2)}{3} \right\rceil.\]

Ainsi \(\left\lceil \frac{2(n-2)}{3} \right\rceil \geq 2015\), ce qui impose \(n \geq 3024\).

Construction. L'ensemble à \(3024\) éléments

\[A = \{2 \cdot 6^i,\ 3 \cdot 6^i,\ 6^{i+1} \mid 0 \leq i \leq 1007\}\]

convient : chaque élément de la forme \(3 \cdot 6^i\) ou \(6^{i}\), sauf \(6^{1008}\), est séparateur (par exemple, à la coupure après \(3 \cdot 6^i\), le PPCM à gauche et le PGCD à droite valent tous deux \(6^{i+1}\) ; à la coupure après \(6^{i+1}\), ils valent aussi \(6^{i+1}\)), tandis que les \(2 \cdot 6^i\) ne le sont pas. Cela fait \(1008 + 1007 = 2015\) bonnes partitions.

Le minimum cherché est donc \(n = 3024\). \(\blacksquare\)

Remarques

Remarque 1 (cas général). Si l'on remplace \(2015\) par un entier \(m \geq 1\) quelconque, la borne \(\left\lceil \frac{2(n-2)}{3} \right\rceil \geq m\) reste valable et donne \(n \geq \left\lceil \frac{3m}{2} \right\rceil + 1\). Elle est optimale : pour \(m = 2t\) pair, l'ensemble \(\{6^i, 2 \cdot 6^i, 3 \cdot 6^i \mid 0 \leq i \leq t-1\} \cup \{6^t\}\) convient, et pour \(m = 2t - 1\) impair, l'ensemble \(\{2 \cdot 6^i, 3 \cdot 6^i, 6^{i+1} \mid 0 \leq i \leq t-1\}\).

Problèmes voisins

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

  • 2023 N4 ★★☆☆☆ : Des produits où l'on remplace un à un les \(a_i\) par les \(b_i\) forment une progression arithmétique : quelle raison minimale ?
  • 2021 N3 ★★☆☆☆ : Pour quels \(n\) peut-on ordonner les diviseurs de façon que toutes les sommes partielles soient des carrés ?
  • 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 ?
  • 2016 N3 ★★☆☆☆ · OIM P4 : Des valeurs consécutives de \(n^2 + n + 1\) dont aucune n'est première avec le produit des autres : combien en faut-il au minimum ?