Problème "Fox and Holes" avec augmentation des possibilités du renard
Rappel du défi
Un renard, Fox, est dans l’un de cinq terriers alignés.
Chaque nuit, Fox reste dans son terrier ou 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. Pouvons-nous trouver une stratégie pour trouver Fox ?
Appropriation
Une stratégie valide doit l’être pour n’importe quel trajet du renard et, en particulier, quand le renard connaît notre stratégie et tente de s’y soustraire. Le problème précédent n’a pas de solution !
En effet, admettons que le renard soit sur une case \(i\) pour \(i\) allant de 1 à 5, de cette case, il a toujours au moins deux (il en a trois pour \( i=2,i=3\) et \(i=4\) ,mais seulement deux pour \(i=1\) et \( i=5\) ) possibilités de déplacement (ce minimum n’était que de 1 pour le problème « Fox and Holes » et cela nous a permis de trouver une stratégie solution pour ce problème). S’il sait que nous allons observer dans l’un de ces deux terriers, il lui suffit d’opter pour l’autre afin de se soustraire à notre observation. Cet argument suffit à montrer qu’il ne peut y avoir de stratégie capable de déceler Fox à coup sûr.
Du coup, si on autorise trois déplacements au renard, on doit sans doute autoriser deux observations par jour pour pouvoir trouver Fox.
En réalité, en mobilisant la même démonstration que ci-dessus, on pourrait démontrer la propriété plus générale suivante : « si de n’importe quelle position, le renard a au moins k déplacements disponibles, avec strictement moins de \(k\) observations, il sera impossible de trouver une stratégie capable de trouver Fox de façon certaine ».
Problème "Fox and Holes" avec augmentation des possibilités du renard et du nombre d’observations
Rappel du défi
Un renard, Fox, est dans l’un de cinq terriers alignés.
Chaque nuit, Fox reste dans son terrier ou passe dans un terrier voisin de celui qu’il occupe.
Chaque jour, nous pouvons regarder dans deux des terriers pour voir si Fox y est.
Donner une stratégie pour trouver Fox.
Solution
Initialement, le renard est en 1, 2, 3, 4 ou 5.
En observant en 1 et en 2, soit on le trouve, soit il était en 3, 4 ou 5 et peut donc atteindre 2, 3, 4 ou 5.
En observant ensuite en 2 et en 3, soit on le trouve, soit il était juste précédemment en 4 ou 5 et peut donc atteindre 3, 4 ou 5.
En observant ensuite en 3 et en 4, soit on le trouve, soit il était juste précédemment en 5 et peut donc atteindre 4 ou 5.
Enfin, en observant ensuite en 4 et en 5, on le trouve.
Cette stratégie se note « (1 ; 2), (2 ; 3), (3 ; 4), (4 ; 5) ».
Problème "Fox and Holes" avec augmentation des possibilités du renard et du nombre d’observations, un peu plus complexe
Rappel du défi
Un renard, Fox, est dans l’un de six terriers alignés.
Chaque nuit, Fox reste dans son terrier ou passe du terrier occupé à l’un des deux terriers parmi celui juste à gauche et celui juste à droite de celui juste à droite.
Chaque jour, nous pouvons regarder dans deux des terriers pour voir si Fox y est.
Donner une stratégie pour trouver Fox.
Solution
Initialement, le renard est en 1, 2, 3, 4, 5 ou 6.
En observant en 1 et en 2, soit on le trouve, soit il était en 3, 4, 5 ou 6 et peut donc atteindre 2, 3, 4, 5 ou 6.
En observant ensuite en 2 et en 3, soit on le trouve, soit il était juste précédemment en 4, 5 ou 6 et peut donc atteindre 3, 4, 5 ou 6.
En observant ensuite en 3 et en 4, soit on le trouve, soit il était juste précédemment en 5 ou 6 et peut donc atteindre 4, 5 ou 6.
En observant ensuite en 4 et en 5, soit on le trouve, soit il était juste précédemment en 6 et peut donc atteindre 5 ou 6.
Enfin, en observant ensuite en 5 et en 6, on le trouve.
Cette stratégie se note « (1 ; 2), (2 ; 3), (3 ; 4), (4 ; 5), (5 ; 6) ».
Problème "Fox and Holes" avec augmentation des possibilités du renard et du nombre d’observations, encore un peu plus complexe
Rappel du défi
Un renard, Fox, est dans l’un de six terriers alignés.
Chaque nuit, Fox reste dans son terrier ou passe du terrier occupé à l’un des deux terriers parmi celui situé à 2 terriers vers la gauche et celui situé à 3 terriers vers la droite.
Chaque jour, nous pouvons regarder dans deux des terriers pour voir si Fox y est.
Donner une stratégie pour trouver Fox.
Solution
Initialement, le renard est en 1, 2, 3, 4, 5 ou 6.
En observant en 2 et en 5, soit on le trouve, soit il était en 1, 3, 4 ou 6 et peut donc atteindre 1, 2, 3, 4 ou 6.
En observant ensuite en 1 et en 3, soit on le trouve, soit il était juste précédemment en 2, 4 ou 6 et peut donc atteindre 2, 4, 5 ou 6.
En observant ensuite en 2 et en 5, soit on le trouve, soit il était juste précédemment en 4 ou 6 et peut donc atteindre 2, 4 ou 6.
En observant ensuite en 2 et en 4, soit on le trouve, soit il était juste précédemment en 6 et peut donc atteindre 4 ou 6.
Enfin, en observant ensuite en 4 et en 6, on le trouve.
Cette stratégie se note « (2 ; 5), (1 ; 3), (2 ; 5), (2 ; 4), (4 ; 6) ».
Les 117 stratégies pour trouver Fox en 5 jours sont :
« ( 1 ; 3), ( 3 ; 5), ( 2 ; 5), ( 2 ; 4), ( 4 ; 6) »
« ( 1 ; 3), ( 3 ; 5), ( 2 ; 5), ( 2 ; 6), ( 2 ; 4) »
« ( 1 ; 3), ( 3 ; 5), ( 2 ; 5), ( 4 ; 6), ( 2 ; 5) »
« ( 1 ; 3), ( 3 ; 5), ( 4 ; 6), ( 2 ; 3), ( 3 ; 5) »
« ( 1 ; 3), ( 3 ; 5), ( 4 ; 6), ( 3 ; 5), ( 2 ; 5) »
« ( 1 ; 3), ( 3 ; 5), ( 5 ; 6), ( 2 ; 4), ( 3 ; 5) »
« ( 1 ; 3), ( 3 ; 5), ( 5 ; 6), ( 2 ; 5), ( 2 ; 4) »
« ( 1 ; 3), ( 3 ; 5), ( 5 ; 6), ( 4 ; 5), ( 2 ; 5) »
« ( 1 ; 3), ( 3 ; 6), ( 3 ; 4), ( 2 ; 3), ( 3 ; 5) »
« ( 1 ; 3), ( 3 ; 6), ( 3 ; 4), ( 3 ; 5), ( 2 ; 5) »
« ( 1 ; 3), ( 3 ; 6), ( 3 ; 5), ( 2 ; 4), ( 3 ; 5) »
« ( 1 ; 3), ( 3 ; 6), ( 3 ; 5), ( 2 ; 5), ( 2 ; 4) »
« ( 1 ; 3), ( 3 ; 6), ( 3 ; 5), ( 4 ; 5), ( 2 ; 5) »
« ( 2 ; 4), ( 3 ; 5), ( 1 ; 2), ( 2 ; 4), ( 4 ; 6) »
« ( 2 ; 4), ( 3 ; 5), ( 1 ; 2), ( 2 ; 6), ( 2 ; 4) »
« ( 2 ; 4), ( 3 ; 5), ( 1 ; 2), ( 4 ; 6), ( 2 ; 5) »
« ( 2 ; 4), ( 3 ; 5), ( 1 ; 6), ( 2 ; 4), ( 3 ; 5) »
« ( 2 ; 4), ( 3 ; 5), ( 1 ; 6), ( 2 ; 5), ( 2 ; 4) »
« ( 2 ; 4), ( 3 ; 5), ( 1 ; 6), ( 4 ; 5), ( 2 ; 5) »
« ( 2 ; 4), ( 3 ; 5), ( 2 ; 4), ( 1 ; 4), ( 4 ; 6) »
« ( 2 ; 4), ( 3 ; 5), ( 2 ; 4), ( 1 ; 6), ( 2 ; 4) »
« ( 2 ; 4), ( 3 ; 5), ( 2 ; 4), ( 4 ; 6), ( 1 ; 4) »
« ( 2 ; 4), ( 3 ; 5), ( 2 ; 6), ( 1 ; 2), ( 2 ; 4) »
« ( 2 ; 4), ( 3 ; 5), ( 2 ; 6), ( 1 ; 4), ( 2 ; 5) »
« ( 2 ; 4), ( 3 ; 5), ( 2 ; 6), ( 2 ; 4), ( 1 ; 4) »
« ( 2 ; 4), ( 4 ; 5), ( 1 ; 3), ( 2 ; 4), ( 4 ; 6) »
« ( 2 ; 4), ( 4 ; 5), ( 1 ; 3), ( 2 ; 6), ( 2 ; 4) »
« ( 2 ; 4), ( 4 ; 5), ( 1 ; 3), ( 4 ; 6), ( 2 ; 5) »
« ( 2 ; 4), ( 4 ; 5), ( 3 ; 4), ( 1 ; 4), ( 4 ; 6) »
« ( 2 ; 4), ( 4 ; 5), ( 3 ; 4), ( 1 ; 6), ( 2 ; 4) »
« ( 2 ; 4), ( 4 ; 5), ( 3 ; 4), ( 4 ; 6), ( 1 ; 4) »
« ( 2 ; 4), ( 4 ; 5), ( 3 ; 6), ( 1 ; 2), ( 2 ; 4) »
« ( 2 ; 4), ( 4 ; 5), ( 3 ; 6), ( 1 ; 4), ( 2 ; 5) »
« ( 2 ; 4), ( 4 ; 5), ( 3 ; 6), ( 2 ; 4), ( 1 ; 4) »
« ( 2 ; 5), ( 1 ; 3), ( 2 ; 5), ( 2 ; 4), ( 4 ; 6) » (celle trouvée plus haut)
« ( 2 ; 5), ( 1 ; 3), ( 2 ; 5), ( 2 ; 6), ( 2 ; 4) »
« ( 2 ; 5), ( 1 ; 3), ( 2 ; 5), ( 4 ; 6), ( 2 ; 5) »
« ( 2 ; 5), ( 1 ; 3), ( 4 ; 6), ( 2 ; 3), ( 3 ; 5) »
« ( 2 ; 5), ( 1 ; 3), ( 4 ; 6), ( 3 ; 5), ( 2 ; 5) »
« ( 2 ; 5), ( 1 ; 3), ( 5 ; 6), ( 2 ; 4), ( 3 ; 5) »
« ( 2 ; 5), ( 1 ; 3), ( 5 ; 6), ( 2 ; 5), ( 2 ; 4) »
« ( 2 ; 5), ( 1 ; 3), ( 5 ; 6), ( 4 ; 5), ( 2 ; 5) »
« ( 2 ; 5), ( 2 ; 3), ( 1 ; 2), ( 2 ; 4), ( 4 ; 6) »
« ( 2 ; 5), ( 2 ; 3), ( 1 ; 2), ( 2 ; 6), ( 2 ; 4) »
« ( 2 ; 5), ( 2 ; 3), ( 1 ; 2), ( 4 ; 6), ( 2 ; 5) »
« ( 2 ; 5), ( 2 ; 3), ( 1 ; 6), ( 2 ; 4), ( 3 ; 5) »
« ( 2 ; 5), ( 2 ; 3), ( 1 ; 6), ( 2 ; 5), ( 2 ; 4) »
« ( 2 ; 5), ( 2 ; 3), ( 1 ; 6), ( 4 ; 5), ( 2 ; 5) »
« ( 2 ; 5), ( 2 ; 3), ( 2 ; 4), ( 1 ; 4), ( 4 ; 6) »
« ( 2 ; 5), ( 2 ; 3), ( 2 ; 4), ( 1 ; 6), ( 2 ; 4) »
« ( 2 ; 5), ( 2 ; 3), ( 2 ; 4), ( 4 ; 6), ( 1 ; 4) »
« ( 2 ; 5), ( 2 ; 3), ( 2 ; 6), ( 1 ; 2), ( 2 ; 4) »
« ( 2 ; 5), ( 3 ; 6), ( 2 ; 5), ( 1 ; 2), ( 2 ; 4) »
« ( 2 ; 5), ( 3 ; 6), ( 2 ; 5), ( 1 ; 4), ( 2 ; 5) »
« ( 2 ; 5), ( 3 ; 6), ( 2 ; 5), ( 2 ; 4), ( 1 ; 4) »
« ( 3 ; 5), ( 1 ; 5), ( 2 ; 5), ( 2 ; 4), ( 4 ; 6) »
« ( 2 ; 5), ( 2 ; 3), ( 2 ; 6), ( 1 ; 4), ( 2 ; 5) »
« ( 2 ; 5), ( 2 ; 3), ( 2 ; 6), ( 2 ; 4), ( 1 ; 4) »
« ( 2 ; 5), ( 2 ; 4), ( 1 ; 3), ( 2 ; 4), ( 4 ; 6) »
« ( 2 ; 5), ( 2 ; 4), ( 1 ; 3), ( 2 ; 6), ( 2 ; 4) »
« ( 2 ; 5), ( 2 ; 4), ( 1 ; 3), ( 4 ; 6), ( 2 ; 5) »
« ( 2 ; 5), ( 2 ; 4), ( 3 ; 4), ( 1 ; 4), ( 4 ; 6) »
« ( 2 ; 5), ( 2 ; 4), ( 3 ; 4), ( 1 ; 6), ( 2 ; 4) »
« ( 2 ; 5), ( 2 ; 4), ( 3 ; 4), ( 4 ; 6), ( 1 ; 4) »
« ( 2 ; 5), ( 2 ; 4), ( 3 ; 6), ( 1 ; 2), ( 2 ; 4) »
« ( 2 ; 5), ( 2 ; 4), ( 3 ; 6), ( 1 ; 4), ( 2 ; 5) »
« ( 2 ; 5), ( 2 ; 4), ( 3 ; 6), ( 2 ; 4), ( 1 ; 4) »
« ( 2 ; 5), ( 3 ; 6), ( 1 ; 4), ( 2 ; 3), ( 3 ; 5) »
« ( 2 ; 5), ( 3 ; 6), ( 1 ; 4), ( 3 ; 5), ( 2 ; 5) »
« ( 2 ; 5), ( 3 ; 6), ( 1 ; 5), ( 2 ; 4), ( 3 ; 5) »
« ( 2 ; 5), ( 3 ; 6), ( 1 ; 5), ( 2 ; 5), ( 2 ; 4) »
« ( 2 ; 5), ( 3 ; 6), ( 1 ; 5), ( 4 ; 5), ( 2 ; 5) »
« ( 3 ; 5), ( 1 ; 5), ( 2 ; 5), ( 2 ; 6), ( 2 ; 4) »
« ( 3 ; 5), ( 1 ; 5), ( 2 ; 5), ( 4 ; 6), ( 2 ; 5) »
« ( 3 ; 5), ( 1 ; 5), ( 4 ; 6), ( 2 ; 3), ( 3 ; 5) »
« ( 3 ; 5), ( 1 ; 5), ( 4 ; 6), ( 3 ; 5), ( 2 ; 5) »
« ( 3 ; 5), ( 1 ; 5), ( 5 ; 6), ( 2 ; 4), ( 3 ; 5) »
« ( 3 ; 5), ( 1 ; 5), ( 5 ; 6), ( 2 ; 5), ( 2 ; 4) »
« ( 3 ; 5), ( 1 ; 5), ( 5 ; 6), ( 4 ; 5), ( 2 ; 5) »
« ( 3 ; 5), ( 1 ; 6), ( 3 ; 4), ( 2 ; 3), ( 3 ; 5) »
« ( 3 ; 5), ( 1 ; 6), ( 3 ; 4), ( 3 ; 5), ( 2 ; 5) »
« ( 3 ; 5), ( 1 ; 6), ( 3 ; 5), ( 2 ; 4), ( 3 ; 5) »
« ( 3 ; 5), ( 1 ; 6), ( 3 ; 5), ( 2 ; 5), ( 2 ; 4) »
« ( 3 ; 5), ( 1 ; 6), ( 3 ; 5), ( 4 ; 5), ( 2 ; 5) »
« ( 3 ; 5), ( 2 ; 5), ( 1 ; 2), ( 2 ; 4), ( 4 ; 6) »
« ( 3 ; 5), ( 2 ; 5), ( 1 ; 2), ( 2 ; 6), ( 2 ; 4) »
« ( 3 ; 5), ( 2 ; 5), ( 1 ; 2), ( 4 ; 6), ( 2 ; 5) »
« ( 3 ; 5), ( 2 ; 5), ( 1 ; 6), ( 2 ; 4), ( 3 ; 5) »
« ( 3 ; 5), ( 2 ; 5), ( 1 ; 6), ( 2 ; 5), ( 2 ; 4) »
« ( 3 ; 5), ( 2 ; 5), ( 1 ; 6), ( 4 ; 5), ( 2 ; 5) »
« ( 3 ; 5), ( 2 ; 5), ( 2 ; 4), ( 1 ; 4), ( 4 ; 6) »
« ( 3 ; 5), ( 2 ; 5), ( 2 ; 4), ( 1 ; 6), ( 2 ; 4) »
« ( 3 ; 5), ( 2 ; 5), ( 2 ; 4), ( 4 ; 6), ( 1 ; 4) »
« ( 3 ; 5), ( 2 ; 5), ( 2 ; 6), ( 1 ; 2), ( 2 ; 4) »
« ( 3 ; 5), ( 2 ; 5), ( 2 ; 6), ( 1 ; 4), ( 2 ; 5) »
« ( 3 ; 5), ( 2 ; 5), ( 2 ; 6), ( 2 ; 4), ( 1 ; 4) »
« ( 3 ; 5), ( 5 ; 6), ( 1 ; 4), ( 2 ; 3), ( 3 ; 5) »
« ( 3 ; 5), ( 5 ; 6), ( 1 ; 4), ( 3 ; 5), ( 2 ; 5) »
« ( 3 ; 5), ( 5 ; 6), ( 1 ; 5), ( 2 ; 4), ( 3 ; 5) »
« ( 3 ; 5), ( 5 ; 6), ( 1 ; 5), ( 2 ; 5), ( 2 ; 4) »
« ( 3 ; 5), ( 5 ; 6), ( 1 ; 5), ( 4 ; 5), ( 2 ; 5) »
« ( 3 ; 5), ( 5 ; 6), ( 2 ; 5), ( 1 ; 2), ( 2 ; 4) »
« ( 3 ; 5), ( 5 ; 6), ( 2 ; 5), ( 1 ; 4), ( 2 ; 5) »
« ( 3 ; 5), ( 5 ; 6), ( 2 ; 5), ( 2 ; 4), ( 1 ; 4) »
« ( 3 ; 6), ( 1 ; 3), ( 3 ; 4), ( 2 ; 3), ( 3 ; 5) »
« ( 3 ; 6), ( 1 ; 3), ( 3 ; 4), ( 3 ; 5), ( 2 ; 5) »
« ( 3 ; 6), ( 1 ; 3), ( 3 ; 5), ( 2 ; 4), ( 3 ; 5) »
« ( 3 ; 6), ( 1 ; 3), ( 3 ; 5), ( 2 ; 5), ( 2 ; 4) »
« ( 3 ; 6), ( 1 ; 3), ( 3 ; 5), ( 4 ; 5), ( 2 ; 5) »
« ( 3 ; 6), ( 3 ; 5), ( 1 ; 4), ( 2 ; 3), ( 3 ; 5) »
« ( 3 ; 6), ( 3 ; 5), ( 1 ; 4), ( 3 ; 5), ( 2 ; 5) »
« ( 3 ; 6), ( 3 ; 5), ( 1 ; 5), ( 2 ; 4), ( 3 ; 5) »
« ( 3 ; 6), ( 3 ; 5), ( 1 ; 5), ( 2 ; 5), ( 2 ; 4) »
« ( 3 ; 6), ( 3 ; 5), ( 1 ; 5), ( 4 ; 5), ( 2 ; 5) »
« ( 3 ; 6), ( 3 ; 5), ( 2 ; 5), ( 1 ; 2), ( 2 ; 4) »
« ( 3 ; 6), ( 3 ; 5), ( 2 ; 5), ( 1 ; 4), ( 2 ; 5) »
« ( 3 ; 6), ( 3 ; 5), ( 2 ; 5), ( 2 ; 4), ( 1 ; 4) »
Problème "Fox and Holes" avec augmentation des possibilités du renard et du nombre d’observations, complexe
Rappel du défi
Un renard, Fox, est dans l’un de sept terriers alignés.
Chaque nuit, Fox reste dans son terrier ou passe du terrier occupé à l’un des deux terriers parmi celui situé à 2 terriers vers la gauche et celui situé à 3 terriers vers la droite.
Chaque jour, nous pouvons regarder dans deux des terriers pour voir si Fox y est.
Donner une stratégie pour trouver Fox.
Solution
Initialement, le renard est en 1, 2, 3, 4, 5, 6 ou 7.
En observant en 1 et en 3, soit on le trouve, soit il était en 2, 4, 5, 6 ou 7 et peut donc atteindre 2, 3, 4, 5, 6 ou 7.
En observant ensuite en 3 et en 6, soit on le trouve, soit il était juste précédemment en 2, 4, 5 ou 7 et peut donc atteindre 2, 3, 4, 5 ou 7.
En observant ensuite en 3 et en 4, soit on le trouve, soit il était juste précédemment en 2, 5 ou 7 et peut donc atteindre 2, 3, 5 ou 7.
En observant ensuite en 2 et en 3, soit on le trouve, soit il était juste précédemment en 5 ou 7 et peut donc atteindre 3, 5 ou 7.
En observant ensuite en 3 et en 5, soit on le trouve, soit il était juste précédemment en 5 et peut donc atteindre 5 ou 7.
Enfin, en observant ensuite en 5 et en 7, on le trouve.
Cette stratégie se note « (1 ; 3), (3 ; 6), (3 ; 4), (2, 3), (3, 5), (5, 7) »
Les 102 stratégies pour trouver Fox en 6 jours sont :
« (1 ; 3), (3 ; 5), (4 ; 6), (2 ; 3), (3 ; 5), (5 ; 7) »
« (1 ; 3), (3 ; 5), (4 ; 6), (2 ; 3), (3 ; 7), (3 ; 5) »
« (1 ; 3), (3 ; 5), (4 ; 6), (3 ; 5), (2 ; 5), (5 ; 7) »
« (1 ; 3), (3 ; 5), (4 ; 6), (3 ; 5), (2 ; 7), (3 ; 5) »
« (1 ; 3), (3 ; 5), (4 ; 6), (3 ; 5), (5 ; 7), (2 ; 5) »
« (1 ; 3), (3 ; 5), (4 ; 6), (3 ; 7), (2 ; 3), (3 ; 5) »
« (1 ; 3), (3 ; 5), (4 ; 6), (3 ; 7), (3 ; 5), (2 ; 5) »
« (1 ; 3), (3 ; 5), (5 ; 6), (2 ; 4), (3 ; 5), (5 ; 7) »
« (1 ; 3), (3 ; 5), (5 ; 6), (2 ; 4), (3 ; 7), (3 ; 5) »
« (1 ; 3), (3 ; 5), (5 ; 6), (4 ; 5), (2 ; 5), (5 ; 7) »
« (1 ; 3), (3 ; 5), (5 ; 6), (4 ; 5), (2 ; 7), (3 ; 5) »
« (1 ; 3), (3 ; 5), (5 ; 6), (4 ; 5), (5 ; 7), (2 ; 5) »
« (1 ; 3), (3 ; 5), (5 ; 6), (4 ; 7), (2 ; 3), (3 ; 5) »
« (1 ; 3), (3 ; 5), (5 ; 6), (4 ; 7), (3 ; 5), (2 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 4), (2 ; 3), (3 ; 5), (5 ; 7) » (celle trouvée plus haut)
« (1 ; 3), (3 ; 6), (3 ; 4), (2 ; 3), (3 ; 7), (3 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 4), (3 ; 5), (2 ; 5), (5 ; 7) »
« (1 ; 3), (3 ; 6), (3 ; 4), (3 ; 5), (2 ; 7), (3 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 4), (3 ; 5), (5 ; 7), (2 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 4), (3 ; 7), (2 ; 3), (3 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 4), (3 ; 7), (3 ; 5), (2 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 5), (2 ; 4), (3 ; 5), (5 ; 7) »
« (1 ; 3), (3 ; 6), (3 ; 5), (2 ; 4), (3 ; 7), (3 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 5), (4 ; 5), (2 ; 5), (5 ; 7) »
« (1 ; 3), (3 ; 6), (3 ; 5), (4 ; 5), (2 ; 7), (3 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 5), (4 ; 5), (5 ; 7), (2 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 5), (4 ; 7), (2 ; 3), (3 ; 5) »
« (1 ; 3), (3 ; 6), (3 ; 5), (4 ; 7), (3 ; 5), (2 ; 5) »
« (2 ; 4), (4 ; 7), (4 ; 5), (3 ; 4), (1 ; 4), (4 ; 6) »
« (2 ; 4), (4 ; 7), (4 ; 5), (3 ; 4), (4 ; 6), (1 ; 4) »
« (3 ; 5), (1 ; 5), (4 ; 6), (2 ; 3), (3 ; 5), (5 ; 7) »
« (3 ; 5), (1 ; 5), (4 ; 6), (2 ; 3), (3 ; 7), (3 ; 5) »
« (3 ; 5), (1 ; 5), (4 ; 6), (3 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 5), (1 ; 5), (4 ; 6), (3 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 5), (1 ; 5), (4 ; 6), (3 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 5), (1 ; 5), (4 ; 6), (3 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 5), (1 ; 5), (4 ; 6), (3 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 5), (1 ; 5), (5 ; 6), (2 ; 4), (3 ; 5), (5 ; 7) »
« (3 ; 5), (1 ; 5), (5 ; 6), (2 ; 4), (3 ; 7), (3 ; 5) »
« (3 ; 5), (1 ; 5), (5 ; 6), (4 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 5), (1 ; 5), (5 ; 6), (4 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 5), (1 ; 5), (5 ; 6), (4 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 5), (1 ; 5), (5 ; 6), (4 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 5), (1 ; 5), (5 ; 6), (4 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 4), (2 ; 3), (3 ; 5), (5 ; 7) »
« (3 ; 5), (1 ; 6), (3 ; 4), (2 ; 3), (3 ; 7), (3 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 4), (3 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 5), (1 ; 6), (3 ; 4), (3 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 4), (3 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 4), (3 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 4), (3 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 5), (2 ; 4), (3 ; 5), (5 ; 7) »
« (3 ; 5), (1 ; 6), (3 ; 5), (2 ; 4), (3 ; 7), (3 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 5), (4 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 5), (1 ; 6), (3 ; 5), (4 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 5), (4 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 5), (4 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 5), (1 ; 6), (3 ; 5), (4 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 4), (2 ; 3), (3 ; 5), (5 ; 7) »
« (3 ; 5), (5 ; 6), (1 ; 4), (2 ; 3), (3 ; 7), (3 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 4), (3 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 5), (5 ; 6), (1 ; 4), (3 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 5), (4 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 5), (4 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 5), (4 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 4), (2 ; 3), (3 ; 5), (5 ; 7) »
« (3 ; 5), (5 ; 6), (1 ; 4), (3 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 4), (3 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 4), (3 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 5), (2 ; 4), (3 ; 5), (5 ; 7) »
« (3 ; 5), (5 ; 6), (1 ; 5), (2 ; 4), (3 ; 7), (3 ; 5) »
« (3 ; 5), (5 ; 6), (1 ; 5), (4 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 5), (5 ; 6), (1 ; 5), (4 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 4), (2 ; 3), (3 ; 7), (3 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 4), (3 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 6), (1 ; 3), (3 ; 4), (3 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 4), (3 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 4), (3 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 4), (3 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 5), (2 ; 4), (3 ; 5), (5 ; 7) »
« (3 ; 6), (1 ; 3), (3 ; 5), (2 ; 4), (3 ; 7), (3 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 5), (4 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 6), (1 ; 3), (3 ; 5), (4 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 5), (4 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 5), (4 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 6), (1 ; 3), (3 ; 5), (4 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 4), (2 ; 3), (3 ; 5), (5 ; 7) »
« (3 ; 6), (3 ; 5), (1 ; 4), (2 ; 3), (3 ; 7), (3 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 4), (3 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 6), (3 ; 5), (1 ; 4), (3 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 4), (3 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 4), (3 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 4), (3 ; 7), (3 ; 5), (2 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 5), (2 ; 4), (3 ; 5), (5 ; 7) »
« (3 ; 6), (3 ; 5), (1 ; 5), (2 ; 4), (3 ; 7), (3 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 5), (4 ; 5), (2 ; 5), (5 ; 7) »
« (3 ; 6), (3 ; 5), (1 ; 5), (4 ; 5), (2 ; 7), (3 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 5), (4 ; 5), (5 ; 7), (2 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 5), (4 ; 7), (2 ; 3), (3 ; 5) »
« (3 ; 6), (3 ; 5), (1 ; 5), (4 ; 7), (3 ; 5), (2 ; 5) »
« (4 ; 7), (2 ; 4), (4 ; 5), (3 ; 4), (1 ; 4), (4 ; 6) »
« (4 ; 7), (2 ; 4), (4 ; 5), (3 ; 4), (4 ; 6), (1 ; 4) »
Programmation en C++
Programme en C++ qui génère dans un cadre limité à 32 terriers l’ensemble des solutions en un minimum de jours.
Programme de résolution
Vous trouverez ci-dessous un code source en C++ qui, une fois compilé, est capable de calculer les solutions pour N terriers (N < 32),
X observations (X < N) et M déplacements du renard (M < N) :
#include
#include
using namespace std ;
typedef unsigned int uint ;
struct terriers {
uint PresenceRenard ; /// champ de bits : 0 absence certaine du renard
static uint size ; /// nbre de terriers pour le renard et l’observateur (<32)
vector histoire ; /// histoire des observations successives
static vector MvtRenard ; /// déplacements rel. du renard ds les terriers
};
uint terriers::size = 0 ;
vector terriers::MvtRenard ;
/** Tableau à deux dimensions (jours x tableau de terriers) avec les présences
de renard à cardinalité minimale et unique pour chaque jour **/
vector<vector> CardMin(1,vector()) ;
/** retourne le nbre de terriers occupables par le renard (~ popcnt) **/
uint PossiblementOccupes(const terriers&) ;
/** retourne une structure terriers après l’application des déplacements possi-
bles du renard juste après les observations (paramètre passé en argument) **/
terriers DeplaceRenard(const terriers&) ;
/** fonct. recursive appliquant toutes les observations dans les terriers **/
void AjouterObservation(const terriers&, uint, uint,const uint,const uint) ;
/// *** Fonction principale ***************************************************
int main(void)
{
/** — La saisie des données d’entrée (aucun contrôle de validité) ——— **/
cout << « Des terriers et un renard » << endl ;
cout << « Donnez le nombre de terriers (<32) : » ; cin >> terriers::size ; /// saisie du nombre de terriers accessibles
cout << « Donnez le nombre d’observations (< » << terriers::size << « ) : » ; uint NbreObservations ; /// nombre d’observations possibles par jour. cin >> NbreObservations ;
uint NbrDeplacements ;
cout << « Donnez le nombre de deplacements possibles du renard (< »
<< terriers::size << « ) : » ; cin >> NbrDeplacements ;
cout << « Donnez le(s) » << NbrDeplacements << » deplacements un a un : » ;
while (terriers::MvtRenard.size() < NbrDeplacements) { int d ; cin >> d ;
terriers::MvtRenard.push_back(d) ;
}
cout << « Voulez-vous afficher les solutions (o/n) : » ; string rep ; cin >> rep ;
bool AfficheSol = (rep == « o ») ; /// (des-)active l’affichage des solutions
/** — Résumé des données d’entrée avant de débuter le calcul ————- **/
cout << « > » << terriers::size << » terriers. » << endl
<< « > » << NbreObservations << » observations par jour. » << endl
<< « > » << terriers::MvtRenard.size() << » deplacements autorises du renard : » ;
for (int d : terriers::MvtRenard) cout << » » << d ;
cout << endl ; /** — Début des calculs ————————————————– **/ uint day(0U) ; /// permet de compter les jours d’observations. CardMin.at(day).push_back(terriers{0xFFFFFFFFU}) ; /// tous les terriers occupés /** tant que l’on pas atteint des terriers tous non occupés par le renard **/ while (CardMin.at(day).begin()->PresenceRenard != 0x00000000U) {
/** allocation du vecteur de terriers pour le jour suivant **/
CardMin.push_back(vector()) ; /// allocation pour le jour suivant
/** parcours de toutes les configurations de terriers à analyser **/
for (terriers t : CardMin.at(day)) {
/** pour la config de terriers en cours, on fait les observations puis les
déplacements de renards en commançant par le terrier 0 et l’observation 1**/
AjouterObservation(t, 0, 1,NbreObservations, day) ;
}
day++ ; /// incrément du jours en cours
}
/** — Affichage des resultats ——————————————– **/
cout << « Trouve en » << day << » jours. » << endl ;
cout << « Nombre de solutions : » << CardMin.at(day).size() << endl ;
if (AfficheSol)
for (terriers soluce: CardMin.at(day)) {
cout << « < » ;
for (uint i = 0 ; i < soluce.histoire.size() ; ++i) {
cout << soluce.histoire.at(i) ;
if (i <soluce.histoire.size() -1) cout << « , » ;
}
cout << « > » ;
}
cout << endl ;
return 0 ;
}
/// Permet d’effectuer une observation de terrier (le bit associé est mis à 0)
/// holes : configuration des terriers avant les observations
/// l_holes : configuration (locale) des terriers avec les observations
/// new_holes : configuration des terriers avec les observations et les déplace-
/// ments du renard destinée à être stocker si sa cardinalité est minimale.
/// TerriersOccMin : nombre minimal de terriers occupés par le renard (cardinal
/// des bits à 1). Initialisé au nombre de terriers.
void AjouterObservation(const terriers &holes, uint h, uint obs,
const uint nbr_obs, const uint d)
{
static uint TerriersOccMin = terriers::size ;
terriers l_holes ;
/// avec une observation on scrute les différents terriers
for (uint num_ter = h ; num_ter < terriers::size ; ++num_ter) {
/// Mise à 0 du bit correspondant au terrier observé
l_holes.PresenceRenard = holes.PresenceRenard & ~(1<< num_ter) ;
l_holes.histoire = holes.histoire ;
/// comme on vient d’appliquer une observation on la rend historique
l_holes.histoire.push_back(num_ter+1) ;
/// s’il ne s’agit pas de la dernière observation on recommence à partir des
/// terriers qui restent (num_ter+1) et l’observation suivante (obs +1)
if (obs < nbr_obs) {
AjouterObservation(l_holes, num_ter+1, obs+1, nbr_obs, d) ;
}
else { /// ici toutes les observations ont généré une nouvelle configuration
terriers new_holes = DeplaceRenard(l_holes) ; /// alors on déplace le renard
/// on compte le nombre de terriers occupables
uint NbreTerriersOccupes = PossiblementOccupes(new_holes) ;
if (NbreTerriersOccupes < TerriersOccMin) { /// si cardinalité plus faible
CardMin.at(d+1).clear() ; /// on efface le stockage déjà effectué
TerriersOccMin = NbreTerriersOccupes ; /// on update la cardinalité min.
}
/// si la cardinalité des terriers occupables est = celles stockées
if (NbreTerriersOccupes == TerriersOccMin)
CardMin.at(d+1).push_back(new_holes); /// on rajoute la config. en cours
}
}
return ;
}
/// Retourne le nombre de terriers possiblement occupés (Cardinalité des 1)
uint PossiblementOccupes(const terriers &t)
{
uint occupes = 0 ;
for (uint nb_ter = 0; nb_ter < terriers::size ; ++nb_ter)
if ((t.PresenceRenard & (1U<<nb_ter)) != 0)
occupes++ ;
return occupes ;
}
/// Déplace le renard selon les mvts autorisés et à partir des terriers occupés
/// holes : configuration des terriers après toutes les observations et avant
/// application de tous les déplacements autorisés du renard.
/// new_holes : configuration des terriers après application de tous les dépla-
/// cements autorisés du renard. Retourné à la fonction appelante.
terriers DeplaceRenard(const terriers &holes)
{
terriers new_holes { 0x00000000U } ; /// aucun terrier n’est possiblement occupé
/// passage en revue de tous les terriers après observation(s)
for (uint num_ter = 0 ; num_ter < terriers::size ; ++num_ter) {
/// présence possible d’un renard (bit associé au terrier différent de 0)
if ((holes.PresenceRenard & (1U<<num_ter)) != 0) { /// passage en revue de tous les déplacements du renard for (int d : terriers::MvtRenard) { /// dans le respect des limites (terrier cible entre 0 et size-1) int cible = int(num_ter) + d ; if ((cible >= 0) and (uint(cible) < terriers::size)) {
/// mise à 1 du bit correspondant au terrier cible
new_holes.PresenceRenard = new_holes.PresenceRenard | (1U << cible) ;
} } } }
new_holes.histoire = holes.histoire ; /// copie de l’histoire des observations
return new_holes ;
}
Retrouvez les autres défis et l'application
L’application
1e défi
2e défi
3e défi
4e défi
5e défi
6e 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
