From: Niklas Frykholm <niklas@...>
Date: 2004-10-04T17:49:53+09:00
Subject: [SOLUTION] Secret Santas (#2)

An interesting problem. It seems trivial at first, but when you start to 
think about whether a solution is possible or not and in which way you 
can assign santas as random as possible, but without painting yourself 
into a corner it gets quite complex. Here is a mathematical analysis:


At any stage in the solution we have a number of persons from different 
families that need to be assigned a santa, and a number of available 
santas. We define the "santa surplus number" SS(F) for a family F as:

   SS(F) := (number of available santas for this family) -
            (number of family members that haven't been assigned a santa)

The available santas for a family are the available santas that doesn't 
belong to that family.

It is clear that if SS(F) < 0 for some family then no santa assignment 
is possible, because there are not enough santas for that family.

Suppose that SS(F) >= 0 for all families, then a santa assignment is 
always possible. To see this, we look at what happens to the SS number 
when a santa is assigned.

Suppose that a person from family F is assigned a santa from family S. 
Let O be any other family. The assignment will cause the following 
changes to the SS numbers.

   SS(F) := SS(F)

     The family F looses an available santa, but the number of santas
     needed is also reduced by one, so SS stays the same.

   SS(S) := SS(S)

     The S family does not loose an available santa because the santa
     comes from the S family and could never be a santa for the S
     family.

   SS(O) := SS(O) - 1

     All other families loose an available santa.

If SS(O) = 0, for some family O, then the assignment will lead to an 
impossible configuration, because SS(O) will become negative. This gives 
us the rule for assigning santas without creating an impossible 
configuration:

   If SS(F) = 0 for some family F, then in the next santa assignment,
   either the santa or the person that is assigned a santa must come
   from the family F.

We can always make our santa assignments so that they follow this rule
*unless* there are three or more families with SS(F) = 0. But if SS(F) 
 >= 0 for all families, there can never be three families with SS(F) = 0.

To see this, let N be the total number of persons without santas (and 
also the number of available santas). Let S(F) be the number of 
available santas from family F and P(F) be the number of persons without 
santas from F, then

	SS(F) = (N - S(F)) - P(F) = N - S(F) - P(F)

So if SS(F) = 0 then:

         N = S(F) + P(F)

Suppose that there are two families A and B with SS(A) == 0 and SS(B) == 
0 then:

         N = S(A) + P(A)
         N = S(B) + P(B)

         2N = S(A) + S(B) + P(A) + P(B)

         (N - S(A) - S(B)) + (N - P(A) - P(B)) = 0

         N - P(A) - P(B) = 0    (since N - S(A) - S(B) >=0)
         N - S(A) - S(B) = 0    (and N - P(A) - P(B) >= 0)

         N = P(A) + P(B)
         N = S(A) + S(B)

In other words, then all santas and all persons come from those two 
families. So if two families have SS(F) = 0, there can be no other 
families with unassigned santas.

Since there will always be at most two families with SS(F) = 0, we can 
always select a santa according to the rule above. And we MUST select a 
santa according to that rule in order to not create an impossible 
situation. This means that if we randomize the choice of santa while 
following the rule, we get a selection that is as random as possible 
while obeying the constraints.

// Niklas