Voici un joli raisonnement par récurrence dû à Keith Austin conduisant à une étrange conclusion.
Nous allons démontrer que lorsque \(n\) pièces de monnaies \((n\geq 2)\) d’apparences identiques sont données, l’une plus légère que les autres, alors trois pesées au plus avec une balance àdeux plateaux (permettant de comparer des masses sans les mesurer) suffisent pour l’identification de la pièce la plus légère..
Lorsque \(n = 2,\) on procède de la manière suivante. On prend les deux pièces indiscernables, on en place une sur le plateau de gauche et une autre sur le plateau de droite de la balance. L’équilibre ne se fait pas car l’une des pièces est plus légère par hypothèse. On peut la repérer, c’est celle qui se trouve sur le plateau qui monte. Dans ce cas simple, une seule pesée a suffi.
Soit maintenant \(n \geq 2.\) Supposons, comme hypothèse de récurrence, que nous connaissons une procédure utilisant au plus trois pesées pour \(n\) pièces, toutes de même masse, sauf une qui est plus légère. Montrons comment obtenir une procédure pour \(n + 1\) pièces.
Considérons \(n+1\) pièces de même masse, sauf une qui est plus légère que les autres. Nous mettons à part l’une des \(n+1\) pièces, et nous appliquons la procédure donnée par l’hypothèse de récurrence aux \(n\) pièces restantes.
Si la pièce la plus légère est dans les \(n\) pièces retenues, la procédure permet de la trouver. On a donc identifié la pièce la plus légère et il a suffi de trois pesées.
Si la procédure ne permet pas de trouver une pièce plus légère que les autres parmi celles retenues, c’est que la plus légère est celle que nous avons mise de côté. On trouve à nouveau la pièce la plus légère et il a encore suffi de trois pesées.
Donc, en au plus trois pesées, nous avons réussi à connaître la pièce la plus légère parmi les \(n+1\) pièces données.
Le raisonnement par récurrence fonctionne donc bien et, en conséquence, pour tout entier \(n \geq 2,\) il existe une procédure en trois pesées permettant d’identifier une pièce plus légère que les autres dans un ensemble de \(n\) pièces.
Croyez-vous vraiment qu’avec un million de pièces, en trois pesées vous pouvez repérer la plus légère? N’est-il pas étrange que le raisonnement présenté semble s’adapter et arriver à la même conclusion avec une seule pesée au lieu de trois? Il y a donc une erreur. Laquelle?
