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

Une seconde extension de l’énigme, avec de nouveaux déplacements du renard

Problème "Fox and Holes" avec de nouveaux déplacements du renard

Solution du deuxième défi

Rappel du défi

Un renard, Fox, est dans l’un de n terriers alignés (n ≥ 2).
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.

Une stratégie

Notre stratégie se démontre de la même façon que pour le problème « Fox and Holes » (à 5 terriers), en deux temps.

Dans un premier temps, nous traitons l’éventualité où Fox débute d’un terrier pair en commençant par le terrier 2 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 impair, nous nous ramenons au premier temps. Pour se ramener du deuxième temps au premier, il faut que le nombre de terriers visités auparavant soit impair, on complète donc par autant d’observations farfelues que nécessaire.

Si \(n\) est impair, on peut poser \(n = 2k + 1\) avec \(k\) entier naturel non nul. La stratégie « \(2, 3, 4, 5, …, 2k − 1, 2k, 2, 3, 4, 5, …, 2k − 1, 2k\) » permet de trouver Fox.

Si \(n\) est pair, on peut poser \( n = 2k\) avec \(k \) entier naturel supérieur ou égal à \(1\).
La stratégie « \(2, 3, 4, 5, …, 2k−2, 2k−1, x, 2, 3, 4, 5, …, 2k−2, 2k−1\) » où \(x\) est un nombre quelconque permet de trouver Fox. L’ajout du « \(x\) » permet de se ramener au premier temps.

Remarque Pour le problème « Fox and Holes » à \(n\) terriers, 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.

Discussion sur notre stratégie

Indépendamment de la parité de \(n\), on peut trouver une autre solution dans le même contexte sur MSE ¹Mathematics Stack Exchange ; Devinette du renard et des trous avec n trous ou sur GTJ ²Gateways to joy ; casse-tête ; Renard dans un trou :
« \(2, 3, 4, 5, …, n−2, n−1, n−1, n−2, …, 5, 4, 3, 2\) ». Cette solution est différente de celle proposée  dans cette section, et est même plus courte dans le cas où \(n\) est pair. La validité de cette solution ne se justifie pas de la même façon : le premier temps des deux stratégies est identique et se justifie d’égale façon, mais si dans notre deuxième temps, nous avions eu pour objectif de nous ramener au premier en chassant à nouveau le renard des terriers pairs, le deuxième temps sur MSE ou sur GTJ chasse le renard des terriers impairs dans le cas où \(n\) est pair (en commençant par \(n − 1\), …) et chasse autrement le renard des terriers pairs dans le cas où \(n\) est impair (en partant de \(n − 1, n − 2, …\) et non en reprenant de \(2, 3,\) …).

On peut aussi trouver une solution dans le cas où \(n = 17\) dans un autre contexte sur PSE ³Puzzling Stack Exchange ; Pourquoi cette solution garantit-elle que le prince frappe à la bonne porte pour retrouver la princesse ? . La démarche est analogue à celle sur MSE ou sur GTJ.

Pourquoi conserver notre solution qui est moins performante que celle trouvée sur MSE ou sur GTJ ? La raison principale est que nous ne nous intéressons qu’à l’existence d’une solution sans forcément nous confronter à l’exigence d’optimalité, c’est-à-dire sans s’efforcer à produire une solution la plus courte possible. Tout comme les solutions sur MSE ou sur GTJ la notre peut être étendue à un cas plus général, et nous préférons le principe de se ramener dans chaque temps au premier à celui de traiter dans chaque temps des éventualités différentes qui deviendront finalement exhaustives.

Retrouvez les autres défis et l'application

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