Tunnels magiques

Quatre castors aiment jouer avec des tunnels magiques. Lorsqu'ils entrent tous ensemble dans un tunnel, ils en ressortent dans un ordre différent.

Si le tunnel est noir, ils ressortent en ordre inverse.

Si le tunnel est blanc, ils ressortent dans le même ordre sauf que le premier et le dernier échangent leurs places.

Les quatre castors traversent successivement les tunnels ci-dessous. Glissez les lettres des castors à droite, dans l'ordre dans lequel ils vont ressortir.

Solution

Si les castors entrent dans l'ordre :

alors ils sortent des 3 tunnels dans l'ordre :

Il y avait plusieurs façons de résoudre le sujet. La manière naïve consiste à appliquer les règles des tunnels les une après les autres, en représentant la position des 4 castors à la sortie de chacun des 3 tunnels.

Il existait une manière plus astucieuse de résoudre le sujet. On part des deux observations suivantes :

1. Le résultat final ne change pas si l'on modifie l'ordre des tunnels.
2. Si les castors passent successivement dans 2 tunnels noirs, leur ordre ne changent pas.

Ainsi, dans le sujet l'effet des deux tunnels noirs s'annule. Le passage à travers les trois tunnels est donc équivalent au passage dans le seul tunnel blanc. L'effet de ce tunnel blanc étant décrit dans le sujet, il suffit d'en recopier l'ordre de sortie des castors.

C'est de l'informatique !

De nombreux algorithmes, en particulier les algorithmes de tri, font intervenir des permutations, c'est-à-dire des opérations changeant l'ordre des éléments. En regardant la manière dont fonctionnent les différentes permutations, on peut souvent optimiser la manière dont on effectue (ou fait effectuer par un programme) les changements d'ordre.

Par exemple, dans ce sujet, on peut observer que la permutation « inverser l'ordre de tous les castors » et la permutation « inverser l'ordre du premier et du dernier castor » sont des permutations que l'on peut effectuer dans l'ordre que l'on veut, sans changer le résultat. De plus, pour chacune de ces deux permutations, si on l'effectue deux fois de suite, alors cela revient à ne rien changer. Du coup, l'ordre final des castors ne dépend que de la parité du nombre de tunnels noirs et de la parité du nombre de tunnels blancs.

Ainsi, un programme qui simule l'effet de plusieurs millions de tunnels n'a pas besoin de réaliser plusieurs millions d'opérations de changement de place : il suffit de regarder s'il y a un nombre impair de tunnels noirs (auquel cas il faut inverser tous les castors) et s'il y a un nombre impair de tunnels blancs (auquel cas il faut inverser le premier et le dernier castor). Un petit peu de réflexion économise des millions de calculs !