David Madore's WebLog: Comment répartir aléatoirement des cadeaux à Noël

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

↓Entry #2485 [older| permalink|newer] / ↓Entrée #2485 [précédente| permalien|suivante] ↓

(dimanche)

Comment répartir aléatoirement des cadeaux à Noël

(Allez, hop, je suis en forme : une troisième entrée pour aujourd'hui.)

Je suppose que je ne suis pas le seul, en cette saison, à me retrouver occasionnellement dans un groupe d'amis où on a décidé de faire une répartition aléatoire de petits cadeaux (c'est-à-dire que chacun apporte un cadeau d'une valeur approximative fixée, et l'idée est que chacun repart avec le cadeau d'un autre). Une façon de faire la répartition consiste à mettre les noms de tous les participants dans un chapeau, puis chacun tire un nom et donne son cadeau à la personne dont il a tiré le nom : le problème est qu'il y a un risque de tirer son propre nom — il faut alors retirer, mais si c'est la dernière personne qui tire son propre nom, ce n'est pas aussi évident à corriger. Bon, ce n'est pas très difficile, il y a des algorithmes efficaces pour tirer au hasard un dérangement (= une permutation sans point fixe), on peut même se permettre de refaire tout le tirage depuis le début dès qu'une personne tire son propre nom, ça finira par marcher en environ e≈2.7 tirages en moyenne. Mais je propose quand même une autre façon de faire la répartition qui ne nécessite pas de chapeau, qui est au moins aussi simple et efficace dans la pratique, et peut-être plus rigolote. Je ne sais plus qui l'a trouvée (ce n'est pas moi, c'était à une soirée entre amis, et maintenant elle est adoptée à chaque fois). La voici :

Chacun choisit un nombre aléatoire (pour simplifier les comparaisons, on pourrait dire que chacun choisit un nombre entiers à quatre chiffres, c'est-à-dire entre 0 et 9999). Puis la règle est simple : on trie tous ces nombres (par ordre croissant), et chacun donne son cadeau à celui qui a choisit le nombre venant immédiatement après, sauf le plus grand nombre qui donne son cadeau au plus petit.

Dans la pratique, ça va très vite (chacun écrit son nombre sur un papier, puis on demande qui a choisi un nombre entre tant et tant, par exemple entre 0 et 999, et on diminue l'intervalle tant qu'il y a plusieurs personnes, ce qui donne un tri raisonnablement efficace). Il est bien sûr possible que plusieurs personnes choisissent le même nombre, dans ce cas on peut les trier, par exemple, par ordre d'âge (ou leur faire choisir des chiffres supplémentaires pour départager).

La construction produit un n-cycle, où n est le nombre de participants, aléatoire uniforme (au moins si toutes les personnes sauf au plus une choisissent honnêtement un nombre aléatoire indépendamment les unes des autres ; enfin, peu importe, ce n'est pas le genre de truc où on a envie de tricher). Ce n'est pas pareil qu'un dérangement aléatoire, c'est plus particulier, mais un n-cycle me semble finalement plus convivial, parce que tout le monde se retrouve intégré à la même chaîne de cadeaux où chacun donne au suivant.

Ajout () : Suite à des remarques dans les commentaires, je précise la manière dont on peut modifier ce protocole pour des contraintes un peu différentes. Premièrement, le cas (Secret Santa) où on veut que chacun ignore qui lui fait le cadeau qu'il reçoit (personnellement, je trouve ça plutôt moins drôle dans un groupe d'amis, parce que c'est sympa de pouvoir parler de comment on a trouvé tel ou tel cadeau rigolo, mais bon, peu importe) : chacun apporte un cadeau avec un numéro aléatoire attaché et le place (sans être vu) sous le sapin de Noël ; puis les numéros de tous les cadeaux sont recopiés sur un papier et triés publiquement, et chacun prend le cadeau dont le numéro (qui est toujours étiqueté dessus) est immédiatement avant celui qu'il avait choisi. (On peut même s'arranger ainsi pour que chacun ignore à qui son cadeau va.) • Deuxièmement, le cas où, au lieu de faire des cadeaux pouvant convenir à tout le monde et les répartir aléatoirement, on veut que chacun se voie attribué un destinataire à l'avance et fasse un cadeau spécialement pour lui (personnellement, là aussi, je trouve ça plutôt moins drôle) : dans ce cas, dans une réunion préparatoire, chacun apporte une enveloppe avec son nom à l'intérieur et un numéro aléatoire à l'extérieur et la place (sans être vu) sur une table ; puis les numéros de toutes les envelooppes sont recopiés sur un papier et triés publiquement, et chacun prend l'enveloppe dont le numéro (qui est à l'extérieur) est immédiatement après celui qu'il avait choisi, prépare un cadeau pour la personne dont le nom est à l'intérieur, et le jour de la distribution, étiquette son cadeau pour cette personne (et le place en secret sous le sapin).

En revanche, je n'ai pas trouvé de solution vraiment simple et satisfaisante au cas où on veut empêcher que deux personnes en couple se donnent leur cadeau l'un à l'autre. Une possibilité est de dire que les couples choisissent leurs nombres ensemble et qu'ils doivent être distants de 5000 (par exemple 1729 et 6729) si on s'est placé dans le cas de figure où tout le monde choisit un nombre entre 0 et 9999 : du coup, s'il y a au moins deux couples dans le groupe, personne ne donnera de cadeau à son significant other.

↑Entry #2485 [older| permalink|newer] / ↑Entrée #2485 [précédente| permalien|suivante] ↑

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées