Vous pouvez retrouver cette question au format pdf.

Question du jeudi #61 : On répartit les entiers de $1$ à $n$ en $k$ classes de telle sorte que deux éléments d'une même classe ne se divisent jamais l'un l'autre. Quel est la plus petite valeur possible pour $k$ ?

Soit $2^p$ la plus grande puissance de $2$ comprise entre $1$ et $n$ (autrement dit, soit $p = \lfloor \log_2(n)\rfloor$). On remarque déjà que les entiers $1$, $2, \ldots, 2^p$ possèdent la propriété qu'étant donné deux d'entre eux, l'un divise forcément l'autre. Cela a pour conséquence qu'une partition respectant la contrainte de la question doit nécessairement les envoyer dans des classes distinctes. En particulier, quelle que soit la partition, on a forcément $k \geq p + 1$.

Réciproquement, notons $A_i$ l'ensemble des entiers compris entre $2^i$ et $2^{i+1}-1$. Quand deux entiers se divisent l'un l'autre, le plus grand des deux est au moins égal au double du premier. En particulier, deux éléments de $A_i$ ne peuvent pas se diviser l'un l'autre. On a donc trouvé $p+1$ classes qui conviennent :
\[ A_0 = \{1\}, A_1 = \{2, 3\}, \ldots, A_p \cap \{1, 2, \ldots, n\} = \{2^p, 2^p+1,\ldots, n\}.\]

Le nombre $k$ optimal est donc bien $p+1 = \lfloor \log_2(n)\rfloor +1$.

Remarque. On peut en fait essayer de généraliser cette question à des relations plus générales que celle de divisibilité. La notion de relation d'ordre généralise les relations comme la relation d'ordre usuelle $\leq$, la divisibilité, l'inclusion, etc. Autrement dit, il s'agit de relations exprimant l'idée qu'un objet est plus petit qu'un autre, mais sans que deux éléments donnés soient forcément comparables.[fn]Formellement, une relation d'ordre $\sqsubseteq$ sur un ensemble $E$ est une relation réflexive (c'est-à-dire $\forall x \in E, x \sqsubseteq x$), transitive $(\forall x, y, z \in E, x \sqsubseteq y\ \text{et} \ y \sqsubseteq z \implies x \sqsubseteq z$) et antisymétrique ($\forall x, y \in E, x \sqsubseteq y \ \text{et} \ y \sqsubseteq x \implies x = y$).[/fn] Une partie dans laquelle deux éléments donnés sont toujours comparables (comme $\{1, 2, \ldots, 2^p\}$ pour la divisibilité) est appelée une chaîne. À l'inverse, une partie dans laquelle deux éléments différents ne sont jamais comparables (comme nos $A_i$) est appelée une antichaîne. La question était donc ici de partitionner l'ensemble des entiers compris entre $1$ et $n$ en un nombre minimal d'antichaînes (pour la relation de divisibilité).

Le premier argument que nous avons donné se traduit dans ce langage plus sophistiqué en disant que le nombre minimal de classes est au moins égal au cardinal maximal d'une chaîne. Dans notre exemple, nous avons trouvé une partition explicite qui montrait que cette inégalité est optimale. C'est un fait un cas particulier d'un résultat important de combinatoire, le théorème de Dilworth.