View Single Post

Dici's Avatar


Dici
10.10.2012 , 02:16 PM | #1
Pour tous ceux qui ont eu un perso république, je suppose que vous vous souvenez de cette mission de zone qui a dû vous faire perdre un temps monstre. A l'époque, j'avais un peu cogité là-dessus et trouvé une technique de résolution à la main (facilement programmable) systématique et simple. En faisant un reroll, je suis retombé sur cette mission et ça m'a donné enfin de faire un petit interlude "mathématique" pour les rares clampins que ça pourrait intéresser.

La première question que je me suis posé, c'est : pour une situation initiale donnée dont on suppose qu'elle est résoluble, existe-t-il une solution optimale (la plus courte possible) ?

La réponse est oui, pour deux raisons :

- l'opération consistant à changer l'état d'un pylône est une involution (c'est-à-dire qu'en le faisant deux fois on retrouve l'état initial) ; cela est clair si on représente chaque pylône par la la liste non ordonnée des pylônes qui lui sont reliés, et qu'on définit le fait de cliquer sur un pylône par une multiplication par "-1" (un opérateur unaire involutif) de la liste.

- l'ordre des changements ne compte pas ; en effet si vous concaténez deux listes non ordonnées, que vous choisissiez l'une des listes en tête ou l'autre, on obtient toujours la même liste. Il y a donc commutation.

Ainsi toute composition de changement d'état des pylônes peut se ramener à un produit inclus dans L1 o...o L9 où les Li sont les 9 pylônes. Cela signifie que s'il existe une solution, on peut toujours se ramener à une solution en 9 coups maximum... inutile donc de cliquer sans arrêt.


Avec ce résultat intéressant, on aimerait savoir s'il existe toujours une solution. Cette partie est la plus difficile et il faut un peu d'intuition et de tâtonnements pour y arriver. Au final, mon idée a été de composer un "alphabet" de résolution, c'est-à-dire de décomposer le problème en plusieurs problèmes élémentaires (au sens où ils ne peuvent plus être décomposés). Il suffit alors d'aligner les solutions de chacun de ces problèmes.

Cela revient à se demander comment modifier chaque pylône indépendamment des autres. Comme la disposition est symétrique, au lieu de trouver 9 lettres à notre alphabet, il en suffit de 3. Il suffit donc de trouver 3 solutions à autant de problèmes élémentaires, et de se les noter au papier. Le fait que cet alphabet existe implique qu'à partir de n'importe quelle configuration initiale donnée, on peut atteindre n'importe quelle configuration finale donnée. On peut donc avancer une solution en 9 coups au plus dans n'importe quel cas.

En pratique, il faut se dessiner les 3 schémas correspondant aux 3 problèmes élémentaires, on compte alors pour chaque pylône le nombre de modifications qu'on va lui imposer, si c'est pair, on n'y touche pas, sinon on le modifie une fois (conséquence de l'involution). Et voilà... ça n'intéressera personne à part moi je pense mais pas grave !