The only real problem here is determining a practical way to generate a random derangement without a computer. This requires unique kinds of algorithms that can be carried out as a party game. Clearly a computer could generate a random derangement. This is a directed graph consisting only of directed cycles, Isolated vertices (or self loops) are not allowed, where each person is assigned a vertex and an edge. The secret santa as an n-cycle random permutation is generated by the algorithm I posted as a two step algorithm. First; it randomly generates a set of directed edges from a given set of vertices (the aliases), and second; each person randomly chooses an edge where they are assigned both a vertex and the edge. That is a new secret alias that they make public, and a secret friend that they keep secret. Here is a way to generate a derangement that can include any number of cycles. Again we first generate the edges, and then each person randomly chooses an edge. ALGORITHM: Everyone is publicly given an envelope with unique number and a white card with a matching number. They may secretly place their white card in anyone elses envelope. A person is free to look at the cards in their envelope. If they have more than one card, they must take any cards in excess of one and distribute them secretly to envelopes which have no cards with the restriction that they may not put a card into an envelope with the same number as is on the white card they are placing. When everyone has one white card in their envelope they are randomly given a two colored card with a unique secret name on the blue side. They find the person who has the number of the white card that is in their envelope and ask them to secretly write their secret name on the red side of colored the card. They do not look at the card and place the colored card in a hat. Each person then draws a card from the hat with their new blue public name and their new red secret friend. DISCUSSION: In fact, some of the players in this game may be able to deduce whether short cycles exist, but because of the double blind where names are assigned to numbers without general knowledge of the participants, although they may be able to deduce some of the geometry they will not be able to deduce their secret santa. Regards Otto otto@olympus.net
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun -------------------------------------------------------