Après quelques essais infructueux pour faire évader tous les sorciers, vous avez peut-être l'impression que la mission est impossible : quels que soient les choix pour faire avancer les sorciers, il y en a toujours qui bloquent la libération des derniers sorciers prisonniers. Mais comment être certain qu'il n'y a jamais moyen, même après des milliards de coups joués, de faire sortir tous les prisonniers ?

Une façon de prouver que le problème posé n'a effectivement aucune solution consiste à mettre en évidence un invariant, c'est-à-dire une propriété de l'état du jeu qui ne peut jamais changer au cours du temps et qui est incompatible avec le but recherché. Pour mieux comprendre l'invariant en question, nous vous proposons ci-dessous une présentation un peu différente, mais néanmoins équivalente, du même jeu.

Dans cette nouvelle présentation, les lignes du tableau n'ont pas toute la même hauteur, et de même les colonnes n'ont pas toutes la même largeur. Une case contenant un sorcier apparaît en couleur, tandis qu'une case vide reste blanche. La règle du jeu reste inchangée.

Cette nouvelle présentation a un premier avantage : elle permet de faire tenir le tableau infini de cases dans un seul carré, dont le côté a une longueur égale à 2. La première ligne du tableau a une hauteur égale à 1, et de même la première colonne a une largeur égale à 1. La case du coin en haut à gauche (une des 3 cases de la prison) est donc un carré de côté 1, qui occupe un quart de la surface du tableau. Puis la deuxième ligne a une hauteur égale à 1/2, la troisième ligne est de hauteur 1/4, et ainsi de suite : la hauteur de chaque ligne vaut la moitié de la hauteur de la ligne précédente. De même les largeurs des colonnes successives sont à chaque fois divisées par 2.

On en déduit que chaque case a une aire double de celle qui est immédiatement en-dessous, et de même chaque case a une aire double de celle immédiatement à droite. Mais alors, chaque fois que l'on fait partir un sorcier d'une case, l'aire totale de la surface colorée ne change pas : la case colorée où était le sorcier au départ est remplacée par deux nouvelles cases colorées, chacune d'aire moitié. Nous venons de mettre en évidence un invariant : l'aire totale des cases colorées.

Au départ, les 3 cases colorées sont un carré de côté 1, et deux rectangles d'aire 1/2, ce qui donne une aire totale colorée égale à 2. Mais puisque cette quantité est un invariant, on en déduit qu'à chaque étape du jeu l'aire totale des cases occupées vaut 2.

Or l'aire totale du tableau vaut 4 : c'est un carré de côté 2. Ce tableau est divisé en deux parties : la zone prison d'aire totale 2, et la zone libre d'aire totale 2 également. Puisqu'il y a un nombre infini de cases en zone libre, à tout moment du jeu il existe des cases de la zone libre non occupées. Donc l'aire colorée en zone libre est toujours strictement inférieure à 2, et donc il reste forcément au moins un sorcier en prison !

Revenir au jeu de l'évasion des sorciers.