CultureMath
- Généralités
- Logique
- Mathématiques discrètes, algorithmique
- Algèbre
- Arithmétique
- Géométrie
- Topologie
- Analyse
- Probabilités
- Statistique
- Analyse numérique
- Interactions des mathématiques
- Mathématiques et physique
- Mathématiques et sciences de la vie
- Mathématiques et économie
- Mathématiques et autres disciplines
- Histoire des mathématiques
- Histoire : généralités
- Histoire : Mésopotamie
- Histoire : Grèce
- Histoire : autres mathématiques anciennes
- Histoire : Europe (jusqu'au dix-huitième siècle)
- Histoire : Europe (à partir du dix-neuvième siècle)
- Didactique, histoire de l'enseignement
- Épistémologie
- Ethnomathématiques
- Thèmes > Mathématiques discrètes, algorithmique , Arithmétique ,
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.1 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.
- 1. 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$).
- Vade-mecum Clubs de mathématiques
- Brève 35 : Publimath | 50 ans des IREM
- Les algorithmes gloutons
- Brève 34 : L’intégrale de 1981 à nos jours : deux brochures pour témoigner des réformes | 50 ans des IREM
- Les laboratoires de mathématiques à l'international
- Brève 33 : Promotion d’une perspective historique en classe | 50 ans des IREM
- Brève 32 : Agrandir, réduire | 50 ans des IREM
- Brève 31 : La formation à distance des professeurs d’école | 50 ans des IREM
- Brève 30 : Deux réformes fondamentales de l’enseignement des mathématiques | 50 ans des IREM
- Brève 29 : Interdisciplinarité | 50 ans des IREM