Le paradoxe des crayons

Stratégie : on ne cherche pas où la conclusion est fausse, on cherche où l'argument est invalide. Une récurrence a exactement deux points d'appui, l'initialisation et l'hérédité. On les examine l'un après l'autre, et l'on n'accepte l'hérédité qu'au rang précis où on doit s'en servir.

L'énoncé prétendu. Pour $n\ge 1$, notons

$$P(n):\text{dans tout ensemble de }n\text{ crayons, tous ont la meˆme couleur.}$$

L'initialisation est correcte. $P(1)$ est vraie : dans un ensemble réduit à un crayon, il n'y a aucune paire de crayons à comparer, l'assertion est vraie faute de contre-exemple possible.

L'hérédité, telle qu'elle est rédigée. Soit $n\ge 1$ tel que $P(n)$ soit vraie, et soit $\{c_1,\dots ,c_{n+1}\}$ un ensemble de $n+1$ crayons. On pose

$$A=\{c_1,\dots ,c_n\}\text{et}B=\{c_2,\dots ,c_{n+1}\}.$$

Chacun a exactement $n$ éléments, donc $P(n)$ s'y applique : tous les crayons de $A$ ont une même couleur, disons $\alpha$, et tous ceux de $B$ une même couleur, disons $\beta$. L'argument conclut alors : « $A$ et $B$ ont un crayon commun, ce crayon porte à la fois la couleur $\alpha$ et la couleur $\beta$, donc $\alpha =\beta$, donc les $n+1$ crayons ont tous la même couleur ».

⚠️ La faute est dans les mots « ont un crayon commun ». Calculons cette intersection :

$$A\cap B=\{c_2,\dots ,c_n\},$$

qui est vide lorsque $n=1$. Le raisonnement suppose donc, sans jamais le dire, que $n\ge 2$.

Pourquoi tout s'effondre. L'implication $P(n)\Rightarrow P(n+1)$ est parfaitement valide pour tout $n\ge 2$ — et fausse pour $n=1$. Or c'est précisément celle-là dont on a besoin : le seul rang acquis par l'initialisation est $P(1)$, et il ne permet pas d'atteindre $P(2)$, puisque $\{c_1\}$ et $\{c_2\}$ sont disjoints. Une récurrence est une chaîne d'anneaux : le premier anneau est rompu, donc $P(2)$ n'est jamais établi, et tous les rangs suivants, dont l'hérédité est pourtant impeccable, reposent sur du vide.

Contrôle sur le plus petit cas. Vérifions $P(2)$ à la main : prenons deux crayons, l'un rouge et l'autre bleu. Ils forment un ensemble à deux éléments dont les crayons n'ont pas la même couleur. $P(2)$ est donc fausse — ce qui confirme qu'aucune démonstration correcte ne pouvait l'établir, et localise la rupture exactement entre le rang $1$ et le rang $2$.

La leçon de rédaction. Il ne suffit pas qu'une hérédité soit correcte « en général » : elle doit être correcte au plus petit rang où on l'utilise. Chaque fois qu'une démonstration d'hérédité découpe l'ensemble, prend un élément « du milieu », ou parle d'un indice $n-1$, il faut se demander à voix haute si l'objet invoqué existe encore au premier rang.

C'est le paradoxe des crayons, souvent énoncé avec des chevaux, et attribué à George Pólya.