1 roi, 10 prisonniers, 1000 bouteilles de vin

Découvrez comment sauver la vie de 1000 personnes en sacrifiant quelques rebuts de la société qui l’ont bien mérité. Saurez-vous résoudre cette énigme qui touche au vin, boisson des dieux?

Récemment, je suis tombé sur cette énigme assez sympa. Je vous l’énonce.

Le roi d’un petit pays invite 1000 sénateurs à sa fête annuelle. La tradition veut que chaque sénateur apporte au roi une bouteille de vin.

Peu après, la reine découvre que l’un des sénateurs tente d’assassiner le roi en lui donnant une bouteille de vin empoisonné. Malheureusement, ils ne savent ni quel sénateur ni quelle bouteille de vin est empoisonnée, et le poison n’est pas reconnaissable.

Cependant, le roi a dix prisonniers qu’il veut exécuter. Il décide de les utiliser comme goûteurs pour déterminer quelle bouteille de vin contient le poison. Lorsque le poison est ingéré, il n’a aucun effet sur le prisonnier jusqu’à ce qu’il meure soudainement exactement 24 heures plus tard. Le roi doit déterminer quelle bouteille de vin est empoisonnée d’ici demain afin que les festivités puissent se poursuivre comme prévu. Il n’a donc le temps de procéder qu’à une seule série de tests.

Comment le roi peut-il administrer le vin aux prisonniers de manière à être sûr d’avoir trouvé la bouteille empoisonnée dans les 24 heures ?

Tentez de résoudre l’énigme et voyez si vous y arrivez! Si oui, vous avez un énorme cerveau et une intelligence cinétique hors norme. Si non, vous avez un énorme cerveau et une intelligence potentielle qui dépasse l’entendement.

La solution

La tentative « à la rache »

Nous avons 1000 bouteilles de vin, et seulement 10 prisonniers. Pour parodier les génies de notre époque:

J’ai 1000 bouteilles de vin et 10 prisonniers, pourquoi j’ai pas plutôt 1000 prisonniers et 10 bouteilles de vin?

Homer Simpson

Le problème réside évidemment dans le fait qu’on a trop peu de prisonniers pour beaucoup trop de bouteilles. Pour palier cela, la première idée qui nous vient est de distribuer les bouteilles afin d’en faire tester plusieurs par un seul prisonnier. Mais comment les répartir?

Réduisons la taille du souci. Prenons plutôt, disons, 10 prisonniers, et 10 bouteilles. Il nous suffira alors de distribuer une bouteille par prisonnier, et nous trouverons, après décès, quelle bouteille était empoisonnée. Bien. Le tout est de trouver une combinaison pour que chaque cas soit considéré.

Réduisons encore plus le souci. Nous avons désormais 1 prisonnier et 2 bouteilles. Il n’aura qu’à en boire une: s’il meurt, c’est qu’elle était empoisonnée, sinon… La bouteille qu’il n’a pas consommé était, elle, empoisonnée. Nous avons trouvé une combinaison permettant de tester chaque bouteille, même sans boire dedans.

Enfin, compliquons les choses: nous avons désormais 4 bouteilles pour 2 prisonniers. Comment procéder? Il faut trouver une combinaison qui permet de distribuer ces 4 bouteilles pour avoir une solution claire.

Pour nous simplifier la vie, numérotons chaque bouteille: 0, 1, 2, 3. Et chaque prisonnier sera nommé: A et B. Commençons une distribution. Chaque prisonnier peut avoir 2 bouteilles.

Dans cette solution, si le prisonnier A meurt, alors la bouteille empoisonnée était 0 ou 2. Sinon, si le prisonnier B meurt, alors il s’agissait de 1 ou 3.

Ne gâchez pas le vin!

Seulement voilà: le roi étant capitaliste et avare, cela ne lui convient pas de gâcher une bouteille de bon vin! Il faut trouver une nouvelle répartition pour n’avoir qu’une bouteille à éliminer à la fin. Tentons encore.

Dans cette répartition, la bouteille 0 n’a été distribuée à personne. Ainsi, si personne ne meurt, c’est que c’est celle-ci qui était empoisonnée.

La bouteille 1 est distribuée seulement au prisonnier B. S’il meurt, c’est que c’est celle-ci qui était empoisonnée. Vice versa pour la bouteille 2 et le prisonnier A.

Enfin, la bouteille 3 est distribuée aux deux prisonniers: si les deux meurent, c’est que c’est celle-ci qui était empoisonnée.

Les petits malins reconnaîtront un certain modèle dans cette distribution. Il s’agit d’une distribution binaire. Voyez:

En fait, pour résumer, nous pouvons transformer les morts de prisonniers en nombre binaire pour obtenir la bouteille empoisonnée. Reprenons la situation d’avant. Chaque prisonnier représente une valeur. Le prisonnier A représente 2^1, soit 2, et le prisonnier B représente 2^0, soit 1.

Si personne ne meurt, la somme des prisonniers morts est de 0. La bouteille étiquetée 0 était donc empoisonnée.

Si le prisonnier B (dont la valeur est 1) meurt, la somme des morts est de 1: la bouteille étiquetée 1 était donc empoisonnée.

Si le prisonnier A (dont la valeur est 2) meurt, la somme des morts est 2: la bouteille étiquetée 2 était donc empoisonnée.

Si le prisonnier A et B meurent, la somme des morts est 3: la bouteille étiquetée 3 était donc empoisonnée.

A grande échelle

Il nous suffit désormais d’appliquer ce même système à tous les prisonniers. Ils auront chacun une valeur: de 2^0 (soit 1) à 2^9 (512). Chaque bouteille sera numérotée de 1 à 1000. Les petits malins comprendront alors: nous pouvons faire 1024 possibilités différentes! Dingue, non? Cela nous fait un peu de bouteilles de rab, ce qui est toujours sympa au cas où davantage de sénateurs s’invitent.

Enfin, la distribution se fera en suivant l’ordre des nombres binaires, comme précédemment:

Et voilà. Si la somme des prisonniers morts fait 867, alors cette maudite bouteille 867 sera cassée sur la tête du sénateur qui l’a offert.

Aller plus loin

D’abord, en voyant ce tableau, quelque chose devrait vous interloquer. Le prisonnier a la valeur 1 boit une bouteille sur deux: il n’est donc pas à exclure qu’il ait une cirrhose du foie et qu’il meurt sans même avoir été empoisonné. Il a également, de ce fait, une chance sur deux d’être empoisonné.

Voici quelques sources qui peuvent vous intéresser:

• L’article Medium en anglais par Brett BERRY, qui m’a motivé à écrire cet article à ma propre sauce,
• Les nombres binaires sur Wikipedia, qui peuvent aider les moins aguerris sur le sujet.