Une histoire de carré magique



Pour fêter la fin des examens, la direction de l'école de magie Poudlard a organisé le concours suivant :

Grand Concours de Magie

Le but du concours de fin d'année est de fabriquer un objet qui n'existe pas.
L'équipe qui aura réalisé l'objet qui n'existe pas ayant le plus émerveillé le jury remportera un bon gâteau au chocolat.
signé : A. Dumbledore



Le jour du concours, Harry et Hermione se présentent face au jury.
- Nous avons un carré... magique, annonce Harry.
- Vraiment ? interroge Dumbledore.
- En fait, explique Hermione, il s'agit d'un carré de 3x3 cases, chaque case pouvant être soit bleue, soit rouge. Cependant, si je considère une ligne quelconque du carré, je suis assurée qu'elle comporte un nombre impair de cases bleues (propriété L).
- De plus, ajoute Harry, si je considère une colonne quelconque du carré, je suis assuré qu'elle comporte un nombre impair de cases rouges (propriété C).
Les membres du jury échangent des regards perplexes.
- Intéressant, observe Dumbledore.
?
- Voyons, Albus, rugit Rogue. Ils prétendent que chaque ligne contient un nombre impair de cases bleues, et que chaque colonne contient un nombre impair de cases rouges, donc un nombre pair de cases bleues. La propriété d'Hermione (L) m'indique que le carré possède un nombre impair+impair+impair=impair de cases bleues, alors que celle de Harry (C) implique que le carré possède un nombre pair+pair+pair=pair de cases bleues. Ridicule !
- Effectivement notre carré n'existe pas, concède Harry.
- Mais nous en avons un ! s'exclame Hermione.
- Dans ce cas, le jury serait très curieux de le voir, sourit Dumbledore.

Harry prend un air grave.
- En fait, notre carré est top secret, on ne peut pas vous le montrer. Cependant, il existe des opérations qui préservent les propriétés (L) et (C) : par exemple une permutation de lignes, ou de colonnes, ou une rotation de 90 degrés suivie d'une inversion globale des couleurs. Appelons une telle opération une transformation magique (TM). Vous pouvez vérifier que notre carré vérifie (C) sans le connaître dans sa totalité. Pour cela, j'applique au carré initial une TM secrète puis je vous divulgue la colonne de votre choix, ceci autant de fois que vous voulez.
- Et pour vérifier que notre carré vérifie (L), poursuit Hermione, je peux également appliquer diverses TM secrètes au carré initial, et vous révéler après chacune d'entre elle la ligne de votre choix.
- Aha, ricane Rogue. Evidemment c'est trivial pour chacun d'entre vous. Mais ce que le jury veut vérifier, c'est que le carré vérifie simultanément (L) et (C). A savoir que si vous faites chacun de votre côté la même TM, et qu'ensuite on vous demande séparément de divulguer une ligne (Hermione) et une colonne (Harry), vos réponses doivent coïncider au niveau de l'intersection.
- Excellente suggestion, approuve Dumbledore. J'imagine que personne ne voit d'inconvénient à ce petit protocole. Hermione, Harry, accordez-vous sur une suite de TM à effectuer, puis commencera la vérification, durant laquelle notre magie fera en sorte qu'il vous soit strictement impossible de communiquer entre vous, de telle sorte qu'aucun de vous ne connaîtra le contenu des requêtes adressées à l'autre.
- Si on s'en sort, on aura mérité le gâteau, murmure Harry.

Question : Bien comprendre la problématique. Harry et Hermione peuvent-ils s'entendre préalablement sur les réponses successives à fournir de telle manière à ce que les coïncidences soient systématiquement vérifiées ? Comment peuvent-ils triompher de cette épreuve ?

(Merci à A. M. !)

Réponse

Retour aux énigmes

Accueil