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

Apokrif (2017-12-21T07:19:15Z)

@Ruxor: "it seems more fun to talk about where we found the (usually quirky) presents we bought"

Dans un premier temps, il serait amusant de deviner qui a fourni le cadeau (voire comment il l'a trouvé) :-)

Serge (2017-12-19T14:19:54Z)

Nos députés pourraient adopter cette méthode lorsqu'ils auront à répartir les emplois d'attaché parlementaire aux enfants de leurs collègues sans pour autant enfreindre la loi pour la confiance dans la vie politique…

Anonymous Couard (2017-12-19T13:31:13Z)

en quoi est-ce différent de la méthode suivante ?
- on écrit les nombres de 1 à n (n=nombre de personnes) sur des papiers
- tout le monde tire un papier
- le numéro k offre à k+1

jonas (2017-12-18T17:45:09Z)

> chacun prend l'enveloppe dont le numéro (qui est à l'extérieur) est immédiatement après celui qu'il avait choisi

Ruxor: yes, that's much better. There's still a slight problem, in that you have to be able to distribute the envelopes in such a way that nobody can get information about what envelope any other participant may have taken. You could eliminiate that information leak if you have the participants enter the room with the envelope one by one, and have them put the envelope back to the stack after examining the contents. But that arrangement makes the procedure inconvenient, and probably slower than the classical method of drawing names and repeating the draws until nobody draws their own name.

Ruxor (2017-12-18T13:11:35Z)

@jonas: Well, then, once again, I think it's more fun if you don't know in advance whom your present will go to, but if you insist on that, I can still modify my protocol: going back to what I previously described, instead of people putting presents under the Christmas tree, some days in advance, they put their name in en envelope with the chosen number on the outside, the protocol is used to distribute the envelopes, then each participant buys a present to the person whose name was inside the envelope they drew, and on Christmas day they label their present accordingly.

This is more or less equivalent to the solution described in the Numberphile video linked in the comment by Mauvaisours. The mathematical morale is that if we want to draw a derangement and we don't really care that every derangement can be chosen, merely that the image of any element is uniformly chosen, then it is simpler to draw an n-cycle than a derangement, because an n-cycle can be drawn by taking the standard n-cycle (1 2 3 … n) and conjugating by a random permutation (the various protocols I described and the Numberphile one all end up doing exactly this).

jonas (2017-12-18T11:48:13Z)

Ruxor: that only works if you would give the same present to anyone. In groups where people know each other well, such as a school class, people will tailor their present to the recepient. Again I'll cite <URL: http://russell2.math.bme.hu/~ambrus/sc/comic/millie/comic?n=20051215 > for that.

Mauvaisours (2017-12-18T11:03:33Z)

Il y a un très bon épisode de numberphile sur les secret santa, avec une solution (que je trouve) très élégante pour réaliser la sélection… <URL: https://www.youtube.com/watch?v=5kC5k5QBqcc >

Ruxor (2017-12-18T10:56:41Z)

@jonas: I haven't done these "secret Santa" in real life, because among a group of friends it seems more fun to talk about where we found the (usually quirky) presents we bought than keep it a secret. Nevertheless, the protocol I described is easily modified for the secret case: let everyone bring a present with a random number attached and put it (without being seen) under the Christmas tree; then the numbers of all presents are all copied on a piece of paper and ordered, and everyone takes the present whose number (still attached to it) is immediately before the one they had chosen.

Denis (2017-12-18T09:53:05Z)

Je m'étais posé cette question à l'occasion d'un précédent Noël, mais avec une contrainte supplémentaire qu'on peut vouloir respecter en vrai: ne pas savoir de qui vient le cadeau, pour plus de mystère. Et aussi ne pas pouvoir essayer d'obtenir un cadeau d'après l'apparence du paquet. Voir ici pour une formulation complète: https://math.stackexchange.com/questions/1069290/christmas-protocol
Je ne crois pas qu'une solution vraiment élégante était sortie.

jonas (2017-12-18T02:07:07Z)

I think you're solving the wrong problem here. Whenever people play this sort of gift-giving game, they usually require that the permutation is secret as much as possible while everyone still knows who they're giving a gift to. This is sometimes called “secret santa”, eg. <URL: http://russell2.math.bme.hu/~ambrus/sc/comic/millie/comic?n=20051208>. I don't understand how you could ensure that with the numbers method you propose.

Johan (2017-12-17T20:55:14Z)

Je crois que le problème des gens qui "tricheraient" se poserait très souvent en dehors des cercles de matheux tous convaincus des vertus et de la beauté de l'aléatoire.

Soit que la répartition aléatoire soit un compromis et que certaines personnes eusssent préféré faire autrement, soit que la méthode de répartition soit comprise comme la règle du jeu sans qu'il soit mal vu de la "hacker".

Outre les paires qui décideraient conjointement de tricher, il y a les gens qui auraient leur nombre fétiche, ceux qui essayeraient de deviner le nombre d'un autre et de se mettre juste avant pour montrer leur attention à celui-ci…

Et que dire du cas où des gens souhaitent donner leur cadeau à une personne en particulier sans qu'on voie que c'était intentionnel… Imaginons un triangle amoureux dans lequel Alice et Bob veulent tous les deux donner leur cadeau à Claire dont ils savent qu'elle choisira probablement le nombre 4242, mais aucun n'ose avouer sa flamme en public. Chacun essaiera de prendre un nombre proche mais pas trop, et celui ou celle qui aura pris le nombre le plus osé pourra offrir son cadeau, tandis que le perdant devra donner son cadeau au gagnant ! Je crois qu'on tient un bon filon de scénarios de films à l'eau de rose…