For secret santa as a n-cycle random permutation. Generator stage: 1 N folks stands in a circle each has an envelope., they each draw X, a random unique alias from a hat. They make up two cards. One says I give to X, the other says I am X. They put the I am X card in there own envelope and the I give to X card in the envelope of the person on their right. Finding secret stage. 2. The envelopes are put in a hat and each person draws an envelope. They make the I am X alias public and keep the I give to alias. Regards Otto otto@olympus.net On Thursday 08 January 2004 12:54, Michael Kleber wrote:
Marc LeBrun wrote:
That is, a random derangement of the entire set is selected but each participant is only allowed to know their own assignment.
My impression of Secret Santa is that you're supposed to have a random n-cycle, not just a random derangement. With a random derangement, for example, you might end up with a bunch of pairs of people each unknowingly just exchanging gifts with each other, which seems to me undesirable.
Making a random n-cycle out of a random permutation is easy, of course: each person gives gifts to the person who comes after them in the permutation. This is like taking a permutation written in 1-line notation, and putting parens around it to make it into an n-cycle written in cycle structure notation. Each n-cycle can appear in n different ways, of course. (So, obviously, 1/n of all permutations of n things are n-cycles.)
Of course, the interesting question is generating things secretly, modeled on pulling names out of a hat. I stayed my hand moments before sending out email based on the
same idea Gene Salamin proposed:
Divide the problem into two stages. First, secretly assign numbers to people by drawing sealed numbers from a hat. Second, generate a random derangement; this need not be done secretly.
But then you only know the secret number of the person you're giving a gift to, not the name! It's the decoding (secretly) that's tricky.
Here's the best idea I've come up with. It's pretty baroque, and I'm sure there's something better.
--------- 1) Each person gets a secret code name, just as Gene said. Practically, I'd do this by closing your eyes and pointing to a random word on a random page of a dictionary.
2) Each person: a. writes their real name on a piece of paper, b. folds that paper up so the name can't be seen, c. puts it in an envelope, d. writes their secret code name on the outside of the envelope, and e. puts that envelope into a second, larger envelope, in such a way that it is possible to open both flaps to get to the inside piede of paper. (!)
3) These overstuffed envelopes get put in a hat and are drawn out randomly, and put in a stack in that random order.
4) Make this random permutation into a random n-cycle: open both flaps of each doubled envelope, take out the folded paper inside it, and put it into the previous doubled envelope. (The folded paper from the first envelope goes in the last one.)
5) Put all the envelopes back into the hat, mix them up again, and then take them all out and remove the inner paper-in-envelopes from their outer covers.
6) Each person can now safely take the (inner) envelope with their own secret dictionary word written on it, and read the name on the folded paper inside it to see their giftee. ---------
The second, outer set of envelopes is a little bit of overkill. It would suffice to draw the paper-in-one-envelopes out of the hat face down, so that no one got to see the secret code names written on the underside of them. (It's easier to open envelope flaps when they are face down anyway.)
It's not immediately obvious that we need to preserve secrecy during step (4); nothing would be given away then and there if the secret code names were visible. But secrecy would then be compromised in step (6), where people reveal their secret code names.
Improvements welcomed, since this looks pretty bad to me. (But for Marc's motivating n=5, it will certainly work!)
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun