Énigme
Sauve qui peut !
Un prisonnier (en haut à gauche) veut s’échapper. Pour atteindre la sortie, il doit assommer tous ses codétenus, sans repasser par une cellule dans laquelle il y a un prisonnier inanimé afin de ne pas le réveiller. Comment peut-il faire ?
Méthode de résolution
Cette réponse a été proposée par Philippe Vallin, partenaire d’EURODECISION, que nous remercions chaleureusement.
« De l’impossibilité de trouver un chemin passant une fois par toutes les cases dans un carré pair »
Hypothèse : on passe une fois et une seule dans chaque case d’un carré n x n.
Appelons « pas » le passage d’une case à une autre.
Soit d, g , b, h le nombre de pas à droite, à gauche, en bas , en haut du chemin.
Puisqu’on passe dans chaque case avec un départ et une fin on a :
(1) : d+g+b+h = n²-1 (le fameux comptage des intervalles)
Si on se déplace du NO au SE donc de gauche à droite et de bas en haut on doit avoir :
- (2) : d-g= n-1, il faut s’être déplacé de n-1 cases à droite quelles que soit les circonvolutions
- (3) : b-h = n-1, il faut bien descendre !
En faisant (1)+(2)+(3) = 2(d+b) = n²+2n-3=(n+1)²-4 soit S =d+b= (n+1)²/2 -2.
Quel que soit le chemin S est constant, ce qui n’est pas évident a priori, tout pas à droite économise un pas en bas.
Mais il doit aussi être entier ! Or si n est pair, il ne l’est pas puisque n+1 et (n+1)² sont impairs. D’où l’impossibilité.
Pour notre problème la solution consiste à passer 2 fois dans une case, la seule possible est celle de départ en visitant une case adjacente au début et revenir.
Remarque : en revanche il tout à fait possible de passer du NE au SE, S=n(n+1)/2-1 est toujours entier.
Solution triviale pour n pair et simple pour n impair.