Problem 1977

Solution:

Soit $A=A_{1} \cup A_{2}$ une partition démoniaque et soient $a=\max \left(A_{1}\right), b=\min \left(A_{2}\right)$. On a alors que le plus petit multiple commun des éléments de $A_{1}$ est plus grand ou égal à $a$ et le plus grand diviseur commun des éléments de $A_{2}$ est plus petit ou égal à $b$. Il faut donc que $a<b$, et ainsi $A_{1}$ et $A_{2}$ sont obtenus à partir de $A$ en mettant tous les éléments inférieurs à un certain nombre dans $A_{1}$ et tous les éléments restants dans $A_{2}$. En particulier, si $A$ possède $n$ éléments, le nombre de partitions démoniaques vaut au plus $n-1$.

Construisons maintenant un ensemble $A$ qui admet exactement 2016 partitions démoniaques. On écrit la paire $(x, y)$ pour représenter le nombre $2^{x} \cdot 3^{y}$ et l'ensemble $A$ est alors
$$A=\{(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2), \ldots,(1008,1008)\}$$
On voit facilement que l'on peut mettre la séparation entre $(a, a)$ et $(a+1, a)$ ou entre $(a, a+1)$ et $(a+1, a+1)$ pour obtenir des ensembles démoniaques. Cela donne alors exactement 2016 ensembles démoniaques et $A$ possède 3025 éléments.

Il reste à montrer que $A$ doit forcément avoir au moins 3025 éléments. Pour fixer la notation, soit
$$A=\left\{x_{1}, x_{2}, \ldots, x_{n}\right\}$$
Tout d'abord on ne peut pas avoir que $A_{1}=\left\{x_{1}\right\}$ et $A_{1}^{\prime}=\left\{x_{1}, x_{2}\right\}$ soient deux partitions démoniaques. En effet si $A_{1}, A_{2}$ est une partition démoniaque, le ppmc de $A_{1}$ vaut $x_{1}$ et donc le $\operatorname{pgcd}$ de $A_{2}$ également, donc $x_{1} \mid x_{i}$ pour tout $i \geq 1$. En particulier $x_{1} \mid x_{2}$ donc le ppmc de $A_{1}^{\prime}$ vaut $x_{2}$, ce qui implique que le pgdc de $A_{2}^{\prime}$ vaut $x_{2}$ et donc $x_{2} \mid x_{i}$ pour tout $i \geq 2$. Mais alors le $\operatorname{pgdc}$ de $A_{2}$ est $x_{2}$, ce qui contredit le fait que $A_{1}, A_{2}$ est une partition démoniaque. Supposons qu'il existe $i$ tel que $A_{1}=\left\{\ldots, x_{i}\right\}, A_{1}^{\prime}=\left\{\ldots, x_{i}, x_{i+1}\right\}, A_{1}^{\prime \prime}=\left\{\ldots, x_{i}, x_{i+1}, x_{i+2}\right\}$ forment trois partitions démoniaques. Nous avons alors les relations
$$\begin{gathered} x_{i}\left|\operatorname{ppmc}\left(A_{1}\right)=\operatorname{pgdc}\left(A_{2}\right)\right| b \quad \forall b \in A_{2} \\ x_{i+1}\left|\operatorname{ppmc}\left(A_{1}^{\prime}\right)=\operatorname{pgdc}\left(A_{2}^{\prime}\right)\right| b^{\prime} \quad \forall b^{\prime} \in A_{2}^{\prime} \end{gathered}$$
et
$$x_{i+2}\left|\operatorname{ppmc}\left(A_{1}^{\prime \prime}\right)=\operatorname{pgdc}\left(A_{2}^{\prime \prime}\right)\right| b^{\prime \prime} \quad \forall b^{\prime \prime} \in A_{2}^{\prime \prime}$$
Cependant les deux dernières relations impliquent alors que $\operatorname{pgdc}\left(A_{2}^{\prime}\right)=x_{i+2}$ et $\operatorname{pgdc}\left(A_{2}\right)=x_{i+1}$, et donc également que $\operatorname{ppmc}\left(A_{1}\right)=x_{i+1}$ car $A_{1}, A_{2}$ est démoniaque. Nous arrivons maintenant à une contradiction car $A_{1}^{\prime}$ est construit en rajoutant à $A_{1}$ uniquement l'élément $x_{i+1}$, donc $\operatorname{ppmc}\left(A_{1}^{\prime}\right)=x_{i+1}$ également, et comme on a déjà prouvé que $\operatorname{pgdc}\left(A_{2}^{\prime}\right)=x_{i+2}$ la paire $A_{1}^{\prime}, A_{2}^{\prime}$ ne pourrait être démoniaque. Ainsi il est impossible d'obtenir 2016 paires démoniaques si $A$ possède strictement moins de 3025 éléments.