Renard y es-tu ? 5^e défi

Toujours plus fort : avec n terriers et encore de nouveaux déplacements du renard

Toujours plus fort : avec n terriers et encore de nouveaux déplacements du renard

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.

Retrouvez les autres défis et l'application

L’application
^1e défi
^2e défi
^3e défi
^4e défi
6^e défi
Solution du dernier défi