Où est la faute ? On « démontre » que dans tout ensemble de n ≥ 1…

L'énoncé qu'on prétend démontrer. Notons, pour $n\ge 1$ : $$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 à un seul crayon, il n'y a rien à comparer.

L'hérédité, telle qu'elle est écrite. Soient $n\ge 1$ tel que $P(n)$ soit vraie, et $\{c_1,\dots ,c_{n+1}\}$ un ensemble de $n+1$ crayons. On considère $$A=\{c_1,\dots ,c_n\}\text{et}B=\{c_2,\dots ,c_{n+1}\}$$ Chacun a $n$ éléments, donc $P(n)$ donne : tous les crayons de $A$ ont une même couleur $\alpha$, tous ceux de $B$ une même couleur $\beta$. Puis l'argument conclut : « $A$ et $B$ se rencontrent, un crayon commun porte à la fois $\alpha$ et $\beta$, donc $\alpha =\beta$, donc les $n+1$ crayons ont la même couleur ».

La faute. Elle est dans le mot « se rencontrent ». On a $$A\cap B=\{c_2,\dots ,c_n\}$$ et cet ensemble est vide lorsque $n=1$. Le raisonnement suppose donc, sans le dire, que $n\ge 2$.

Autrement dit : l'implication $P(n)\Rightarrow P(n+1)$ est parfaitement valide pour tout $n\ge 2$, et fausse pour $n=1$. Or c'est exactement celle-là dont on a besoin : $P(1)$ est le seul rang acquis, et il ne permet pas d'atteindre $P(2)$, les deux ensembles $\{c_1\}$ et $\{c_2\}$ étant disjoints.

Pourquoi tout s'effondre. Une récurrence est une chaîne : chaque anneau tient au précédent. Ici l'anneau $P(1)\to P(2)$ 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. Un seul maillon manquant suffit à faire tomber l'énoncé pour tout $n\ge 2$.

La leçon. Quand on rédige une hérédité, il ne suffit pas qu'elle soit correcte « en général » : elle doit être correcte au plus petit rang où on l'utilise. Ici, il aurait fallu vérifier $P(2)$ à la main — et l'on aurait alors constaté que deux crayons peuvent parfaitement être de couleurs différentes.

C'est le paradoxe des crayons (ou des chevaux), attribué à George Pólya.