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 renard, Fox, est dans l’un de ces cinq terriers alignés.
Chaque nuit, Fox passe dans un terrier contigu à 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
Précisons d’emblée un point qui a fait débat : pour Rabah, « trouver Fox » signifie : pouvoir identifier le terrier dans lequel il se trouve à l’issue d’une observation, même s’il ne se trouve pas dans le dernier terrier observé.
Pour nous qui rédigeons cet article, « trouver Fox » aura un sens plus contraignant et signifiera : déterminer une stratégie qui nous assure de voir effectivement Fox, de le débusquer dans son terrier.
Une solution de ce défi sera donnée dans le défi suivant !
(une extension à n terriers du premier défi)
Une petite application avec son mode d’emploi nous accompagnera tout au long des différents défis et nous aidera dans notre réflexion…
Pour modéliser le problème, nous numérotons les terriers de 1 à 5. Ensuite, pour résumer une stratégie (qu’elle permette ou non de trouver Fox) nous donnons la suite des terriers observés. Par exemple « 2, 5, 4 » (qui se lit « deux, cinq, quatre ») signifie « d’abord, nous regardons dans le terrier 2, puis dans le 5 et enfin dans le 4 ».
La stratégie « 2, 5, 4 » permet-elle de trouver à coup sûr Fox ? Non, comme le montre l’exemple ci-dessous :
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 à prouver qu’une stratégie n’est pas gagnante puisqu’elle 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.
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.
Ne poursuivez pas votre lecture si vous préférez chercher seul•e une solution.
— 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).
Retrouvez les autres défis et l'application
L’application
2e défi
3e défi
4e défi
5e défi
6e défi
Solution du dernier défi
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 - INSPÉ Lille Nord de France - Université du Littoral Côte d'Opale
