Onze entiers parmi vingt : des tiroirs à construire

Ce qu'on a le droit d'utiliser. Le principe des tiroirs, forme contraposée du théorème du cours : si $|A|>|T|$, aucune application de $A$ dans $T$ n'est injective — deux objets tombent dans le même tiroir. En effet, une application injective $\varphi$ ferait de $\varphi (A)$ une partie de $T$ à $|A|$ éléments, alors qu'une partie de $T$ a au plus $|T|$ éléments. Et un fait de divisibilité : un diviseur commun à deux entiers divise leur différence. Le théorème ne fait aucun travail ; tout l'exercice est dans la fabrication des tiroirs, et les deux questions en demandent deux systèmes différents.

a) Les tiroirs sont des paires. Découpons $\{1,\dots ,2n\}$ en $n$ paires d'entiers consécutifs, $\{1,2\},\{3,4\},\dots ,\{2n-1,2n\}$ : c'est une partition, chaque entier est dans une paire et une seule. L'application « entier choisi $\mapsto$ sa paire » va d'un ensemble à $n+1$ éléments dans un ensemble à $n$ éléments : elle n'est pas injective, et deux entiers choisis tombent dans la même paire. Ce sont deux entiers consécutifs, $m$ et $m+1$. Tout diviseur commun $d$ de $m$ et $m+1$ divise leur différence, qui vaut $1$ : $d=1$. Leur PGCD vaut $1$.

b) Les tiroirs sont des parties impaires. L'écriture. Tout entier $a\ge 1$ s'écrit de façon unique $a=2^{\alpha }q$, avec $\alpha \in \mathbb{N}$ et $q$ impair. Existence : on prend pour $\alpha$ le plus grand entier tel que $2^{\alpha }$ divise $a$ — il existe, puisque $2^{\alpha }\le a$ borne $\alpha$ — et $q=\frac{a}{2^{\alpha }}$ est impair, sinon $2^{\alpha +1}$ diviserait $a$. Unicité : si $2^{\alpha }q=2^{\beta }{q}^{\prime }$ avec $q,q^{\prime }$ impairs et $\alpha <\beta$, alors $q=2^{\beta -\alpha }{q}^{\prime }$ serait pair ; donc $\alpha =\beta$ et $q=q^{\prime }$. On appelle $q$ la partie impaire de $a$.

Les tiroirs. Si $a\le 2n$, sa partie impaire est un entier impair au plus égal à $2n$ : elle appartient à $\{1,3,5,\dots ,2n-1\}$, qui compte exactement $n$ éléments. L'application « entier choisi $\mapsto$ sa partie impaire » envoie $n+1$ entiers dans $n$ tiroirs : deux entiers choisis distincts ont la même partie impaire, $a=2^{\alpha }q$ et $b=2^{\beta }q$. Comme $a\ne b$, $\alpha \ne \beta$ ; si $\alpha <\beta$, alors $b=2^{\beta -\alpha }a$, et $a$ divise $b$ ; sinon $b$ divise $a$.

Le point délicat. Les deux questions se règlent 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 affirme qu'un couple existe sans dire lequel : le prix à payer est de deviner la partition, adaptée à la propriété visée.

c) L'optimalité. Pour a) : les $n$ entiers pairs $2,4,\dots ,2n$ ont deux à deux le diviseur commun $2$, donc un PGCD au moins égal à $2$. Pour b) : parmi les $n$ entiers $n+1,n+2,\dots ,2n$, aucun n'en divise un autre ; si $a$ divisait $b$ avec $a<b$, on aurait $b\ge 2a\ge 2n+2>2n$. Le « plus un » n'est pas une marge de sécurité : c'est le seuil exact.

Contrôle. Pour $n$ allant de $1$ à $7$, l'examen de tous les choix possibles — par exemple les $3003$ façons de choisir $8$ entiers parmi $14$ — confirme les deux conclusions sans exception ; pour $n=5$, les ensembles $\{2,4,6,8,10\}$ et $\{6,7,8,9,10\}$ mettent en défaut, respectivement, a) et b).

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… », on cherche une partition en $n$ classes telle que deux objets d'une même classe vérifient la propriété : chercher les tiroirs, c'est chercher l'invariant que deux objets sont forcés de partager. Et l'optimalité se prouve par un contre-exemple à $n$ objets, geste aussi nécessaire que le premier.