Interstices


  Ludique

Le problème des campeurs

Le Dr Jacob Ecco est un détective mathématique qui résout des énigmes. Ces énigmes s'inspirent des méthodes et du mode de réflexion des informaticiens et des mathématiciens.
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.

Photo by Neeraj Tripathi, sur Flickr.

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. (Voir la solution)
 

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. (Voir la solution)
 

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. (Voir la solution)
 

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. (Voir la solution)
 

« 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.

Et quel rapport avec l'informatique

Cette énigme a été publiée dans le livre Les Aventures extraordinaires du Docteur Ecco, Éditions Odile Jacob, nouvelle édition juin 2006.