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é¶
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\),
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
Ainsi \(\left\lceil \frac{2(n-2)}{3} \right\rceil \geq 2015\), ce qui impose \(n \geq 3024\).
Construction. L'ensemble à \(3024\) éléments
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\}\).