« Mon cher Poirot, je ne vois pas où vous voulez en venir avec cette grille.
— Voyons Hastings, c'est pourtant simple. Pour prouver la culpabilité de notre suspect, il est nécessaire de reconstituer ses déplacements. D'accord ?
— Évidemment.
— Bien. Dans la réalité, c'est extrêmement compliqué à cause de tous les facteurs perturbateurs. Mais si on parvient à modéliser ces déplacements à l'aide de règles simples, cela peut nous aider à nous rapprocher de la vérité. Suffisamment, peut-être, pour que cela constitue la preuve que l'on cherche.
— Dans une grille de 10x10 cases ?
— C'est un modèle, donc il est forcément simplifié. Mais il peut nous aider, oui. Je vous explique une nouvelle fois.»
Le célèbre détective belge dessine alors une grille 5x5 garnie de nombres entiers positifs ou négatifs, puis reprend les règles. Le coin supérieur gauche (A1) contient un 0, ainsi que le coin inférieur droit (E5). Un pion est posé sur la case A1, et l'objectif est d'atteindre la case E5. Le pion a une caractéristique appelée altitude. Initialement, l'altitude du pion est 0. À chaque coup, le pion peut être déplacé d'une ou deux cases :
- vers la droite ou vers le bas si son altitude est paire
- vers la gauche ou vers le haut si son altitude est impaire
Par ailleurs, on fera en sorte de ne jamais visiter deux fois une case lors d'un trajet.
À chaque fois que le pion arrive sur une nouvelle case, son altitude est mise à jour en lui ajoutant la valeur de la case sur laquelle il a atterri.
Voici un exemple de partie sur cette grille :
A B C D E
+--------------
1 | 0 1 2 1 -2
2 | 2 1 1 -1 -2
3 | 1 1 -1 2 1
4 | 1 -1 -2 1 -2
5 | 2 2 -2 -1 0
Le pion est initialement en A1, à l'altitude 0.
L'altitude est paire, donc le pion peut aller en B1, C1, A2 ou A3.
Supposons qu'on joue en C1. L'altitude vaut maintenant 2 (0 + 2). Elle est paire, on peut aller en D1, E1, C2 ou C3.
Supposons qu'on joue en E1. L'altitude vaut maintenant 0 (2 + (-2)). Elle est paire, donc on peut aller en E2 ou E3.
Supposons qu'on aille en E2. L'altitude vaut maintenant -2. On peut jouer en E3 ou E4.
Supposons qu'on aille en E4. L'altitude vaut maintenant -4. On peut jouer en E5 uniquement.
On arrive en E5 pour terminer le parcours :
Un autre parcours serait le suivant :
On va en C1, E1, et E3:
L'altitude vaut alors 1. On va en C3, D3 et D5 :
Et on termine par D4, E4 et enfin E5 :
Pour chaque parcours, on peut mesurer son score en donnant deux valeurs : la différence (positive) entre l'altitude minimale et l'altitude maximale le long du parcours (pas forcément au début et à la fin, le long de tout le parcours), et la longueur du trajet.
Dans l'exemple 1, le score est (6, 6), puisque l'altitude minimale est -4 et l'altitude maximale est 2, et que 6 cases en tout ont été occupées.
Dans l'exemple 2, le score est (2, 10).
L'objectif est de trouver un trajet de score minimum. À noter qu'on utilise la comparaison lexicographique (a,b) < (c,d) si a < c ou bien si a = c et b < d. On a donc (4, 7) < (4, 10), mais (4, 7) > (2, 10).
Dans la grille qui précède, l'exemple 2 est justement le trajet de score minimal.
On peut le décrire ainsi : A1, C1, E1, E3, C3, D3, D5, D4, E4, E5.
Une fois ces explications terminées, Hastings reprend la parole :
« Vraiment, Poirot, je ne vous suis pas. Quelles sont ces histoires d'altitude et d'amplitude dont vous me parlez, et quel rapport avec notre sujet ?
— Ne cherchez pas à comprendre le modèle, car ce n'est que cela, un modèle. L'altitude pourrait représenter la distance entre des lieux qui seraient représentés par chaque case ? L'amplitude serait le niveau de fatigue ou de détresse psychologique de l'accusé ? Accordez moi votre confiance sur ce point : ce modèle devrait fonctionner dans notre affaire. Maintenant que j'ai posé les règles, je vous laisse résoudre ce petit problème. Avec votre rigueur habituelle, je suis confiant dans les résultats ! »
Mettez-vous à la place d'Hastings en résolvant ce défi. Il faut donner un trajet de score minimal sur une grille plus grande. Le trajet doit emmener le pion de la case A1 à la case J10, sur cette grille :
A B C D E F G H I J
-----------------------------
1 | 0 2 -5 -1 4 3 2 -1 3 1
2 | 5 -2 4 -3 -1 -3 -4 5 -1 4
3 | 5 -3 -1 -4 -4 1 3 4 -4 1
4 | 2 1 5 -2 4 3 3 4 -1 -5
5 | 4 -5 -4 2 -5 5 3 1 -2 1
6 | -4 -2 5 -2 -2 -3 4 3 -4 -4
7 | 1 4 3 -4 -1 4 -1 -4 4 1
8 | 4 -2 5 4 5 -1 3 -4 5 2
9 | 1 5 -2 -1 -3 -2 -3 -5 5 -1
10 | 3 -4 -4 -3 -3 -5 -4 4 2 0
Validez en donnant un trajet, par exemple :
A1, B1, D1, C1, E1, E3, E4, E6, G6, I6, J6, J8, J10
« Vous savez, Hastings, reprit Poirot, je me demande si on ne pourrait pas simuler des choses plus petites à l'aide de ce genre de modèle. Par exemple, des cellules, leur vie et leur mort. Et alors...
Il eut un instant de silence, le regard dans le vague, puis se reprit :
- Non, oubliez ce que je viens de vous dire, cela n'a aucun sens. Je crois que je vais aller me promener pour ne pas vous ennuyer dans votre tâche. À tantôt ! »
