|
Un monstre vient de s'introduire dans les douves du donjon de Castor !  Votre objectif est de coincer le monstre pour qu'il ne puisse plus bouger, en utilisant un minimum de barrages. Les cases bleues montrent à chaque fois la zone où se cache le monstre. |
Pour accomplir cette mission, il faut trouver une bonne stratégie. En posant des barrages au hasard, on observe qu'à chaque fois, le monstre se réfugie dans la plus grande des deux parties séparées par le nouveau barrage. Or, si l'on veut poser le moins possible de barrages, on a intérêt à laisser au monstre le plus petit espace possible. Du coup, on a intérêt à couper l'espace restant en deux parties égales.
En répétant cette stratégie, on divise en gros le nombre de cases restantes par deux à chaque étape. Plus précisément, à la première étape, on a 127 cases de douve. En plaçant un bloc au milieu, il reste au monstre un espace de (127-1)/2 = 63 cases. En divisant en deux à nouveau, il lui reste 31 cases, puis 15, puis 7, puis 3 et finalement plus qu'une seule case. Donc, quels que soient les choix du monstre, on peut toujours le coincer avec 6 barrages.
Voici ci-dessous un exemple de « chasse au monstre » en 6 barrages.
La stratégie consistant à diviser exactement en deux l'ensemble des possibilités restantes porte un nom en informatique : la recherche par « dichotomie ».
La dichotomie est un algorithme utilisé dans de nombreux « algorithmes » en informatique, par exemple pour effectuer des recherches dans des ensembles de données triées, ou bien pour calculer sur un ordinateur des valeurs approchées pour les solutions d'une équation mathématique très compliquée.