Actually the fix posted below doesn't work. It will produce only one odd cycle, so that, for instance, in a six person problem it will never generate two three cycles. Oh well, this must be a good problem, it is "fighting back". Regards Otto On Monday 12 January 2004 13:32, Otto Smith wrote:
I think Michael Kleber's algorithm can be fixed albeit with a slight increase in complexity.
Envelopes are prepared as before. There is a red hart and a blue hat as well as the initial hat from which we draw. We draw two envelopes as before and swap the contents, this time we randomly place one envelope in the red hat and one in the blue hat.
If at the last draw, there is only one envelope. we draw a second envelope from the blue hat to match it, swap the contents and place one envelope in the blue and one envelope in the red hat.
The blue hat is then dumped out. All the cards are removed from their envelopes, shuffled and put back in any order. The red and blue hats are combined and the envelopes passed out. I believe this procedure can generate any poosible secret santa configuration.
For the case of an even number, we can see that the set of names has been partitioned into two equal size sets.
The red hat contains only one set as the lables on the envelopes, and the blue hat contains the same set as the contents of the envelopes. Consequently we can safely shuffle the contents in either hat and the criteria that every person is contained in one envelope and has their name on one envelope is met. For the case of an odd number, we must shuffle only the blue hat because it is possible that shuffling the red hat could cause a person to be their own secret santa. In addition, of course, it guarantees an odd cycle in the geometry of the result.
There are probably ways to simplify this algorithm and make it more natural in terms of practicality.
Regards Otto otto@olympus.net
On Sunday 11 January 2004 17:27, Michael Kleber wrote:
Aw, nuts...
Funster-mostly-lurker Thomas Colthurst and I spent a little time this afternoon thinking about how good my secret santa algorithm is. (Recall, it's iterating "remove two envelopes from the hat, swap the names inside, then put one of them back in the hat.") After some amount of mental fumbling, we realized the sad truth: turns out that it generates only n-cycles. :-( Once you realize it's true, the proof's not hard, so I'll leave it as an exercise.
Sigh...
Anyway, in light of Fred Helenius's observation (that choosing among derangements uniformly is essentially hard for prime factorization reasons), it seems that the next obvious thing to hope for is that, even once you know who you're giving gifts to, the person giving gifts to you should be equally likely to be anyone in the group. It's pretty clear that, if you do a decent job randomizing, there should only be two probabilities to think about: that your gift-giver is (a) the person you're giving gifts to, or (b) someone else. And of course if (a) happens 1/(n-1) of the time, you meet this criterion.
Anyway, my algorithm does (a) with probability zero, so unless you're of the camp that says n-cycles are a good thing, a better routine is required.
From this point of view, by the way, the "two hats" algorithm (for n even) is also flawed: the person you're giving gifts to was definitely in the opposite hat from you, making them (epsilon more than) twice as likely as anyone else to be your santa.
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun