Problème "Fox and Holes"
Voici un petit problème de logique tel que l’a envoyé Rabah Bouhallel, un ami de longue date.
Un dessin est fourni présentant 5 terriers alignés,
puis le texte
Un renard, Fox, est dans l’un des cinq terriers.
Chaque nuit, Fox passe dans un terrier voisin de celui qu’il occupe.
Chaque jour, nous pouvons regarder dans l’un des terriers pour voir si Fox y est.
Donner une stratégie pour trouver Fox
Appropriation, modélisation
Levons d’emblée un point qui a fait débat : pour Rabah, « trouver Fox » désigne le fait de pouvoir identifier le terrier dans lequel se trouve Fox à l’issue d’une observation de l’un des terriers, même si Fox ne se situe pas dans le terrier dans lequel nous regardons ; pour nous, « trouver Fox » exige que nous regardons dans un terrier dans lequel on peut effectivement voir Fox. Nous avons l’avantage de pouvoir rédiger cet article et donc opter pour notre interprétation de « trouver Fox » : pour répondre au problème, il faut donc donner une stratégie qui assure que nous puissions regarder dans le terrier dans lequel Fox se trouve.
Une petite application avec son mode d’emploi nous accompagnera tout au long de l’article et nous aidera dans notre réflexion…
Pour modéliser le problème, nous pouvons numéroter les terriers de 1 à 5. Ensuite, pour résumer une stratégie (pas nécessairement qui permette de trouver Fox) nous pouvons écrire une suite comme « 2, 5, 4 » qui se lit « deux, cinq, quatre » et qui résume « d’abord, nous regardons dans le terrier numéro 2, puis dans le numéro 5 et enfin dans le numéro 4 ».
Plus généralement, nous donnons la suite des terriers observés.
Non, comme le montre l’exemple ci-dessous, la stratégie « 2, 5, 4 » ne permet pas de trouver à coup sûr Fox :
Jour 1 : Si Fox est dans le terrier 1, on regarde dans le terrier 2 et Fox ne s’y trouve pas.
Jour 2 : Si Fox passe ensuite dans le terrier 2, on regarde dans le terrier 5 et Fox ne s’y trouve pas non plus.
Jour 3 : Si Fox passe enfin dans le terrier 3, on regarde dans le terrier 4 et Fox ne s’y trouve toujours pas.
Le fait de trouver un seul exemple de positions successives du renard dans lequel ce dernier se soustrait à notre regard suffit à invalider une stratégie : cette stratégie ne garantit pas de trouver Fox.
Invitation à chercher une solution
Ce problème peut sembler décourageant car
— nous n’avons aucune idée de la longueur de la procédure cherchée
— pour tester une stratégie, nous avons de nombreuses éventualités à évaluer.
Ci-dessous, une aide un peu plus conséquente à la résolution du problème. Ne poursuivez pas votre lecture si vous préférez chercher seul•e une solution.
Pour amoindrir les effets des points précédemment cités pouvant mener à un certain découragement, voici quelques indices pour trouver une solution au problème.
— Sachez qu’il nous est possible de trouver une stratégie pour trouver Fox en six observations.
— Pour tester une stratégie, au lieu de regarder tous les cas, un à un, on peut aussi regrouper ces cas (par exemple, selon la parité du terrier dans lequel Fox se trouve) et / ou limiter ces cas (par exemple, en utilisant de la symétrie).
Post-scriptum
La rédaction d’Images des maths, ainsi que les auteurs, remercient pour leur relecture attentive, les relecteurs dont le pseudonyme est le suivant -projetmbc, Walter et Gautier Dietrich.
ÉCRIT PAR
François Dessenne
Maître de conférences - Université de Lille
Jean Fromentin
Professeur - Université du Littoral Côte d’Opale, Calais
Denis Vekemans
Maître de Conférences - ÉSPÉ Lille Nord de France - Université Littoral Côte d'Opale
