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$.