On vous l'a dit : chaque baguette a son sorcier et chaque sorcier a sa baguette. Cette année Olivander a décidé de se moderniser. Afin de ne pas se tromper dans les affectations des baguettes, il fait tester chaque baguette à chaque élève (et inversement par la même occasion). Il est capable, en regardant les réactions des élèves et des baguettes, de fournir une liste de préférences.
Il a donc commencé par dresser la liste des élèves. Par exemple :
1. Hannah Abbot
2. Susan Bones
3. Ernie Macmillan
Puis, il a dressé la liste des baguettes :
1. Acacia et Ventricule de dragon
2. Chêne et Crin de licorne
3. Aulne et Moustache de troll
Pour chaque élève, il peut classer toutes les baguettes par ordre de préférence décroissant. Par exemple :
1 : 2, 1, 3
2 : 3, 1, 2
3 : 2, 3, 1
Ce qui signifie que Hannah Habbot (élève 1), a pour ordre de préférence les baguettes 2, 1, et 3 (elle préfère la baguette en Chêne, son deuxième choix est celle en Acacia, et son dernier choix, celle en Aulne).
De même, pour chaque baguette, il peut classer les élèves par ordre de préférence décroissant :
1 : 1, 2, 3
2 : 2, 1, 3
3 : 2, 3, 1
Ce qui signifie que la baguette en Acacia et Ventricule de dragon (baguette 1) préfèrerait être associée à Hannah Abbot (1). Son deuxième choix serait Susan Bones (2) et son dernier choix Ernie Macmillan (3).
Une fois ce travail fait, il veut associer élèves et baguettes, qui sont en même nombre. Clairement, tout le monde ne pourra pas avoir son premier choix. Ce n'est pas très grave. Par contre, il faut absolument éviter la situation suivante : le sorcier A préfère la baguette du sorcier B à la sienne, et la baguette du sorcier B préfère le sorcier A à son propriétaire. Dans ce cas, le sorcier A et la baguette du sorcier B emploieront toute leur énergie à être enfin réunis, quitte à rompre l'équilibre magique.
Dans l'exemple qui précède, par exemple, on ne peut pas faire l'association suivante (le premier numéro est celui du sorcier et le second celui de la baguette) :
(1, 3), (2, 1), (3, 2)
En effet, les associations (1, 3), (2, 1) ne sont pas stables, car la baguette 3 préfère le sorcier 2 à son propre sorcier (le 1), et le sorcier 2 préfère la baguette 3 à la baguette 1 qui lui a été affectée.
Par contre l'association suivante conviendrait :
(1, 2), (2, 3), (3, 1)
Olivander vous a fourni ses listes de préférences (entrée du problème). Il y a beaucoup de sorciers et beaucoup de baguettes...
Trouvez un appariement qui satisfait aux critères et proposez une réponse au défi
dans le format suivant (1, 2), (2, 3), (3, 1), ...
(pour chaque couple, le premier numéro est celui du sorcier, le second celui de sa baguette).
