D’ordinaire, nous choisissons un départ, exécutons les mouvements et découvrons le résultat. Ici, la question change : quel départ préparer pour obtenir précisément le résultat souhaité ? Dans ces deux problèmes, les opérations inverses deviennent une manière concrète de raisonner.
Ouvrir le laboratoire : cartes et Josephus, en avant et à rebours
Deux applications à essayer entre amis :
Partir de la fin
Un algorithme à rebours n’est pas une suite d’essais au hasard. Nous partons d’un état final souhaité et annulons les opérations dans l’ordre inverse. Le résultat de la dernière action normale devient le départ de la première action inverse. Il faut savoir quelles informations conserver : ici, nous gardons les cartes sur la table et distinguons ceux qui doivent rester de ceux qui doivent sortir.
Problème 1 : le paquet de cartes
Vous avez 10 cartes numérotées de 1 à 10. Comment les disposer pour que la répétition des mouvements suivants les fasse sortir sur la table dans l’ordre 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ?
- Prendre la carte sous le paquet.
- La poser au-dessus du paquet.
- Prendre la carte sous le paquet.
- La poser découverte sur la table, au-dessus des précédentes.
L’ordre de sortie est chronologique : d’abord 1, puis 2, jusqu’à 10. Dans la pile finale sur la table, en revanche, 10 est au-dessus et 1 au-dessous. Il ne faut pas confondre ces lectures.
La vidéo des cartes à l’envers
Imaginons que nous rembobinons la vidéo. La main est vide et la pile finale est sur la table. Reprenons d’abord le 10, puis le 9, etc. Inversons à la fois le sens des transferts et l’ordre des quatre actions :
- Prendre la carte au-dessus de la pile sur la table.
- La placer sous le paquet en main.
- Prendre la carte au-dessus du paquet en main.
- La placer sous le paquet en main.
Les deux premières actions annulent la sortie sur la table ; les deux dernières annulent le transfert du dessous vers le dessus. Même lorsqu’il n’y a qu’une carte en main, le principe reste identique.
Après chaque groupe de quatre actions inverses, le paquet en main gagne une carte. Lisons toujours du dessus au dessous :
| Carte reprise sur la table | Paquet après le tour inverse, du dessus au dessous |
|---|---|
| 10 | 10 |
| 9 | 9, 10 |
| 8 | 10, 8, 9 |
| 7 | 8, 9, 7, 10 |
| 6 | 9, 7, 10, 6, 8 |
| 5 | 7, 10, 6, 8, 5, 9 |
| 4 | 10, 6, 8, 5, 9, 4, 7 |
| 3 | 6, 8, 5, 9, 4, 7, 3, 10 |
| 2 | 8, 5, 9, 4, 7, 3, 10, 2, 6 |
| 1 | 5, 9, 4, 7, 3, 10, 2, 6, 1, 8 |
Disposition initiale, du dessus au dessous :
5, 9, 4, 7, 3, 10, 2, 6, 1, 8
Même disposition, lue du dessous au dessus :
8, 1, 6, 2, 10, 3, 7, 4, 9, 5
En jouant normalement avec ce paquet, les nombres de 1 à 10 sortent exactement dans cet ordre. Dans le laboratoire, on le vérifie carte par carte ; on peut aussi changer N ou choisir un autre ordre de sortie.
Une comparaison : simulation et permutation
On peut obtenir le même paquet sans annuler directement les mouvements. Étiquetons les positions initiales de 1 à 10, en comptant depuis le dessous. Simulons le jeu normal et notons l’ordre chronologique de sortie de ces étiquettes :
2, 4, 6, 8, 10, 3, 7, 1, 9, 5
À la première position sortie, attribuons la valeur 1 ; à la deuxième, la valeur 2, etc. Le tableau conserve toujours le même sens de lecture :
| Étiquette de la position sortie (depuis le dessous) | Valeur attribuée |
|---|---|
| 2 | 1 |
| 4 | 2 |
| 6 | 3 |
| 8 | 4 |
| 10 | 5 |
| 3 | 6 |
| 7 | 7 |
| 1 | 8 |
| 9 | 9 |
| 5 | 10 |
En classant les étiquettes de 1 à 10, nous retrouvons la disposition du dessous au dessus. Les deux méthodes concordent : la simulation observe la permutation des positions ; la reconstruction inverse annule les transferts.
Problème 2 : le cercle de Josephus
Disposons N personnes en cercle. Comptons jusqu’à K, éliminons la K-ième personne et recommençons avec la suivante. Nous voulons que V personnes du groupe des gagnants restent après P éliminations. Comment construire la disposition de départ ? Nous ne choisissons pas leurs places à l’avance : la reconstruction doit les révéler.
Dans le jeu d’élimination, la place 1 est l’origine du comptage : la personne qui s’y trouve compte 1, la suivante 2, et ainsi de suite jusqu’à K. Après chaque élimination, la personne suivante recommence à 1. Les places de la disposition complète sont numérotées dans le sens horaire ; le jeu suit le sens choisi. Les exemples principaux comptent dans le sens horaire.
La place 1 est le point de départ du comptage pour éliminer. Elle n’est pas nécessairement occupée par la personne portant le numéro 1 et n’est pas nécessairement gagnante.
Le jeu montre la simulation en avant. Le nouveau laboratoire reconstruit la disposition à rebours, puis permet de la vérifier également dans ce jeu.
Ouvrir le jeu de Josephus existant
Reconstruire Josephus, un mouvement à la fois
L’algorithme connaît seulement le nombre de gagnants et de perdants, ainsi que la fréquence d’élimination. Au départ, il rassemble tous les gagnants, les uns à la suite des autres. Il ne tient compte d’aucune position antérieure et n’attribue pas encore les places finales. Pour suivre la méthode, numérotons les personnes : de 1 à V, les gagnants ; de V + 1 à N, les perdants.
- Mettre en file les seuls V gagnants, numérotés 1, 2, …, V. Ils sont réunis : ce ne sont pas encore des places numérotées du jeu.
- Prendre le premier perdant, numéroté V + 1, et le placer en tête de file.
- Répéter K − 1 fois la même paire d’opérations : prendre le dernier nombre en queue et le placer en tête.
- Prendre le perdant suivant et répéter l’insertion et les déplacements. Continuer un perdant à la fois jusqu’à avoir inséré les P perdants.
- À la fin seulement, lire la disposition complète depuis la tête, attribuer les places 1, 2, …, N et repérer celles occupées par les gagnants. Le comptage d’élimination partira de la place 1.
La méthode utilise exactement K − 1 déplacements par insertion, comme la boucle du programme. Par exemple, avec K = 3 : insérer un perdant en tête, puis effectuer deux fois « prendre en queue et placer en tête ». Avec K = 1, on insère seulement le perdant, sans déplacement.
Pendant la reconstruction, les nombres identifient les personnes. Ils n’indiquent pas leurs places gagnantes. Dans le cercle du laboratoire, les gagnants verts sont réunis au départ ; les perdants bleus attendent séparément et sont réinsérés un par un. Les places gagnantes sont un résultat de la méthode, pas une donnée initiale.
Un petit exemple : N = 4, K = 3
Prenons V = 1 gagnant, P = 3 perdants et K = 3. Le gagnant est la personne 1 ; les perdants sont les personnes 2, 3 et 4. Partons de 1 seul. Insérons 2 et effectuons deux déplacements de la queue vers la tête ; faisons ensuite de même avec 3 et 4. Le tableau montre chaque insertion et chaque déplacement terminé :
| Opération | File : numéros des personnes, de la tête à la queue |
|---|---|
| Réunir les seuls gagnants | 1 |
| Insérer le perdant 2 en tête | 2, 1 |
| Déplacer 1 de la queue vers la tête (1 sur 2) | 1, 2 |
| Déplacer 2 de la queue vers la tête (2 sur 2) | 2, 1 |
| Insérer le perdant 3 en tête | 3, 2, 1 |
| Déplacer 1 de la queue vers la tête (1 sur 2) | 1, 3, 2 |
| Déplacer 2 de la queue vers la tête (2 sur 2) | 2, 1, 3 |
| Insérer le perdant 4 en tête | 4, 2, 1, 3 |
| Déplacer 3 de la queue vers la tête (1 sur 2) | 3, 4, 2, 1 |
| Déplacer 1 de la queue vers la tête (2 sur 2) | 1, 3, 4, 2 |
La file complète est 1, 3, 4, 2. Maintenant seulement, attribuons les places : la place 1 contient la personne 1, la place 2 la personne 3, la place 3 la personne 4 et la place 4 la personne 2. La place gagnante est donc 1. Si le comptage part de là et élimine chaque troisième personne, les places 3, 2 et 4 sortent : la place 1 reste.
L’anniversaire : je gagne toujours !
Nous sommes à une fête : 9 invités plus la personne qui fête son anniversaire, donc N = 10. Elle a 12 ans : choisissons K = 12 et un seul gagnant, V = 1. Il y a P = 9 invités à éliminer.
Reconstruisons le cercle et donnons la place gagnante à cette personne. Depuis la place 1, le gagnant horaire est à la place 10 ; en sens antihoraire, à la place 2.
Ce n’est pas de la chance : nous avons choisi le résultat et préparé la bonne position. Pour une autre fête, régler P au nombre d’invités, V = 1 et K à l’âge fêté. La personne dont c’est l’anniversaire s’ajoute aux invités pour former N.
Éliminations dans le sens horaire :
2, 5, 9, 6, 4, 8, 7, 3, 1
Le duo : deux gagnants choisis
Nous sommes 20 amis et voulons laisser deux personnes choisies avant le jeu. Réglons N = 20, V = 2, P = 18 et K = 11.
La reconstruction à rebours trouve les places à donner au duo : dans le sens horaire, 9 et 15 ; dans le sens antihoraire, 7 et 13. Le comptage part toujours de la place 1.
Les deux personnes peuvent échanger leurs deux places gagnantes. Cela ne signifie pas que deux places arbitraires peuvent gagner : seules les positions calculées garantissent ce résultat.
Éliminations dans le sens horaire :
11, 2, 14, 6, 19, 13, 8, 4, 1, 20, 3, 7, 12, 18, 16, 17, 10, 5
Deux groupes de 15 personnes
Un autre exemple emploie deux groupes de 15 personnes : V = 15, P = 15, N = 30 et K = 9. La méthode ne change pas : partons de 15 gagnants et réinsérons 15 perdants. Les places gagnantes sont :
Horaire
1, 2, 3, 4, 10, 11, 13, 14, 15, 17, 20, 21, 25, 28, 29
Antihoraire
1, 3, 4, 7, 11, 12, 15, 17, 18, 19, 21, 22, 28, 29, 30
Reconstruire le cercle de 30 personnes
Autre exemple : 2 gagnants et 28 perdants
Avec V = 2, P = 28 et K = 11, réunissons au départ les seuls gagnants 1 et 2. Les perdants de 3 à 30 sont insérés un par un. Aucune place gagnante n’est fixée à l’avance. À la fin, numérotons les 30 places : en comptant dans le sens horaire depuis la place 1, les places gagnantes sont les suivantes :
18, 28
Essayer 2 gagnants, 28 perdants et éliminer chaque 11-ième
Utiliser le laboratoire
- Dans Cartes, choisir N et l’ordre souhaité. Dans Josephus, indiquer les nombres de gagnants et de perdants, K et le sens, ou charger un exemple.
- Utiliser Suivant et Précédent pour les mouvements individuels, Démarrer/Pause pour l’animation et le curseur pour revenir à une étape précise. La vitesse initiale est d’une seconde par action ; elle est réglable.
- Pendant la reconstruction de Josephus, observer le premier groupe disposé en cercle : il commence avec les seuls gagnants verts. Les perdants bleus restent dans la seconde liste durant le comptage animé, puis entrent un à un sans devenir verts. Le cercle montre le groupe en construction, pas des places déjà attribuées.
- À la fin apparaît la rangée des places, avec les gagnantes en vert. La place 1 est l’origine du comptage du jeu d’élimination. Vérifier en avant reproduit ce jeu pour contrôler la disposition.
Ouvrir le laboratoire : cartes et Josephus, en avant et à rebours
Ce que nous avons appris
Avec les cartes, nous reconstruisons le paquet produisant l’ordre de sortie souhaité. Avec Josephus, nous partons des seuls gagnants réunis et réinsérons les perdants un par un. Nous n’imposons pas les positions gagnantes : nous les découvrons à la fin. Une fois la disposition complète numérotée, la place 1 indique où commencer à compter pour éliminer. La vérification en avant confirme le résultat.