Pour atteindre la pierre philosophale (merci pour la correction, Lilymage), une des épreuves consiste à traverser la salle des clés. Une multitude de clés volent dans la salle, et une seule permet de passer à l'étape suivante. Afin qu'aucune clé ne parvienne à s'enfuir, Ron propose de les attacher ensemble.
Hermione lance le sortilège Immobilis Clavem, qui immobilise les clés pendant quelques minutes. L'entrée du problème donne leur position dans l'espace (trois coordonnées pour chaque clé). Ça pourrait être par exemple (s'il n'y avait que 6 clés) :
clé 1 clé 2 clé 3 clé 4 clé 5 clé 6
(0, 0, 0), (0, -1, 0), (0, 1, 1), (5, 1, 1), (6, 0, 1), (6, 1, 1)
À partir de là, deux clés peuvent être attachées ensemble avec de la ficelle. Il faut se débrouiller pour que toutes les clés soient liées, c'est-à-dire qu'aucun groupe de clés ne doit être en mesure de quitter la pièce, à moins que toutes les clés ne partent...
Par exemple, si on liait les paires de clés (1, 2), (1, 3), (4, 6) et (5, 6),
toutes les clés seraient certes attachées à une autre, mais elles ne seraient pas toutes
liées ensemble, et le groupe de clés 1, 2, 3 pourrait partir en laissant 4, 5, 6 sur place.
En revanche, si on liait les clés ainsi : (1, 2), (2, 3), (2, 6), (5, 6), (6, 4)
alors aucune ne pourrait s'enfuir. La quantité de ficelle nécessaire dépendrait
de la distance entre les clés 1 et 2 (distance 1), puis les clés 2 et 3 (distance √5 ≈ 2.24), etc.
La longueur de ficelle totale vaudrait environ 11.64.
Mais il est possible d'économiser de la ficelle (c'est de la ficelle magique,
et au prix où les frères Weasley la commercialisent, on est tenté de faire des
économies). En liant les clés ainsi : (1, 2), (1, 3), (3, 4), (4, 6), (5, 6)
alors la quantité de ficelle nécessaire vaudrait environ 9.414.
Les positions des clés dans l'espace sont données en entrée du problème ; la
numérotation des clés correspond à l'ordre dans lequel on donne les coordonnées
(la première est la clé 1). Vous devez fournir les couples de clés à attacher
qui minimisent la quantité de ficelle utilisée.
Votre réponse sera de la forme : (1, 2), (2, 3), ....
L'ordre des couples ainsi que l'ordre des clés dans le couple n'ont pas d'importance.
