Des tiroirs à construire

Ce qu'on a le droit d'utiliser. Le principe des tiroirs, contraposée du théorème du cours : une application d'un ensemble de cardinal $n+1$ vers un ensemble de cardinal $n$ n'est pas injective — deux objets tombent dans le même tiroir. Le théorème ne fait aucun travail ; tout l'exercice est dans la fabrication de la partition, et les deux questions demandent deux partitions incompatibles.

a) Deux entiers premiers entre eux. Les tiroirs sont les $n$ paires d'entiers consécutifs $$\{1,2\},\{3,4\},\dots ,\{2n-1,2n\},$$ qui forment une partition de $\{1,\dots ,2n\}$. On y range les $n+1$ entiers choisis : par le principe des tiroirs, deux d'entre eux tombent dans la même paire, c'est-à-dire sont de la forme $m$ et $m+1$. Tout diviseur commun $d$ de $m$ et $m+1$ divise leur différence, qui vaut $1$ : $d=1$. Les deux entiers sont premiers entre eux.

b) L'un divise l'autre. Les tiroirs sont tout autres. Tout entier $a\in \{1,\dots ,2n\}$ s'écrit de manière unique $a=2^{\alpha }m$ avec $\alpha \in \mathbb{N}$ et $m$ impair — on extrait la plus grande puissance de $2$ ; c'est la décomposition en facteurs premiers du chapitre 7, lue en $2$. On appelle $m$ la partie impaire de $a$. Comme $m\le a\le 2n$ et $m$ est impair, $m$ appartient à $\{1,3,5,\dots ,2n-1\}$, qui compte exactement $n$ éléments : voilà les $n$ tiroirs, et l'application « partie impaire » envoie les $n+1$ entiers choisis dans ces $n$ tiroirs.

Par le principe des tiroirs, deux entiers choisis $a=2^{\alpha }m$ et $b=2^{\beta }m$ ont la même partie impaire $m$. Comme $a\ne b$, on a $\alpha \ne \beta$ ; si $\alpha <\beta$, alors $b=2^{\beta -\alpha }a$ et $a$ divise $b$ ; sinon $b$ divise $a$. L'un divise l'autre.

Le point délicat. Les deux questions se résolvent par le même théorème, mais les paires consécutives ne disent rien de la divisibilité, et la partie impaire ne dit rien du pgcd. Le principe des tiroirs est un théorème d'existence non constructif — il affirme qu'un couple existe sans jamais dire lequel — et le prix à payer est de deviner la partition.

c) L'optimalité. Pour b) : l'ensemble $\{n+1,n+2,\dots ,2n\}$ a $n$ éléments, et aucun n'en divise un autre. En effet, si $a$ divise $b$ avec $a<b$, alors $b\ge 2a\ge 2(n+1)=2n+2>2n$ : impossible. Pour a) : l'ensemble $\{2,4,6,\dots ,2n\}$ a $n$ éléments, tous pairs : deux quelconques d'entre eux ont $2$ pour diviseur commun. Les deux énoncés sont donc exactement optimaux : $n+1$ est le plus petit nombre d'entiers qui force la conclusion, et le contre-exemple à $n$ est le second geste, aussi nécessaire que le premier.

Contrôle pour $n=5$. Dans $\{1,\dots ,10\}$, six entiers quelconques contiennent toujours deux consécutifs et deux de même partie impaire ; et $\{6,7,8,9,10\}$ ne contient aucun couple divisant, $\{2,4,6,8,10\}$ aucun couple premier entre eux.

Ce que l'exercice installe. Le principe des tiroirs n'est rien ; le choix des tiroirs est tout. Devant un énoncé « parmi $n+1$ objets, deux vérifient… », le réflexe est de chercher une partition en $n$ classes telle que deux objets d'une même classe vérifient la propriété — et, pour prouver l'optimalité, d'exhiber $n$ objets qui l'évitent.