Le problème des campeurs
Vous aussi, lecteur, pouvez résoudre cette énigme posée par un de ses clients. Cela vous permettra d'aborder une notion importante dans le domaine de l'informatique.
Il faut protéger la vérité avec une cuirasse de mensonges. (Winston Churchill)
Si prévenir ses amis que l’on s’apprête à partir en voyage est une marque d’attention, on peut dire qu’Ecco n’est pas loyal du tout. Lui se contente de m’avertir qu’il est parti et de m’appeler à son retour.
Il se rend généralement dans des endroits déserts sur la côte, le plus souvent dans le Maine, à l’automne. « Je me nourris de choses simples, et je passe le plus clair de mon temps à marcher. De temps à autre, je m’allonge sur la plage. Ça sent bon le sel et l’iode ; les mouettes m’enveloppent de leurs cris perçants. C’est là que je reprends mes esprits. »
C’est quelques jours après un de ces voyages que l’une des grandes gageures de sa carrière se présenta. Nous étions plongés dans une partie d’échecs très serrée, mais je voyais bien que les choses n’allaient pas parce qu’Ecco déplaçait souvent sa dame.
Le téléphone sonna et Ecco me fit signe de prendre l’écouteur.
« Docteur Ecco, nous avons besoin de votre aide, dit la voix. Euh… ! Docteur Ecco, nous détectons un signal… On nous écoute.
– Oui, mon général, dit Ecco en souriant. C’est le professeur Scarlet. Ne vous inquiétez pas. »
L’espionnage possible de ses faits et gestes inquiétait moins Ecco maintenant. Le directeur lui avait assuré que la surveillance avait cessé, mais il lui avait demandé de limiter ses voyages à des pays amis.
« Oh ! Bonjour, professeur, dit le général. Nous devons être prudents, c’est tout. Je serai chez vous dans deux heures.
– Parfait. »
« Docteur Ecco, permettez-moi de vous raconter une histoire », commença le général. Ecco me sourit. Les militaires adoraient dissimuler leurs intentions derrière des paraboles. Leurs propos étaient transparents, ou bien ils étaient complètement obscurs.
« Ne vous laissez pas induire en erreur par l’innocence de son cadre, poursuivit le général. Nous parlons de choses graves.
– Oui, mon général.
– Supposons que vous soyez un animateur de camp de vacances. Vous et vos huit campeurs êtes perdus dans les bois, incapables de retrouver votre chemin. Vous arrivez à une croisée de quatre chemins. Vous savez que le camp se trouve à vingt minutes de là, mais vous ne savez quel chemin prendre. Il vous reste encore une heure avant la tombée de la nuit, après quoi tout déplacement sera très dangereux. Il n’est donc pas question que vous empruntiez un chemin en emmenant tous les campeurs. Ce serait trop long.
Arrivés à la croisée des chemins, les campeurs disposent d’une heure pour trouver leur camp.
Illustration : Cédric Trojani.
« Vous devez envoyer des petits groupes vingt minutes dans chaque chemin et leur donner rendez-vous au point de départ, quarante minutes plus tard. Vous déciderez alors quel chemin emprunter. (Vous pouvez aussi participer aux recherches dans les quarante premières minutes.)
« Le problème, c’est qu’il arrive que deux des campeurs de votre groupe mentent. Vous ne savez pas qui ils sont. Comment divisez-vous votre groupe en équipes de recherche ? À l’heure du rendez-vous, comment décidez-vous du chemin à prendre ? Quelle que soit la répartition des menteurs occasionnels – quels qu’ils soient – dans les équipes et qu’ils mentent ou non, vous ne pouvez pas vous tromper. »
À la fin de l’exposé du général, Ecco se tourna vers moi :
« Qu’en pensez-vous, professeur ?
– On a neuf personnes, dont l’animateur, et quatre chemins possibles. Comme le groupe est perdu, n’importe quel chemin est possible. Je pense qu’il serait utile que l’animateur participe aux recherches. Envoyer trois personnes dans trois chemins différents et leur demander de revenir au bout de vingt minutes serait peut-être une bonne idée.
– Mais supposons que deux équipes reviennent en disant que le camp n’est pas au bout de leur chemin. Supposez ensuite que deux campeurs de la troisième équipe disent que le camp se trouve au bout de leur chemin et que le troisième prétende le contraire. Vous ne sauriez pas si le bon chemin est le troisième ou s’il s’agit de celui qui n’a pas été exploré. C’est délicat parce que les menteurs mentent peut-être mais pas forcément.
– Exact. Mais trois chemins devraient suffire. »
Ecco ne répondit pas. Il était plongé dans ses pensées. Au bout d’un moment, il s’exclama en souriant :
« Professeur, l’animateur ne ment pas. » Quelques minutes plus tard, il expliquait sa solution au général.
Essayez de résoudre le problème en vous servant de l’observation d’Ecco.
En suivant la suggestion d’Ecco, envoyez l’animateur dans un chemin, trois campeurs dans un deuxième, trois autres dans un troisième et deux dans un quatrième. Chaque groupe marche vingt minutes, vérifie si le camp est bien là, revient, et chacun des campeurs dit ce qu’il croit être le résultat. L’animateur prend alors sa décision de la manière suivante.
Si c’est lui qui a trouvé le camp, il y conduit ses compagnons. S’il y a désaccord au sein des deux groupes de trois campeurs, il retient l’opinion majoritaire (il ne peut y avoir qu’un menteur par groupe). S’il y a désaccord dans un groupe de trois et dans un groupe de deux, il retient l’opinion majoritaire du groupe de trois et ignore le groupe de deux. S’il y a désaccord au sein d’un seul groupe, il ignore les réponses de ce groupe. S’il n’y a de désaccord dans aucun des groupes, il ignore le groupe des deux campeurs.
La solution d’Ecco eut l’air de satisfaire le général qui avait encore une question en réserve : « Docteur Ecco, il est possible que les… campeurs ne soient que sept. Pouvez-vous résoudre le problème dans ce cas de figure ? »
Donnez une solution ou démontrez qu’aucune solution n’est possible avec sept campeurs.
Avec seulement sept campeurs, il faut que deux chemins (appelons-les A et B) soient explorés par seulement quatre campeurs, sans l’animateur. Supposons que ni l’animateur, ni le reste des campeurs ne trouvent le camp au bout des chemins qu’ils explorent. Si quatre campeurs explorent le chemin A et que personne n’explore le chemin B, le groupe de quatre peut revenir partagé, deux disant oui et deux disant non.
L’animateur ne saurait pas alors s’il convient de prendre le chemin A ou le chemin B. Si trois campeurs explorent le chemin A et que personne n’explore le chemin B, tout désaccord en A laisse également ouvertes ces deux possibilités. Si la répartition est de deux fois deux, si les deux équipes reviennent avec la même réponse, l’animateur n’a de nouveau pas les moyens de décider.
Le général appela quelques jours plus tard pour demander la solution d’un problème bien plus difficile. « Docteur Ecco, supposons qu’il y ait cinq menteurs. Dans ce cas, combien de campeurs seraient indispensables pour trouver le camp et comment vous y prendriez-vous ? »
Essayez de démontrer que le nombre que vous choisissez est le plus petit possible. Il devrait être inférieur à 20.
Avec cinq menteurs potentiels, il faut dix-sept campeurs. L’animateur explore de nouveau un chemin tout seul. Il envoie six campeurs dans deux chemins et cinq dans le quatrième. Voilà comment évaluer les réponses.
S’il n’y a désaccord dans aucune équipe, ignorez l’équipe de cinq. S’il y a désaccord dans une équipe, ignorez-la. S’il y a désaccord dans deux équipes ou plus, l’animateur doit tenir le raisonnement suivant : dans chaque équipe où il y a désaccord, compter le nombre des campeurs en minorité (s’il y a trois voix contre trois, la minorité sera alors de trois). Ce chiffre est le chiffre minimum de menteurs dans cette équipe. Dans toute équipe où le nombre des réponses du camp majoritaire est plus de cinq moins le total du nombre minimum de menteurs dans toutes les autres équipes, faire confiance à cette majorité. Cette procédure plus les conclusions de l’animateur pour le chemin qu’il explore donneront toujours une réponse à propos de trois des quatre chemins.
Avec seulement seize campeurs, deux chemins ne peuvent être explorés que par dix campeurs. Si cinq peuvent mentir, aucune solution ne convient.
Après avoir répondu à cette question, Ecco se détendit… « Cela m’a tout l’air d’un problème de communications, Scarlet. Il arrive aux émetteurs de tomber en panne, comme il arrive à des gens de mentir, mais peut-être savent-ils qu’il est très improbable que plus de deux émetteurs tombent en panne en même temps.
– Et l’animateur en qui on a toute confiance ?
– Oui, je dois réfléchir au rôle qu’il pourrait jouer. »
Le téléphone ne lui en laissa pas le temps. C’était le général.
Docteur Ecco, je vais vous soumettre le problème peut-être le plus difficile de tous. Supposez que vous n’ayez que quatre campeurs et l’animateur, mais qu’il arrive à deux d’entre eux de mentir de temps à autre. Quoi qu’il en soit, vous avez cent minutes – le temps de deux allers-retours complets – pour prendre la décision. Y-a-t-il une solution ? »
Qu’en pensez-vous ?
Ecco me regarda.
« Cela me paraît difficile, dis-je. Avec quatre campeurs, rien ne dit que ceux qui disent la vérité peuvent l’emporter sur les menteurs.
Mais peut-être pouvons-nous jouer de nouveau sur le fait que le camp ne peut se trouver qu’au bout d’un chemin.
– Suggestion très prometteuse, dit Ecco si vite que je compris qu’il en examinait déjà les implications. Mon général, nous allons y réfléchir, nous vous rappellerons.
– Parfait, Ecco. Mais faites vite, s’il vous plaît. En outre, ce serait bien si vous pouviez éviter à certains des campeurs de faire les deux voyages. »
Ecco se mit aussitôt au travail avec beaucoup d’énergie, mais il s’interrompit trois ou quatre fois en grommelant, froissa sa feuille et la jeta au panier. Je cherchai de mon côté, mais sans succès. Ecco s’arrêta, appuya sa tête contre le dossier de sa chaise, et réfléchit, les yeux fixés au plafond. Je me mis à penser à autre chose. Soudain Ecco se mit à rire.
« Eh bien, professeur, vous avez encore gagné. Je peux résoudre le problème. Mon raisonnement repose sur vos observations, qui sont excellentes bien qu’énigmatiques. Vous noterez qu’au moins trois des quatre campeurs ne sont pas obligés de faire le second voyage. »
Résolvez le problème avec quatre campeurs, dont deux menteurs occasionnels. Vous avez le temps pour deux voyages d’exploration et une marche finale vers le site. Notez que chacun des menteurs peut mentir quand cela lui chante. Par exemple, il peut mentir après le premier voyage et non après le second, et vice versa.
Il serait plausible de conclure que l’animateur peut explorer deux chemins (appelons-les A et B) en deux voyages et que les campeurs peuvent s’occuper d’au moins un des deux autres chemins (C et D). Mais ça ne marche pas. Supposons que l’animateur ne trouve pas le camp. La première observation du professeur (à savoir qu’avec quatre campeurs, on ne peut être assuré d’une majorité de campeurs disant la vérité) suggère que l’animateur ne peut savoir avec certitude lequel des chemins C ou D mène le camp. Supposons que les réponses des menteurs impliquent C et que celles de ceux qui disent la vérité impliquent D. Comme on se retrouve encore avec deux contre deux, la symétrie empêche toute solution.
La seconde observation du professeur suggère qu’il faudrait traiter différemment les réponses positives et les réponses négatives des campeurs. Voici comment.
Au premier voyage, l’animateur prend le chemin A. Les quatre campeurs prennent le chemin B.
Quand ils se retrouvent tous, si l’animateur a trouvé le camp, tout le monde prend le chemin A. Si trois ou quatre campeurs sont d’accord pour B, alors B est le bon. Si trois ou quatre campeurs s’accordent pour dire qu’il ne s’agit pas de B, alors l’animateur vérifie le chemin C au deuxième voyage, et tous les campeurs se reposent.
Maintenant le cas difficile. Si deux disent que le camp est au bout de B et que deux autres disent que non, l’animateur part explorer de nouveau le chemin B. On enverra l’un de ceux qui ont dit qu’il ne s’agissait pas de B dans le chemin C. Si l’animateur trouve le camp, il s’agit bien du chemin B. Si l’animateur ne le trouve pas, alors le campeur qui a exploré C doit dire la vérité, parce que les menteurs sont ceux qui ont prétendu que le camp était au bout de B.
« Votre solution est la simplicité même. Pourtant, elle est tellement différente des précédentes, m’émerveillai-je. En outre, vous n’utilisez au plus qu’un campeur dans le second voyage. Je ne peux m’empêcher de me demander si trois campeurs ne suffiraient pas.
– Si vous saviez que les deux menteurs donneront toujours la même réponse s’ils empruntaient le même chemin, vous pourriez certainement y arriver. »
À ce jour, je n’ai toujours pas trouvé la solution.
Il arrive aux circuits et aux branchements informatiques de tomber en panne, ce qui n’est souvent que temporaire. Des méthodes spéciales pour détecter et corriger ce type de pannes « intermittentes » sont intégrées dans le circuit mémoire de la plupart des ordinateurs modernes.
Cette énigme a été publiée dans le livre Les Aventures extraordinaires du Docteur Ecco, Éditions Odile Jacob, nouvelle édition juin 2006.
Newsletter
Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité
Niveau de lecture
Aidez-nous à évaluer le niveau de lecture de ce document.
Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !
Dennis Shasha