## Secret Santa

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

### Secret Santa

I don't know whether this has been done or even if it's a difficult problem, but I gave it some thought when the subject of Secret Santa came up last year and I still don't have a satisfactory solution or proof that it's impossible. Perhaps I'm just not trying hard enough.

Given a set of n > 3 people, devise a method to map to each person one recipient in that set, such that:

• Each person learns who their recipient is.
• Each person is the recipient for exactly one person.
• No person is their own recipient.
• No person gains any more information than the rules above provide regarding possible recipients of other people during the method. ie, each person considers all people except their own recipient and the person in question to be equally likely to be the recipient of each other person after the method has been performed.
• For each n, there is some finite number of operations after which the method must have completed successfully. This excludes the possibility of starting over again indefinitely, as might happen if the last person in a draw can pull their own name from a hat.
You may introduce people outside of the set to assist with the method, but they are subject to the constraints above; that is, they can't gain any non-trivial information regarding possible recipients of any people in the set.

... I hope I didn't miss any obvious constraints. Feel free to post your smarmy answers that fulfil all the criteria without being practical
Chuff wrote:I write most of my letters from the bottom

Goldstein

Posts: 985
Joined: Wed Nov 05, 2008 9:38 pm UTC
Location: Newcastle, UK

### Re: Secret Santa

Here's a simple method that works with a single outsider.
Spoiler:
Have the people in the set agree on a numbering for themselves, which they don't tell the outsider. The outsider generates a derangement of the numbers 1 to n, and for each number, writes that number on an envelope and the number it maps to in the derangement on a slip of paper inside that envelope. The people in the set then take their envelopes (without the outsider seeing) and are assigned the person with the number written inside.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.
Token

Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: Secret Santa

... Oh yeah. Good job.

If anyone's still interested, I suppose there's the variation with no outsiders.
Chuff wrote:I write most of my letters from the bottom

Goldstein

Posts: 985
Joined: Wed Nov 05, 2008 9:38 pm UTC
Location: Newcastle, UK

### Re: Secret Santa

For each of the N! permutations of the list of people:
Spoiler:
- Take a large manila envelope.
- Take N small envelopes.
- For each person
-- Write their name on the outside of one envelope.
-- Write the name of the person after them in the permutation on a card, and seal that card in the small envelope.
-- Put the small envelope in the large manila one.
- Seal the large manila envelope and put it a gigantic sack.

After all that is done:
- draw one large manila envelope from the sack
- open it
- each person takes the envelope with their name and gives a gift to the person whose name is written inside.

For a 10 person group, it will only take 30 million small envelopes and 3 million large ones.
ralphmerridew

Posts: 17
Joined: Wed Jul 11, 2007 3:14 pm UTC

### Re: Secret Santa

ralphmerridew wrote:For each of the N! permutations of the list of people:

This will work, but I’m not convinced you’ve counted the number of possibilities correctly.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

Qaanol wrote:
ralphmerridew wrote:For each of the N! permutations of the list of people:

This will work, but I’m not convinced you’ve counted the number of possibilities correctly.

For exact numbers, it would be 3628800 large envelopes, and 36288000 small envelopes. I think ralph was safe in his rounding considering the impracticality of the whole thing anyway.
Goals:
1. Disprove something widely accepted to be true (In progress... I'm getting there.)
2. Have an action figure made of myself (With karate chop action!)
3. Win a dancing contest (COMPLETE)
Xias

Posts: 194
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California

### Re: Secret Santa

I know that 3 million wasn't exact; I was just making the point that I realize

Spoiler:
- Take N small envelopes, numbered from 1 to N on the outside.
- Each person
-- receives one envelope at random.
-- writes his/her name in it and seals it.
-- remembers the number.
-- and puts it in a bag.
- Then, the bag is left out.
- The person who had envelope N takes envelope 1; anyone who had envelope k<N takes the envelope numbered k+1.
- They do at sporadic times, so that people don't know who has already taken his/her envelope.
- Give gift to the person whose name is in your envelope.
ralphmerridew

Posts: 17
Joined: Wed Jul 11, 2007 3:14 pm UTC

### Re: Secret Santa

ralphmerridew wrote:
Spoiler:
- Take N small envelopes, numbered from 1 to N on the outside.
- Each person
-- receives one envelope at random.
-- writes his/her name in it and seals it.
-- remembers the number.
-- and puts it in a bag.
- Then, the bag is left out.
- The person who had envelope N takes envelope 1; anyone who had envelope k<N takes the envelope numbered k+1.
- They do at sporadic times, so that people don't know who has already taken his/her envelope.
- Give gift to the person whose name is in your envelope.

I think this leaks some information. If I am person k and get person k+1 as my recipient, then I know that the recipient of person k+1 is not myself.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola
Ended

Posts: 1458
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

### Re: Secret Santa

Xias wrote:
Qaanol wrote:
ralphmerridew wrote:For each of the N! permutations of the list of people:

This will work, but I’m not convinced you’ve counted the number of possibilities correctly.

For exact numbers, it would be 3628800 large envelopes, and 36288000 small envelopes. I think ralph was safe in his rounding considering the impracticality of the whole thing anyway.

You are including permutations for which some people are their own recipients, contrary to the rules. You only need those permutations with no fixed points.

For example, with two people, there is only 1 possibility, so only 1 large envelope is needed. With three people, there are 2 possibilities. With four people, 9. With five people, 44. This is the sequence you want. With ten people, there are 1,334,961 valid permutations, so just over one and a third million large envelopes, thirteen and a third million small envelopes. The number of small envelopes is just N times the number of large envelopes, and is given by this sequence I believe.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

There's always the usual self-double-blinding trick:
Spoiler:
Person 1 generates a random permutation f:{1..n}->{1..n}, and makes two sets of envelopes, in the vein of Token's solution... one for f(n) and one for f-1(n).

Person 2 generates a random derangement g:{1..n}->{1..n}, and also makes a set of envelopes for g(n).

Then each person looks in their own-numbered envelope in the f(n) set, then looks up the number they find in the g(n) set, then looks up that number in the f-1(n) set. The resulting function, f-1.g.f, is a derangement on the original set of people. Neither person 1 nor person 2 has any information about the final mapping.

This is inspired by the usual trick for double-blinding a test with only 2 people... the first person puts the Coke and the Pepsi into two glasses, labels them at random 1 and 2... then the second person removes the 1 and 2 labels and re-labels them at random as A and B. Neither person knows which is which (either is a 50/50 chance) but they can figure it out after the fact.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6779
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Secret Santa

Goldstein wrote:[*]No person gains any more information than the rules above provide regarding possible recipients of other people during the method. ie, each person considers all people except their own recipient and the person in question to be equally likely to be the recipient of each other person after the method has been performed.

So are we not counting the shape of the graph as information, then? If we do, it gets harder: in Token's method, the outsider knows, e.g., how many two-person cycles there are, which turns into person-specific information if the recipients are revealed one by one on Christmas Day.
HonoreDB

Posts: 147
Joined: Tue Feb 06, 2007 4:32 pm UTC

### Re: Secret Santa

phlip wrote:There's always the usual self-double-blinding trick:
Spoiler:
Person 1 generates a random permutation f:{1..n}->{1..n}, and makes two sets of envelopes, in the vein of Token's solution... one for f(n) and one for f-1(n).

Person 2 generates a random derangement g:{1..n}->{1..n}, and also makes a set of envelopes for g(n).

Then each person looks in their own-numbered envelope in the f(n) set, then looks up the number they find in the g(n) set, then looks up that number in the f-1(n) set. The resulting function, f-1.g.f, is a derangement on the original set of people. Neither person 1 nor person 2 has any information about the final mapping.

This is inspired by the usual trick for double-blinding a test with only 2 people... the first person puts the Coke and the Pepsi into two glasses, labels them at random 1 and 2... then the second person removes the 1 and 2 labels and re-labels them at random as A and B. Neither person knows which is which (either is a 50/50 chance) but they can figure it out after the fact.

Awesome, well done!

Although, the person who creates the derangement does have a reasonable idea of the probability that they are in an n-person cycle, meaning in particular the probability that they are in a 2-cycle.

We could make it somewhat more robust by having each person make a derangement, and write it down, then shuffle them up and choose one at random, but there’s still a slight bit of probabilistic information each person has about the shape of the graph.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

That's a point. In the extreme case, if they happen, by chance, to generate a derangement that's entirely 2-cycles, then they know that their assignee is also assigned them.

I'm not sure if there's a way around that... I don't see a way for a bunch of people to collaboratively make a derangement without one person just making a derangement and transforming that... in particular, I can't see how two people could generate an f and a g, and ensure that f.g is a derangement (without severely restricting what derangement it can be). Not to say that such a thing can't exist, but just that I can't see how to do it...
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6779
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Secret Santa

HonoreDB wrote:So are we not counting the shape of the graph as information, then? If we do, it gets harder: in Token's method, the outsider knows, e.g., how many two-person cycles there are, which turns into person-specific information if the recipients are revealed one by one on Christmas Day.

Primarily, I was trying to avoid anyone being sure of anyone else's recipient, of course, but the ideal case is where we can end up with some mapping happening without anyone being even partially aware of what it is. As extreme as it seems, it might be important in practice: Even if the group consists of 3-cycles, you might be able to deduce a lot from the gifts involved.

I like the double-blind approach, Phlip. I was trying to adapt Token's method to remove the outsider, but didn't think to perform the inverse to avoid mapping anyone to themselves.
Chuff wrote:I write most of my letters from the bottom

Goldstein

Posts: 985
Joined: Wed Nov 05, 2008 9:38 pm UTC
Location: Newcastle, UK

### Re: Secret Santa

This took over my brain for way too long. But I now have a physically feasible solution that doesn't require any math.

Spoiler:
Label N envelopes with the numbers 1 through N. Each person randomly and secretly picks a different envelope. Lay all the envelopes out on a table in a room. People enter the room at separate times in random, secret order, and do one of the following:

If your envelope number was 1, and there are multiple unsealed envelopes left, leave without doing anything and come back later.
Else if there are no sealed envelopes, put a slip of paper with your name into envelope 1 and seal it.
Else put your name into a random unsealed envelope that isn't yours and seal it.

Once all the envelopes are sealed, collect your envelope and open it. The name inside is your recipient.

This works because:
Spoiler:
This works because you are never confronted with a situation where the only envelope left unsealed is yours. If your envelope number is not 1, then you're never the last to seal an envelope, so there are always multiple unsealed envelopes left. If your envelope number is 1, then your envelope number is always sealed by the time it's your turn to pick one.
HonoreDB

Posts: 147
Joined: Tue Feb 06, 2007 4:32 pm UTC

### Re: Secret Santa

I don't think that's quite fits the "equally likely" clause...
Spoiler:
Some number-crunching shows that, in the 4-person case, say I'm playing and I get Bob as my recipient. With a fair distribution, I should have a 1 in 3 chance of also being Bob's recipient (easily verified by listing all 12 derangements of 4 people... of the 3 that have me pointing to Bob, there's exactly one of each for each of the three other players pointing to me... so each is equally likely).

However, suppose we're using your strategy, and I happened to go in first, and put my name in envelope #1, and then I end up with Bob. Now, crunch the numbers, draw the probability trees, and you get that it's only a 1/4 chance that Bob has me as a recipient (ie that Bob is number 1) rather than the wanted 1/3. The other two people each have a 3/8 chance of having me as the recipient.

More specifically: assume WLOG I'm person 2, and say person 1 has me as a recipient. Then the three possible derangements are 2143, 2341 and 2413. So I know the person I recieve has a 1/3 chance of being each of 1, 3 or 4, so they have a 1/3 chance of being the same person who has me.
However, again assume WLOG I'm person 2, and we're using your strategy, I happen to go in first, and put my name in envelope #1. Now, there's a 50/50 chance of person 3 or 4 being next (ignoring person 1, who, if they were next would just leave doing nothing). If it's 3, they have a 50/50 chance of putting their name in envelopes 2 or 4... if they pick 2, person 4 will be forced to put their name in envelope 3, 1 will put theirs in envelope 4, we'll have 2341. Alternatively, if 3 puts their name in envelope 4, then person 4 will have a 50/50 choice too, between envelopes 2 and 3, and so it'll be either 2143 or 2413. So the probabilities are P(2341)=1/2, P(2143)=1/4, P(2413)=1/4.
Similarly, if person 4 comes in first, then P(2413) = 1/2, P(2143) = 1/4, P(2341) = 1/4.
Combining these, we get the final probabilities as P(2143) = 1/4, P(2341) = 3/8, P(2431) = 3/8. So I have a 1/4 chance of being in a 2-cycle, unlike the 1/3 chance which is ideal.

I believe this extends upwards for larger sets too... whoever puts their name in envelope #1 has a lower-than-expected chance of being in a 2-cycle.

I haven't analysed the other players yet, but I suspect they're not quite fair either.

 No, they're not... and this one is even clearer than the one I found first... if whoever's second-last (ie last person before person #1 can act) goes in and sees their own envelope is empty, then they know that they'll be assigned #1. They also know that they won't be assigned to #1, because that envelope is already sealed. So they'll know they have a 0% chance of being in a 2-cycle.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6779
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Secret Santa

...damn. Sorry. Really thought I had it.
HonoreDB

Posts: 147
Joined: Tue Feb 06, 2007 4:32 pm UTC

### Re: Secret Santa

Here's one that works well statistically for larger N, with virtually no information leaked... certainly not enough to make any vaguely confident predictions.
Spoiler:
Each person secretly writes an N+5 digit random number on their envelope, and puts it in a hat. One person is then chosen to arrange the envelopes randomly on a table in a single line, left to right. Everyone then comes in and makes a note to themselves of how far along the table their envelope is. Those in the leftmost 1/3 (rounding to the right) always call out "not last", those in the middle 1/3 call out "not last" with probability 0.5, and those in the rightmost 1/3 never call it out - in a practical situation, everyone could secretly pick Heads or Tails and flip a coin to obscure this, those in the ends simply ignore the flip. Then, starting with those who called out "not last" each person in turn selects either the rightmost (r) or second rightmost (r') envelope with probability 1-0.5^(g+1) of selecting r, where g is the size of the gap between r and r', unless of course one of them is yours and then you take the other - in a practical situation, everyone can simply pick a g+1 string of {H|T} and flip a coin g+1 times to obscure this.

Technically, there is a minuscule chance of someone being left with only their envelope on the table, but it is vanishingly small compared to the naive drawing from a hat. Only the last person will not have the choice between two envelopes, and thus not have the opportunity to select one that is not theirs. The odds against this will be roughly proportional to 1 in 2^{(\frac{N}{6})^{2}+\frac{N}{6}}
With an N of merely 9 it should be less than 1/576 that you will end up with your own envelope, as opposed to 1/9 from a normal drawing. I'm not sure exactly how much less, just... less. It's also quite easy to actually do. With N of 10 to 12, it should be less than 1/10,000 that you'll end up with your own envelope.

Actually, we can improve upon this... if everyone is trustworthy...
Spoiler:
Set up the table as before. Each person is assigned a unique number 0 <= K <= N. Each person then inspects the table, and determines if they are in the left half (rounding right). For T > N, at time K each person from the left half secretly goes to the table to make their selection as above, and at time T+K each person from the right half does the same. In this manner, no one can narrow down who is in which half of the group, and the odds of having your own envelope forced upon you are vastly smaller - less than 1/300,000 for a group of 9, and less than 1/23,000,000 for a group of 11.

Come to think of it... if everyone is still trustworthy...
Spoiler:
Set up the table as before. Each person takes a unique number 0 <= K <= N, based on the ordering of the envelopes. The people without the rightmost envelope all secretly go to select an envelope at time K, and the person with the rightmost envelope goes at time T>N, taking the last envelope. This removes the denominator entirely, and the odds of having your envelope forced upon you are now exactly:
\frac{1}{N*2^{\frac{N^2-N}{2}}}
... which drops off towards zero very quickly.

Actually, if we add the condition that if there are only two remaining envelopes then you must select the rightmost envelope unless it is yours, then we can be completely sure that no one will get themselves, and no one should be able to deduce anything!

In fact, that should let us remove any coin flipping all together... and one slight problem I just thought of, though someone with sufficient resources could potentially decipher it.
Spoiler:
For an N person group, each person places their name in an envelope, and writes on it a number, which unfortunately must satisfy a lot more math than previous versions... it's also only cryptographically secure, but can be made arbitrarily strongly so, as no 'decryption' is ever required, so should be sufficient to protect against any possible situation that could arise in the real universe.

An 100 digit prime P modulus is chosen (Yeah, computer assistance required at this point) as well as an 99 digit base B.
Each person is assigned a sequential number K (these can be public), they then select a number Q between K/(N+1)*1099 and (K+1)/(N+1)*1099, and finally calculate BQ mod P which they secretly write on their envelope before secretly placing the envelope in a hat.

This ensures no duplicates, and makes it somewhat difficult to associate numbers with people.

Once all the envelopes are in the hat, they are shuffled and placed on the table. Table order does not matter.

People secretly take envelopes in roughly ascending order of the number on their own envelope, at time 5+T, where T is the number of envelopes with numbers less than the number on their own. Then they randomly reorder all but the leftmost envelope such that theirs is not the rightmost envelope, and take the rightmost envelope. If there are only two remaining, and the rightmost is theirs, they may take the leftmost, and shift the rightmost one spot left. A special cast exists for the person with the leftmost envelope. They stealthily select an envelope at time 3.

As such, if there are M envelopes remaining, an outsider could not distinguish this from the case where there were only M people total.

In this manner, an inductive proof should rather easily show that there will be no double ups, no one has their own envelope, and no one knows who has whose envelope without cracking the encrypting function. Some information may be gleaned about what number was on the outside of the envelope of who it was that got you, or to perhaps to know that the person whose name is in envelope #X got person in envelope #Y, but this information should not be associable with any actual person (again, so long as the cryptographic function holds)

If someone can think of a more straightforward way for everyone in a group to select a unique number privately, this could be improved further. I am not aware of any, but that does not mean they don't exist.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1539
Joined: Thu Jul 30, 2009 3:16 pm UTC

### Re: Secret Santa

HonoreDB wrote:This took over my brain for way too long.

You're not joking! Anyway, I think I have it.

Edit: No I don't have it - this doesn't work

1. Secret Santa with bounded number of operations and correct probabilities.
Spoiler:
Put everyone's name into a hat. Each person pulls a name out in turn. This is the who they are going to be giving a present to.

If they get their own name, it is set to one side and they draw again. After drawing again, their name goes back into the hat ready for the next draw.

If the last person pulls out their own name, then everyone else's name goes into another hat and the last person draws from that. They swap recipients. So if the last person is Eve and she picks her own name, then all other names go into a hat and she draws again. If she picks Bob, and Bob was going to give a present to Carol, then now Bob gives a present to Eve and Eve gives a present to Carol.

Obviously this leaks information like a sieve, but at least the probabilities are correct. Not counting redraws when someone other than the last person picks their own name (which don't affect the odds at all), there are two ways for any given graph to be achieved. The natural drawing, for example:

A picks D
B picks E
C picks B
D picks A
E picks C

And the drawing where the last person picks again:

A picks D
B picks C
C picks B
D picks A
E picks E
E redraws from A,B,C & D, and picks B. E and B swap recipients, so it becomes:

A picks D
B picks E
C picks B
D picks A
E picks C

This second method happens with probability 1/(N-1) less often than the first, but all possible derangements are still equally likely.
Edit: If the last person picks themself, there is no way they can end up in a 2-loop. So not all derangements have the same probability - those where the last person to draw is in a 2-loop are less likely than they should be. Drat.

2. Same again but without leaking information.
Spoiler:
To avoid leaking information, you can randomly assign each person a number. Have a red box for each person, with two envelopes with their name in, one labeled "From" and one labeled "To":

Code: Select all
+-------Red-------+  +-------Red-------+  +-------Red-------+|  From    To     |  |  From    To     |  |  From    To     || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ || |Alice| |Alice| |  | |Brian| |Brian| |  | |Carol| |Carol| || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ |+-----------------+  +-----------------+  +-----------------+

Have a second set of green boxes, with two envelopes with a number in, this time one labeled "From#" and one labeled "To#":

Code: Select all
+------Green------+  +------Green------+  +------Green------+|  From#   To#    |  |  From#   To#    |  |  From#   To#    || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ || |  1  | |  1  | |  | |  2  | |  2  | |  | |  3  | |  3  | || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ |+-----------------+  +-----------------+  +-----------------+

Shuffle both sets of boxes separately (e.g. in a sack), then match up each one of the red boxes with a green box. Swap the "To" envelope in each red box with the "From#" envelope in the corresponding green box. This will get you something like this:

Code: Select all
+-------Red-------+  +-------Red-------+  +-------Red-------+|  From    From#  |  |  From    From#  |  |  From    From#  || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ || |Brian| |  2  | |  | |Alice| |  3  | |  | |Carol| |  1  | || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ |+-----------------+  +-----------------+  +-----------------++------Green------+  +------Green------+  +------Green------+|  To      To#    |  |  To      To#    |  |  To      To#    || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ || |Brian| |  2  | |  | |Alice| |  3  | |  | |Carol| |  1  | || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ |+-----------------+  +-----------------+  +-----------------+

Now everyone has a number, but nobody knows who has which number.

Shuffle the green boxes again in a sack. This corresponds to the hat in the first method. For each red box in turn, pull out a green box from the sack. Ask a third party (different each time) to take out and open the "From#" envelope from the red box, and the "To#" envelope from the green box, and say whether they contain different numbers or not.

If they are different, then take the "To" envelope from the green box, and put it in the red box. Set the red box aside, and throw away the green box.

If they are the same, then put the "To#" envelope back in the green box and set it aside. Pull out another green box. This time you know the numbers will be different, so you don't need to compare. Just take the "To" envelope from the green box, and put it in the red box. Set the red box aside and put the original green box back in the sack for the next draw.

When you draw the last green box (Lgreen) to match the last red box (Lred), and if the numbers are the same, then put all the other red boxes in a sack and pull one out (Xred). Take the "To" envelope from the red box you just chose (Xred), and put it in the last red box (Lred). Take the the "To" envelope from the last green box (Lgreen) and put it in the box you just chose (Xred).

All that will leave you with something like this:

Code: Select all
+-------Red-------+  +-------Red-------+  +-------Red-------+|  From    To     |  |  From    To     |  |  From    To     || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ || |Brian| |Alice| |  | |Carol| |Brian| |  | |Alice| |Carol| || +-----+ +-----+ |  | +-----+ +-----+ |  | +-----+ +-----+ |+-----------------+  +-----------------+  +-----------------+

Shuffle the red boxes. Open each "From" envelope, and hand that person the "To" envelope from the same box. That is the person they will be giving a present to.

In fact you do not need third parties for the comparisons of numbers. Nobody ever gets to find out which number goes with which person, and for N people there are N comparisons. So each person can do one comparison and no information is leaked.
Edit: This bit still works, if you can come up with a derangement expressed as it is here with numbers, then it can be applied to a group of people with no information leak.

I believe this is also kind of doable by generating all possible graphs (e.g. for 5 people there are 2, one of a 2-loop & a 3-loop, and one of a 5-loop), calculating the probability of each, picking one with the correct odds, and applying it to the group. But this gets complicated, and for more than 15 people will take all day with lots of sums. More than 20 is not really feasible. I did discover by simulation that as N increases, the chances of getting a graph without a 1-loop in the first try rapidly approaches 1/e, which is kind of neat, and which Wikipedia confirms.

Sandor.
Last edited by Sandor on Thu Dec 16, 2010 4:05 pm UTC, edited 1 time in total.
Sandor

Posts: 98
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Secret Santa

Spoiler:
1. Create a computer program that can shuffle a list (randomize order but keep elements the same).
2. Add each person's name to a list, and shuffle.
3. Each person is assigned to give a present to the next person down on the list.
4. The computer program emails each person the name of their gift recipient, and nobody peeks at eachother's email but each person looks at their own.
5. Computer program deletes the list.
Moose Hole

Posts: 400
Joined: Fri Jul 09, 2010 1:34 pm UTC

### Re: Secret Santa

Moose Hole wrote:I have the answer.

Spoiler:
1. Create a computer program that can shuffle a list (randomize order but keep elements the same).
2. Add each person's name to a list, and shuffle.
3. Each person is assigned to give a present to the next person down on the list.
4. The computer program emails each person the name of their gift recipient, and nobody peeks at eachother's email but each person looks at their own.
5. Computer program deletes the list.

This does not satisfy the criteria specified, as for example you know with 100% probability that the person who you are getting a gift for is not the person getting a gift for you.

If you do it not as a list but as a derangement, then this is identical to the “big envelope full of little envelopes” method, except you have a computer carrying out the menial tasks.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

I have a thought, but it’s 2:30am now so there’s a good chance I forgot something. Nonetheless, here’s what I’ve come up with as a way for a group of N people to make a secret-Santa-style derangement of themselves with no outside help and with no one learning anything other than the identity of the person they have to get a present for:

Spoiler:
This requires everyone to be trustworthy. So if you have a saboteur, it will break down. In fact it’s pretty easy to break down accidentally in real life, as it also requires people to be extremely punctual and have synchronized watches. But I suspect it could be made a lot more robust with slight modification.

We use a four-step plan. First is the coding phase, then the timing phase, the targeting phase, and finally the identifying phase.

The coding phase
Put the numbers from 1 to N in a hat. Each person draws one and keeps it, but does not share it. This is their code.

The timing phase
Put the numbers from 1 to N in a hat. Each person draws one and keeps it, but does not share it. This is their time.

The targeting phase
Put the numbers from 1 to N in a hat in the main room and leave it there.

Each person goes into a separate room, so no one can see nor hear anyone else (it’s okay if people know who went into which room, just so long as once you’re in your own room you can’t tell when the other doors open and close—if you want you can number the rooms 1 to N and have each person draw a room number from a hat, or the rooms can be preassigned before starting the rest of it—the important point is that rooms assignments are not a function of code or time numbers).

After one minute, the person with time 1 comes out to the main room. This person draws a single number from the hat and looks at it. (If it is their own code, they draw another number then put the first one they drew back.) They keep what they draw, so it is no longer in the hat. This is their target. This person goes back into the separate room they came from.

After another minute, the person with time 2 comes out to the main room. This person draws a number from the hat to be their target, making sure it is not their own code, and goes back to their separate room.

This continues minute by minute until their are only 2 numbers left in the hat.

The person with time N-1 looks at both numbers in the hat. If one of them is their own code, they take the other one. Otherwise, they leave them both. Either way, they return to their room.

The person with time N comes out a minute later. If there is only one number remaining, they take it. It cannot possibly their code, since it must have been the code of the person with time N-1. If there are two numbers remaining, they choose one of them which is not their own code. This is their target. They return to their room.

After another minute the person with time N-1 come out. If there is a number remaining (meaning they didn’t take one before), they take it as their target. Either way, they then return to their room.

Everyone now has a code, a time, and a target, all of which are secret from the other people. We have already used the time numbers, and are done with them.

The identifying phase
Everyone is in their own separate room. Each person writes their real name and address on the back of a photo of themself (or something, just so long as it uniquely identifies who they really are in real life.)

After one minute, the person with code 1 comes out and puts their picture and name in the main room, then returns to their own separate room. After another minute the person with target 1 comes out and takes the picture with name and address, then returns to their own separate room. This person, with target 1, has to get a present for the person with code 1, whose real life identity they now know.

After another minute, the person with code 2 puts their picture in the main room, then returns to their own room. After another minute, the person with target 2 comes out and takes that picture, then returns to their own room.

This continues until the person with code N has put their picture out, and it has been taken by the person with target N. Now everyone knows the identity of the person they have to get a present for.

The end.

This takes linear time O(N) to carry out, compared to the nearly-factorial time required by the envelope-of-envelops method that involves constructing all possible derangements.

Edit: quick explanation of why this works:

Spoiler:
For any given participant, the only information they receive is as follows:

100% correlation between real life identity and code number of one other person (the person they have to get a gift for), as desired.

Up to 100% correlation between time and target of at least one other person. This is realized when, during the targeting phase, someone draws their own code and thus knows that no one with lower time has them as target, and someone with higher time will (except for time N, who may have information about the target of the person with time N-1).

But correlation between time and target does not provide any information about code or identity, since no one has any way to bridge the gap between the time-target and code-identity information pairs of other people. Room assignment of course is correlated only with real life identity.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

Qaanol wrote:I have a thought, but it’s 2:30am now so there’s a good chance I forgot something. Nonetheless, here’s what I’ve come up with as a way for a group of N people to make a secret-Santa-style derangement of themselves with no outside help and with no one learning anything other than the identity of the person they have to get a present for:

Spoiler:
This requires everyone to be trustworthy. So if you have a saboteur, it will break down. In fact it’s pretty easy to break down accidentally in real life, as it also requires people to be extremely punctual and have synchronized watches. But I suspect it could be made a lot more robust with slight modification.

We use a four-step plan. First is the coding phase, then the timing phase, the targeting phase, and finally the identifying phase.

The coding phase
Put the numbers from 1 to N in a hat. Each person draws one and keeps it, but does not share it. This is their code.

The timing phase
Put the numbers from 1 to N in a hat. Each person draws one and keeps it, but does not share it. This is their time.

The targeting phase
Put the numbers from 1 to N in a hat in the main room and leave it there.

Each person goes into a separate room, so no one can see nor hear anyone else (it’s okay if people know who went into which room, just so long as once you’re in your own room you can’t tell when the other doors open and close—if you want you can number the rooms 1 to N and have each person draw a room number from a hat, or the rooms can be preassigned before starting the rest of it—the important point is that rooms assignments are not a function of code or time numbers).

After one minute, the person with time 1 comes out to the main room. This person draws a single number from the hat and looks at it. (If it is their own code, they draw another number then put the first one they drew back.) They keep what they draw, so it is no longer in the hat. This is their target. This person goes back into the separate room they came from.

After another minute, the person with time 2 comes out to the main room. This person draws a number from the hat to be their target, making sure it is not their own code, and goes back to their separate room.

This continues minute by minute until their are only 2 numbers left in the hat.

The person with time N-1 looks at both numbers in the hat. If one of them is their own code, they take the other one. Otherwise, they leave them both. Either way, they return to their room.

The person with time N comes out a minute later. If there is only one number remaining, they take it. It cannot possibly their code, since it must have been the code of the person with time N-1. If there are two numbers remaining, they choose one of them which is not their own code. This is their target. They return to their room.

After another minute the person with time N-1 come out. If there is a number remaining (meaning they didn’t take one before), they take it as their target. Either way, they then return to their room.

Everyone now has a code, a time, and a target, all of which are secret from the other people. We have already used the time numbers, and are done with them.

The identifying phase
Everyone is in their own separate room. Each person writes their real name and address on the back of a photo of themself (or something, just so long as it uniquely identifies who they really are in real life.)

After one minute, the person with code 1 comes out and puts their picture and name in the main room, then returns to their own separate room. After another minute the person with target 1 comes out and takes the picture with name and address, then returns to their own separate room. This person, with target 1, has to get a present for the person with code 1, whose real life identity they now know.

After another minute, the person with code 2 puts their picture in the main room, then returns to their own room. After another minute, the person with target 2 comes out and takes that picture, then returns to their own room.

This continues until the person with code N has put their picture out, and it has been taken by the person with target N. Now everyone knows the identity of the person they have to get a present for.

The end.

This takes linear time O(N) to carry out, compared to the nearly-factorial time required by the envelope-of-envelops method that involves constructing all possible derangements.

Thats doesn't work. Every possible derangement is supposed to be equally likely. Here are all 9 ways your solution could pan out with 4 people. The odds are in parenthesis:

Code: Select all
A>B (1/3)  A>B B>A (1/9)    A>B B>A C>D D>C (1/9)  A>B B>C (1/9)    A>B B>C C>D D>A (1/9)  A>B B>D (1/9)    A>B B>D C>A D>C (1/9)A>C (1/3)  A>C B>A (1/6)    A>C B>A C>D D>B (1/6)  A>C B>D (1/6)    A>C B>D C>A D>B (1/12)    A>C B>D C>B D>A (1/12)A>D (1/3)  A>D B>A (1/6)    A>D B>A C>B D>C (1/6)  A>D B>C (1/6)    A>D B>C C>A D>B (1/12)    A>D B>C C>B D>A (1/12)

Your attempt does a similar thing to mine - up until the last person, if someone draws their own name, they just redraw. I thought that was OK, but it's not - it messes up the odds.

Sandor
Sandor

Posts: 98
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Secret Santa

Sorry for the double post, but these are some new thoughts...

For 7 people the possible graphs are:

• Two 2-loops and a 3-loop: 210 derangements
• A 2-loop and a 5-loop: 504 derangements
• A 3-loop and a 4-loop: 420 derangements
• A 7-loop: 720 derangements
Total derangements: 1854

So for 7 people you have to come up with a method of randomly picking 1 out of 1854 possibilities. The prime factors of 1854 are 2, 3, 3 & 103. Any method that consists of repeatedly picking 1 from X options, and doesn't at some stage pick 1 from 103 (or multiple of 103) cannot possibly get the correct odds. The envelope-of-envelops method of course just picks 1 from 1854 straight off.

I think the envelope-of-envelops is the only way to do this. It could be made more practical.

Sandor
Sandor

Posts: 98
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Secret Santa

Sandor wrote:Thats doesn't work. Every possible derangement is supposed to be equally likely.

I am quite convinced that is not what the rules say. What the rules say is that for any given person, that person must believe each of the other people is equally likely to be getting them a gift, and equally likely to be getting anyone else a gift.

That is also why I don’t think the envelope-of-envelopes method with all possible derangements works either. Because then everyone knows their odds of being in a 2-cycle (if they take the time to list out all possible derangements), which in general I suspect is not 1/(N-1).

Sandor wrote:Here are all 9 ways your solution could pan out with 4 people. The odds are in parenthesis:

Code: Select all
A>B (1/3)  A>B B>A (1/9)    A>B B>A C>D D>C (1/9)  A>B B>C (1/9)    A>B B>C C>D D>A (1/9)  A>B B>D (1/9)    A>B B>D C>A D>C (1/9)A>C (1/3)  A>C B>A (1/6)    A>C B>A C>D D>B (1/6)  A>C B>D (1/6)    A>C B>D C>A D>B (1/12)    A>C B>D C>B D>A (1/12)A>D (1/3)  A>D B>A (1/6)    A>D B>A C>B D>C (1/6)  A>D B>C (1/6)    A>D B>C C>A D>B (1/12)    A>D B>C C>B D>A (1/12)

Your attempt does a similar thing to mine - up until the last person, if someone draws their own name, they just redraw. I thought that was OK, but it's not - it messes up the odds.

Sandor

I have not checked your calculations, but I assume they are accurate—for something. But you have not explained what the letters A, B, C, and D stand for. If they stand for what I call the time of each person, so order in which people draw targets, then you are right, up to a point. The only way anyone in my scheme can get information connecting target with real life identity is when considering the odds of being in a 2-cycle. And only the people with the last two times can ever get any such information. The biggest issue is that the person with time N, if they see two names, one of which is their own, then they know they are not in a 2-cycle. However, this does shine some light on how a real solution could look.

Spoiler:
If you make a derangement with exactly one 2-cycle, the odds of being in the 2-cycle are 2/N. If you make another graph with zero 2-cycles, the odds of being in a 2-cycle are 0. So if you make cN large envelopes (for some positive integer c, such as 1) with small envelopes giving as per a derangement with one 2-cycle, and c(N-2) large envelopes with small envelopes giving names as per a derangement with zero two-cycles, then choose a large envelope at random, the odds of any person being in a 2-cycle are exactly 1/(N-1) as desired. Combine that with a self-double-blinding method, and I think we may have a working solution.

Let me see if I can hammer out the details:

Spoiler:
Someone from the group makes a random permutation f of the numbers from 1 to N and makes envelopes labeled with x on the outside and holding f(x) values on the inside, and another set of envelopes for f-1.

The rest of the group splits in two subgroups. One subgroup makes N large envelopes, each of which contains small envelopes for g, a derangement of the numbers from 1 to N with exactly one 2-cycle. It is important that each number appear in the 2-cycle for exactly two functions g, so that all numbers are equally likely to be in a 2-cycle if there is one.

The other subgroup makes N-2 more large envelopes, each of which contains small envelopes for h, a derangement of the numbers from 1 to N with exactly zero 2-cycles. The h’s should all be different, and no two h’s should give the same value for any given number.

The envelopes storing h’s and the envelopes storing g’s must be indistinguishable, so we will henceforth refer to this function as g, even if it was actually an h, since no one can tell them apart anymore.

So there are now 2N-2 large envelopes. You put them all in a hat and choose one at random. Each person draws a number from 1 to N out of a hat and keeps it secret. That person opens the corresponding f envelope, reads a number, opens the the corresponding g envelope, reads a number, then opens the corresponding f-1 envelope.

Finally, everyone draws a number from 1 to N out of a hat and lets everyone else see it. The person who has just drawn the number you got out of the last envelope is the person you have to buy a present for.

Actually even this doesn’t work perfectly, because the people who made the derangements have some slight probabilistic information about their odds of being in a 2-cycle based on whether the g(x) for their x corresponds to a derangement they saw during construction or not. I’m not certain we can alleviate that problem while still maintaining the 1/(N-1) desired odds of being in a 2-cycle, at least not with this method of only using derangements with zero or one 2-cycle.

So what we need is some distribution over all possible derangements, guaranteeing that the probability of being in a 2-cycle is exactly 1/(N-1). That is certainly a necessary condition, and with the inclusion of double-blinding I think it becomes sufficient as well.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

I finally have a complete solution for a group of N people with no outside help. It may be 6:30am and I may have been up all night, but this time I am totally confident in the correctness of my answer. It requires having at least 2 trustworthy people, and is very simple to carry out, not requiring much work at all.

Spoiler:
There are N total participants. Persons P and Q situate themselves so they cannot see what the other is doing, but they can hand papers back and forth. No one else can see either P or Q.

Person P randomly and secretly assigns a unique number from 1 to N to each person participating, thus making a bijection f between names and numbers. To do so, person P writes down each name, puts that name in an unlabeled envelope, and puts that envelope in an envelope labeled by that person’s number. These are the f(x) envelopes. Person P also keeps a cheat-sheet that no one else gets to see, showing the bijection between names and numbers.

Person Q makes a derangement g of the numbers from 1 to N with zero 2-cycles. For example, a single N-cycle will work. The same person also makes a derangement h of the numbers from 1 to N with exactly one 2-cycle. For example, a single 2-cycle and a single (N-2)-cycle. (Note: Special case of N=4 participants cannot have exactly one 2-cycle, requiring slight modification which I will detail in a moment.) This person takes two large envelopes and writes “Red” on one and “Blue” on the other.

For each integer x from 1 to N, person Q puts the number g(x) inside an unlabeled envelope and puts that inside an envelope with x on the outside. They randomly choose one of the “Red” or “Blue” envelopes and put all the g envelopes inside it.

For each integer x from 1 to N, person Q puts the number h(x) inside an unlabeled envelope and puts that inside an envelope with x on the outside. They put all the h envelopes inside the other color envelope.

This same person Q now writes “Blue” on N-2 pieces of paper and “Red” on N-2 pieces of paper, and then on 2 more pieces of paper they write the name of the color on the envelope with the h derangement (the one with a 2-cycle) in it. (Note: Special case of N=4 participants instead uses 1 piece of paper with the color of the 2-cycle and 2 with the other color.) All these slips of paper go in a hat.

Person Q gives the color envelopes and the hat with slips of paper to person P, and person P gives the f(x) bijection envelopes to person Q.

Person P draws a color from the hat and opens the envelope with that color on the outside, taking out the little numbered envelopes. Then they go through the list of names by number.

Person P picks a name, say person R, looks up the corresponding number on the cheat sheet, and opens the little envelope with that number on it from the colored envelope, finding an unlabeled envelope. Person P gives the unlabeled inner envelope to person Q. Person Q opens it and finds a number. Person Q opens the f(x) envelope with that number and gives the unlabeled envelope from inside to person P. Person P writes the name of person R on the outside of that envelope.

The previous paragraph is repeated for all names on the list. Then person P hands each participant the envelope with their name on the outside. Each person opens the envelope they get, and on the inside is the name of the person they have to get a present for.

Edit: Of course, if you can’t count on identifying two trustworthy people in your group, you can augment the above with a zero-knowledge proof system. For example,

Spoiler:
Repeat the above 20 times, putting all the papers and envelopes from a given trial in a box with that trial’s number on it. Roll a fair die so everyone can see (roll it many times first to show it’s fair) and leave that box closed. Open every other box. For each box, have everyone all together verify that everything was done exactly according to the above procedure, meaning the correct number of color labels, and the proper types of derangements, and that the resulting sealed envelopes when opened actually produce the correct type of derangement, and so forth. If all 19 boxes show perfect correctness, then you can be 95% certain that the other box was also done correctly. So use the sealed envelopes from that box.

Obviously 20 was arbitrary, and if you repeat a thousand times and check 999 for quality assurance, then if they pass you can be 99.9% sure the other box is acceptable. So you can become arbitrarily certain. Of course, if any of the randomly-opened boxes do contain errors, then you can know not to trust at least one of the people you chose. By cycling through every combination of people, you can select 2 trustworthy individuals if they exist. However, since there are N(N-1)/2 pairs to try, you need to use quite a few trials in each zero-knowledge proof to be confident you haven’t mistakenly chosen to trust a pair who just happened to have gotten lucky on the die roll.

So the zero-knowledge proof is a lot of work. If you have a simpler way to verify that two people are trustworthy, that would be excellent.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

Sorry about the triple post. I was explaining this to my sister and she came up with a simple way to make sure the people do what they’re supposed to.

Spoiler:
Split the group in halves, the P half and the Q half. Have the entire P half work together to do/oversee/verify what person P does in my above procedure. Have the entire Q half do the same for person Q. Now in order for the process to break down without anyone else knowing, an entire half of the group would have to conspire.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

Qaanol wrote:Person Q makes a derangement g of the numbers from 1 to N with zero 2-cycles. For example, a single N-cycle will work. The same person also makes a derangement h of the numbers from 1 to N with exactly one 2-cycle. For example, a single 2-cycle and a single (N-2)-cycle.

If I have understood what you are saying, then person Q knows which two graphs1 are possible, and everybody knows there can be at most a single 2-cycle (I assume everyone knows the details of the method being used). If come Secret Santa day the first two presents given happen to be Alice to Bob and then Bob to Alice, now everyone knows that nobody left will be getting a present from the person they will be giving a present to.

We've both (I believe) come up with methods for applying a graph to a group of people in a random fashion to generate a derangement, by assigning a secret number to each person. The problem is generating the graph in the first place. This doesn't get much easier if you try to write a program to come up with the derangement, with the same constraint of bounded number of operations2. The envelope-of-envelopes method rapidly fails - with 21 people there are more than 2^64 derangements.

Sandor

(1) By graph, I mean the possible combinations of cycles. For example with 5 people there are two graphs, a 2-cycle and a 3-cycle, or a single 5-cycle. These can be applyed to 5 people to generate 44 derangements.
(2) For this you have to pretend that your Psuedo Random Number Generator (PRNG) is actually a true RNG. I suspect the nature of PRNGs means that the method of "draw names from a hat, and keep trying until you get zero 1-cycles" will in fact have a bounded number of operations.
Sandor

Posts: 98
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Secret Santa

Sandor wrote:If come Secret Santa day the first two presents given happen to be Alice to Bob and then Bob to Alice, now everyone knows that nobody left will be getting a present from the person they will be giving a present to.

I do not see a requirement that information still be secret after the first present has been opened and its giver and receiver revealed. Furthermore, I’m not convinced there is a way to do it. If we use a method like mine, then we need a probability distribution over all possible derangements that gives exactly 1/(k-1) odds of being in a 2-cycle (for people who have not yet had their Santa revealed) when there are k Santas still to be revealed, for all 3<k≤N, no matter what order the Santas are revealed in.

And the thing about your class of solutions (where the recipients are assigned, in effect, by random drawing) is that toward the end there must be some correction mechanism to avoid having a 1-cycle. Similarly, when you get down to the penultimate person, if they happen to get themself (or, in your case, the two envelopes happen to contain the same identification number), there has to be a procedure which assigns recipients for the last two, while preserving the overall probability of being in a 2-cycle at 1/(N-1) (and indeed 1/(k-1) throughout the revelation). I’m not sure this can be done.

I’m sticking with my method as a way to generate a derangement where everyone considers everyone else equally likely to be getting a gift for anyone besides their own known recipient. In particular, each person considers their own recipient just as likely to be their Santa as anyone else is (as well as anyone else’s).
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

I have to admit I didn't understand all the math involved in the previous solutions, but I think I've come up with something that's both simple and fast, and doesn't require outside help. It does require people to be moderately trustworthy. If this doesn't work, I welcome corrections.

Spoiler:
Step 1: Number a set of envelopes 1-N. Have one person shuffle them together.

Step 2: Pass out the envelopes randomly so that the pass-out-er can't see which number each person is getting. Alternatively, just pass them around the room upside down so no one else can see which number a person is getting, and no one can turn over the stack to look at the numbers without being obvious. The number of the envelope becomes the person's number.

Step 3: Each person writes their name (and possibly address, likes/dislikes, or requests) on an index card and puts that card into the envelope. The envelopes are passed in (again, upside down) and placed in a box in the middle of the room, and shuffled again.

Step 4: Starting from one end of the room, each person goes up and looks through the envelopes. This is where it gets a little complicated, and I can't think of a way to say it mathematically, but basically--if N=100, then persons 1-10 can choose from 91-100, persons 11-20 can choose from 81-90, persons 21-30 can choose from 71-80, etc. If N=50, then persons 1-5 can choose from 46-50, etc. In other words, each person has a subset of numbers to choose from that does not include theirs. These numbers can be written out ahead of time and placed on a sheet of paper for quick reference. So, the first person to pick an envelope looks through and chooses the first envelope they see in their permitted interval, removes the index card, replaces the envelope, and sits down. The next person follows the same procedure, and so on. If someone picks up an empty envelope, they simply replace it and continue looking through to find the next one.

So, no person has any probability of picking their own card. No one else is close enough to the envelopes to see which ones are being picked up or replaced. No one knows anyone else's number, so no one knows who could be in the recipient interval of anyone else. Since the envelopes are replaced, no one can tell without opening it if an index card has been removed. The only information leaked could be if the second person to choose happens to be in the same interval as the first, so that they would see the empty envelope and know that the first person to choose did not pick the second person. I think if the intervals are small enough, this is not very likely. The third person might also realize that at least one of the first two people did not pick the third person, but it would become increasingly more difficult to figure this out as more and more people choose their envelopes, and I think the simplicity of the method makes up for the small amount of information that is leaked.

"Lunch Meat, you're so brilliant sometimes, and when you're not, you're just weird." -my best friend

"Are you trying to apply logic to Lunch Meat? That's kind of a pointless exercise." -my best guy friend
Lunch Meat

Posts: 64
Joined: Fri Jun 20, 2008 6:30 am UTC

### Re: Secret Santa

Lunch Meat wrote:I think I've come up with something that's both simple and fast, and doesn't require outside help. It does require people to be moderately trustworthy. If this doesn't work, I welcome corrections.

I think that works pretty well. There are a couple of little niggles that I have with it, though it doesn't particularly effect the practicalities.

Spoiler:
Firstly, say your group size is prime. You could use groups of uneven size to work around, but it loses some of its elegance.

The real problem is that the way the groups are allotted to each other makes for a restriction on the possible ways that people can be paired up. What I mean is, in your example, you can have A allotted B and B allotted A. But you can't have A allotted B, B allotted C and C allotted A. If you think about things like this as loops, then only even length loops are possible with your arrangement. I think you can get around that by having 1-10 being paired with 46-55, 11-20 paired with 56-65 etc. Then I think you can get any kind of permutation, or at least any length of loop. I think the easiest way to work it would be to divide the envelopes into three groups and then pair each group with a set of envelopes that are made up of the other two groups.

So, for 100 people, you could have 1-33, paired with 51-83, 34-66, paired with 84-100 and 1-16, and finally 67-100 paired with 17-50.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5210
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Secret Santa

I think this one might work, assuming you can trust your co-workers to follow the rules:

Spoiler:
Number envelopes 1-N.
Blindly pass them out at random so no one knows anyone else's number.
Everyone puts their own name on a card and seals it in their envelope. Remember your number.
Collect the envelopes face down (so your can't see the numbers), and put them in a pile in the next room.
Everyone enters the room one at a time in random order/times.

On your turn in the room:
Shuffle the envelopes face down, and flip them one at a time until you come to a number greater than yours. Take that envelope.
If you make it through the whole pile without finding one larger than yours, take the smallest number in the pile.
redrogue

Posts: 119
Joined: Tue Dec 15, 2009 9:17 pm UTC

### Re: Secret Santa

Spoiler:
Consider three people: person 1 comes in first, shuffles the envelopes, and the one on top happens to be number 3. Then person 3 comes in, doesn't find a number bigger than that (obviously), so leaves with number 1. Person 2 then comes in, and is forced to take his own envelope.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6779
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Secret Santa

From the initial post:
Given a set of n > 3 people...

Your scenario wouldn't come up. Try it with a base case of 4 people and you'll find you end up with either two loops (Fran<->Jack, Alice<->Zoey) or one loop (Bob->Joe->Jill->Matt->Bob).

Besides, secret santa with n = 3 isn't fun. Nobody can pull their own name, so once you know who you are giving a gift to, you can deduce who is giving one to you.
redrogue

Posts: 119
Joined: Tue Dec 15, 2009 9:17 pm UTC

### Re: Secret Santa

All right, here's one with four people then.
Spoiler:
Person 1 comes in first, shuffles the envelopes, and the one on top happens to be 3.
Person 3 comes in, and the only larger number (and hence the first larger number he sees) is 4, so he takes it.
Person 4 comes in, and doesn't find any larger numbers (duh), so he takes 1.
Person 2 comes in, and the only remaining envelope is his own.
Nitrodon

Posts: 444
Joined: Wed Dec 19, 2007 5:11 pm UTC

### Re: Secret Santa

Right... that result can be extended to any number, it was just easier to show with 3.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6779
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Secret Santa

In that case, replace the last bit with "Alright everyone, go into the room take envelope (your number+1) % n. We shuffled the envelopes already, so this will make a random hamiltonian cycle. We'll just forget about the leaking information rule this year. Whoever gets me should note that I like vodka."
redrogue

Posts: 119
Joined: Tue Dec 15, 2009 9:17 pm UTC

### Re: Secret Santa

For people who didn’t quite follow my solution the first time around:
Spoiler:
Once you’ve got the name of your recipient, in order for you to believe that everyone besides yourself is equally likely to be your Santa, you must believe in particular that your recipient is just as likely as anyone else to be your Santa.

So if there are N people, then N-1 of them are not you. Thus you must believe that for any one of them, the odds of that person being your Santa have to be 1/(N-1). In particular, your recipient must have 1/(N-1) odds of being your Santa. But if your recipient is your Santa, then you are in a 2-cycle on the graph of recipients.

Thus, the entire purpose of my method was to guarantee that everyone has a 1/(N-1) chance of being in a 2-cycle. To do this simply, I made it so there were two possibilities. Either there were no 2-cycles, so for my example I said there is one big N-cycle; or there are some 2-cycles, so for my example I said there is one 2-cycle and one (N-2)-cycle.

Then I made a process where the person who created the graphs of cycles and put labels on them to identify them, did not know which one was drawn. The person who drew one did not know which label meant which cycle. And I made it so the probability of drawing either graph was just right to make everyone have 1/(N-1) odds of being in a 2-cycle.

Finally, I had the labeled envelopes each contain an unlabeled envelope that contains the actual piece of information, so that the person who sees the information on the outer envelope does not know what is inside the envelope, and the person who finds out what is inside does not know what was on the outside.

This can be strengthened slightly to begin to satisfy Sandor’s extra requirement,

Spoiler:
We can modify my solution method (double-blind where one person/group makes the derangement envelopes and proper ratio of numbers for each in a hat, another person/group makes the bijection between people and numbers, and the labeled envelopes contain blank envelopes that contain the next piece of information, so the two people/groups pass the blank envelopes back and forth) to partially satisfy Sandor’s condition that as presents get opened and Santas are revealed one by one, no extra information is reveal. But only up to a point. We can either do it so no one gets any extra information, or so the only people who get information are those who are linked to someone who has been revealed. The latter allows potentially a few more people to open their gifts before everyone has some extra probabilistic envelope, but the former follows more closely the tenet that nobody gain an information advantage. Neither one will let you get all the way down to the end though.

For a particular N, look at the different shapes of graphs of a derangement. For example, with N=8 we have a single 8-cycle, a 6-cycle and a 2-cycle, a 5-cycle and a 3-cycle, two 4-cycles, a 4-cycle and two 2-cycles, two 3-cycles and a 2-cycle, and four 2-cycles, for a total of seven different graphs. If we assign to them probabilities of being drawn as, respectively, A B C D E F and G, then we can try to calculate those probabilities. Obviously A+B+C+D+E+F+G=1. Also, to make everyone equally likely to be your Santa, we must have the odds of being in a 2-cycle at 1/7, so that tells us (B/4)+(E/2)+(F/4)+(G)=(1/7).

After the first person opens a gift and their Santa becomes known, we have four more equations. Namely, for the person who was picked (who now knows whether he/she is in a 2-cycle, but if not then wants to know the odds of being in a 3-cycle), for the person whose recipient was picked (who has learned nothing new), for the person whose recipient’s recipient was picked (and now knows whether he/she is in a 2-cycle, but if not then wants to know the odds of being in a 3-cycle), and for everyone else. These all give linear equations when set equal to the required probability of 1/6 (but 1/7 for the Santa of the person who opened first), but not all of them are linearly independent.

Similarly, after the second person goes, the first two might form a 2-cycle, one of them might be the other’s Santa but not vice-versa, or they might not be directly linked. For each case, all possibilities from among “Being one of the people who went”, “Being the Santa of one of the people who went”, “Being the Santa of the Santa of one of the people who went”, and “Not being directly linked to either person who went” each give a linear equation, though not all of them are necessarily independent.

This can be continued as long as possible, until we run out of free variables. Those variables are just the probabilities of each shape of graph being selected, so for N-8 we have seven of them, meaning we cannot support more than seven independent equations. I haven’t calculated them all out, but I think for N=8 we can only guarantee that nobody gains any extra knowledge through the second person opening a gift. So when the third person goes, someone may (depending on graph shape) get some extra probabilistic information. I think we need N=10 to bump that up so the third person can go without imparting any information.

Also, in my preliminary calculations, it looks like when the first person goes, no matter what N is, only their Santa’s Santa requires an extra equation. That is, the equations for everyone else are all linear combinations of the existing equations. Can anyone prove or disprove that?
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Secret Santa

Qaanol wrote:For a particular N, look at the different shapes of graphs of a derangement. For example, with N=8 we have a single 8-cycle, a 6-cycle and a 2-cycle, a 5-cycle and a 3-cycle, two 4-cycles, a 4-cycle and two 2-cycles, two 3-cycles and a 2-cycle, and four 2-cycles, for a total of seven different graphs. If we assign to them probabilities of being drawn as, respectively, A B C D E F and G, then we can try to calculate those probabilities. Obviously A+B+C+D+E+F+G=1. Also, to make everyone equally likely to be your Santa, we must have the odds of being in a 2-cycle at 1/7, so that tells us (B/4)+(E/2)+(F/4)+(G)=(1/7).

I don't think this is right. One way to calculate the number of derangements of 8 people that have a graph of four 2-cycles is to take the number of permutations of 8 people (8!), and remove duplicates. The duplicates are a) rotations of the cycles, which you divide by 2^4 to remove, and b) permutations of cycles of the same length, which you divide by 4! to remove. That gives a total of 8!/(2^4 * 4!) = 105 derangements that have a graph of four 2-cycles.

The number of derangements for all the different shapes of graphs for 8 people are as follows. Wikipedia agrees that there are 14833 derangements for 8 people. Also, if you include 1-cycles in the graph shapes, the total comes to 8! as it should, so I am pretty sure these numbers are correct:

Code: Select all
Id  Shape of Graph         Number of Derangements             Probability==  ==============         ======================             ===========A   1*8-cycle              8!/(8^1 * 1!)            = 5040    5040/14833B   1*6-cycle, 1*2-cycle   8!/(6^1 * 1! * 2^1 * 1!) = 3360    3360/14833C   1*5-cycle, 1*3-cycle   8!/(5^1 * 1! * 3^1 * 1!) = 2688    2688/14833D   2*4-cycle              8!/(4^2 * 2!)            = 1260    1260/14833E   1*4-cycle, 2*2-cycle   8!/(4^1 * 1! * 2^2 * 2!) = 1260    1260/14833F   2*3-cycle, 1*2-cycle   8!/(3^2 * 2! * 2^1 * 1!) = 1120    1120/14833G   4*2-cycle              8!/(2^4 * 4!)            = 105      105/14833                                              Total = 14833

(B/4)+(E/2)+(F/4)+(G) does not equal (1/7). I think that is because you are implicitly counting (some of) the duplicates I eliminated above.
Sandor

Posts: 98
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Secret Santa

Read what I wrote again. In order to satisfy the requirements of the problem stated at the start of this thread, we must force the probability of being in a 2-cycle to be exactly 1/(N-1) at the outset.

I believe you have the correct numbers there (though I haven’t checked), and they serve to demonstrate my point: treating all derangement as equally likely does not suffice.

We need to assign probabilities to each shape of derangement in such a way that the odds of being in a 2-cycle are exactly 1/(N-1). For the case N=8, that means (B/4)+(E/2)+(F/4)+G=1/7. One way to do that is A = 3/7, B = 4/7, all the rest 0. That is just my 2-colored-envelopes method. But any allocation of probabilities satisfying that constraint will work. And some of them will keep everyone in the dark about things that have not yet been revealed to them even after the first few people open their presents and their Santas are revealed.
Small Government Liberal

Qaanol

Posts: 2258
Joined: Sat May 09, 2009 11:55 pm UTC

Next