Toujours plus fort : avec n terriers et encore de nouveaux déplacements du renard
Problème "Fox and Holes" avec n terriers et encore de nouveaux déplacements du renard
.
Un renard, Fox, est dans l’un des n terriers.
Chaque nuit, Fox passe du terrier occupé à l’un des deux terriers parmi celui situé à g terriers vers la gauche et celui situé à d terriers vers la droite. On suppose n ≥ g + d.
Chaque jour, nous pouvons regarder dans l’un des terriers pour voir si Fox y est.
Donner une stratégie pour trouver Fox.
Remarque L’hypothèse n ≥ g + d garantit que de n’importe quel terrier, le renard a toujours au moins un déplacement possible.
.
.
Solution du quatrième défi
Rappel du défi
.
Un renard, Fox, est dans l’un de n terriers alignés (n ≥ 3).
Chaque nuit, Fox 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 l’un des terriers pour voir si Fox y est.
Donner une stratégie pour trouver Fox.
Une stratégie
Notre stratégie se démontre de la même façon que pour le problème « Fox and Holes » avec de nouveaux déplacements du renard (avec 6 terriers), en trois temps.
Dans un premier temps, nous traitons l’éventualité où Fox débute d’un terrier multiple de 3 en commençant par le terrier 3 et nous empêchons Fox de se rapprocher des terriers déjà fouillés tout en progressant sur la file des terriers.
Dans un second temps, si Fox avait commencé dans un terrier précédant un terrier multiple de 3, nous nous ramenons au premier temps.
Et dans un troisième temps, si Fox avait commencé dans un terrier succédant un terrier multiple de 3, nous nous ramenons encore au premier temps. Pour se ramener du deuxième temps au premier, il faut que le nombre de terriers visités auparavant soit un prédécesseur d’un multiple de 3 et si nécessaire, on complète donc par autant d’observations farfelues que nécessaire. Pour se ramener du troisème temps au premier, il faut que le nombre de terriers visités auparavant soit un successeur d’un multiple de 3 et si nécessaire, on complète donc par autant d’observations farfelues que nécessaire.
Si n est impair sans être un multiple de 3, on peut poser \(n = 2k + 1\) avec \(k\) entier naturel.
La stratégie « \(3, 5, 7, …, 2k−1, 3, 5, 7, …, 2k−1, 3, 5, 7, …, 2k−1\) »
permet de trouver Fox.
Si n est impair et multiple de 3, on peut poser \(n = 2k + 1\) avec \(k\) entier naturel.
La stratégie « \(3, 5, 7, …, 2k − 1, x, 3, 5, 7, …, 2k − 1, y, 3, 5, 7, …, 2k − 1\) »
où \(x\) et \(y\) sont des nombres quelconques permet de trouver Fox.
Si n est pair sans être prédécesseur d’un multiple de 3, on peut poser \(n = 2k\) avec \(k\) entier naturel.
La stratégie « \(3, 5, 7, …, 2k−1, 3, 5, 7, …, 2k−1, 3, 5, 7, …, 2k−1\) »
permet de trouver Fox.
Si n est pair et prédécesseur d’un multiple de 3, on peut poser \(n = 2k\) avec \(k\) entier naturel.
La stratégie « \(3, 5, 7, …, 2k−1, x, 3, 5, 7, …, 2k−1, y, 3, 5, 7, …, 2k−1\) »
où \(x\) et \( y\) sont des nombres quelconques permet de trouver Fox.
Remarque Pour ce problème, nous nous sommes contentés de fournir une seule stratégie valide, mais nous n’avons aucune preuve que cette solution soit la plus courte possible et encore moins pu donner l’ensemble des stratégies de longueur minimale.
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
