Solution au problème de décembre 2009

Le problème:

MP91 Problème de décembre 2009 stamp-search.com   Après que Blanche-Neige eût épousé son prince pour filer un bonheur parfait, la mine a fermé et les sept nains ont pris leur retraite. Ils vivent maintenant aux quatres coins du pays et communiquent par courriel. Ils se retrouvent toujours à Noël pour un échange de présents, mais maintenant ils ont du mal à établir la liste pour l'échange: Dans le bon vieux temps ils se réunissaient au début de décembre, et Blanche-Neige et chaque nain pigeait dans un sac le nom de la personne à qui offrir un présent. Mais cette année, ils ne se verront pas avant Noël, et alors il sera trop tard. Ils pourraient bien sûr demander à l'un d'entre eux d'établir la liste, et d'envoyer à tout le monde le nom de la personne à qui offrir un présent. Mais cette solution a deux inconvénients: La personne qui établirait la liste saurait qui lui offre un présent, et les autres ne pourraient jamais être certains que la liste est bien le résultat du hasard, sans tricherie. En effet plusieurs rechignent à recevoir un présent de Simplet, en donner un à Grincheux ou devoir embrasser Atchoum. Ce mois-ci, votre tâche est de créer la version ``courriel'' de la pige de noms dans un sac pour faire une liste d'échange de présent. Spécifiquement, trouvez une procédure qui N'utilise que des courriels entre Blanche-Neige et les sept nains, sans aide d'autres personnes ou de logiciels (Les courriels peuvent avoir un destinataire unique ou de multiples destinataires.) Donne à chacun le nom de la personne à qui offrir un présent, sans révéler à personne le nom de la personne qui lui offre un présent. Donne un résultat aléatoire, ou personne ne peut décider qui offre un présent à qui. Votre méthode va peut-être même améliorer la méthode traditionnelle: Lorsqu'une personne pige son propre nom dans le sac, alors on doit remettre tous les noms dans le sac, et repartir à zéro. Essayez de trouver une méthode qui fonctionne à tout coup, sans donner à personne son propre nom. Merci à Matthieu Dufour, qui nous a communiqué ce problème après s'être lui-même retrouvé dans la position des sept nains. Nous avons reçu des solutions correctes de Bojan Basic (Serbie) Magnus Jakobsson (Suède) John Campbell (Alberta) Philippe Fondanaiche (France) John T. Robinson (États Unis) Tom Fuzzesy (Regina) Math 20 IB class, Archbishop MacDonald High School (Alberta)

La solution:

Nos correspondants ont trouvé plusieurs méthodes intéressantes pour résoudre le problème. Nous examinerons d'abord la solution de John Campbell, puis quelques suggestions d'autres correspondants, pour terminer avec la solution de Magnus Jakobsson.

Solution de Campbell: Soit D(1) à D(7), les sept nains, et D(8), Blanche Neige. Lors d'un échange traditionnel, chaque participant pige en secret le nom d'un autre participant à qui ils offriront un présent. Pour la version courriel, chacun pigera en public le code secret du participant qui lui offrira un présent.

Première étape: Une colonne de code secrets est créée. D(1) amorce la colonne en écrivant un nombre aléatoire dans un courriel qu'il envoie à D(2). Puis chaque participant D(i), i = 2, ..., 7, va permuter la colonne reçue de D(i-1), ajouter son propre (nouveau) nombre aléatoire sur une nouvelle ligne quelque part dans la colonne, et envoyer la colonne à D(i+1). Blanche Neige (D(8)) va faire de même et renvoyer la liste à D(1).

Deuxième étape: Une liste de donneurs est créée. D(1) inscrit son nom à côté d'un nombre aléatoire autre que le sien. Puis il change son propre nombre aléatoire et envoie la liste à D(2). Puis chaque participant D(i), i = 2, ..., 7, va faire de même et passer la liste à D(i+1). Lorsque Blanche Neige reçoit la liste, elle inscrit son nom à côté du dernier nombre aléatoire si ce n'est pas le sien, et renvoie la liste à D(1). Si le dernier nombre aléatoire est le sien, elle écrit à tout le monde pour dire que le processus a échoué et qu'il faut recommencer.

Troisième étape: La liste est diffusée. Chaque participant D(i), i = 1, ..., 7, note le nom à côté de son nombre aléatoire, puis change son nombre aléatoire et envoie la liste à D(i+1). Lorsque Blanche Neige reçoit la liste, tous les participants savent à qui offrir un présent. En fait, certains (dont Blanche Neige) le savent dès la deuxième étape. La troisième étape permet de s'assurer que tout les participants ont cette information. Et puisque chaque participant reçoit une nouvelle série de nombres aléatoires chaque fois qu'il revoit la liste, il n'a aucune information au sujet des autres donneurs.

Il y a une chance sur huit que Blanche Neige doive tout faire recommencer à la fin de la deuxième étape. Pour éviter ce contretemps, Basic et les élèves de Archbishop MacDonald High School suggèrent de profiter du fait que 8 est pair: A la fin de la première étape, Blanche Neige inscrit ``Groupe A'' à côté de quatre des nombres aléatoires, et ``Groupe B'' à côté de quatre autres. Durant la deuxième étape, les participants du Groupe A inscriront leur nom à côté d'un nombre du Groupe B, et vice versa.

Solution de Jakobsson:
Première étape: Une liste de donneurs secrets est créée. Blanche Neige amorce le processus en écrivant à un nain choisi au hasard ``Veux-tu être le donneur 1?''. (En bons amis, ils se tutoient.) Puis pour i = 1, ..., 8, lorsqu'un nain ou Blanche Neige reçoit l'invitation ``Veux-tu être le donneur i?'', il/elle peut la rejetter et la transférer à un autre participant, ou l'accepter et envoyer l'invitation ``Veux-tu être le donneur i+1?'' à un autre participant. Chaque participant doit accepter d'être donneur une seule fois. La première étape se termine lorsque quelqu'un accepte d' être le donneur 8.

Deuxième étape: Une liste de receveurs secrets est créée. Le donneur 8 envoie le message ``Veux-tu être le receveur 1?'' a un autre participant choisi au hasard. Puis pour i = 1, ..., 8, lorsqu'un nain ou Blanche Neige reçoit l'invitation ``Veux-tu être le receveur i?'', il/elle peut la rejetter et la transférer à un autre participant, ou l'accepter et envoyer l'invitation ``Veux-tu être le receveur i+1?'' à un autre participant. Chaque participant doit accepter d'être receveur une seule fois, et le donneur i ne peut accepter d'être le receveur i. Pour éviter que le donneur 8 ne se retrouve dans une impasse, il y a un règlement spécial: Avant d'accepter d'être le receveur 7, un participant doit s'assurer que tous les autres participants ont vu cette invitation, soit parce qu'ils lui ont transmise ou parce qu'il/elle leur a transmise. La deuxième étape se termine lorsque quelqu'un accepte d'être le receveur 8. Il écrit alors à tous ``Je suis le receveur 8'', et à ce signal, les autres participants envoient aussi un message indiquant leur numéro de receveur aux autres. Ainsi, tous les participants savent à qui offrir un présent.