From: Peter <Peter.Vanbroekhoven@...>
Date: 2004-10-04T17:43:40+09:00
Subject: Re: [SOLUTION] Secret Santas (#2)

> [1] Statistics is not my strong suit. My reasoning is as follows:
> Consider a pool of 6 participants:
> Joe Smith
> Jane Smith
> Jim Smith
> Bob Dole
> Barbara Bush
> Bill Clinton
>
> The correct arrangement for this pathological case is an interleaving
> of Smiths and others, for example:
> Jane Smith
> Bill Clinton
> Joe Smith
> Bob Done
> Jim Smith
> Barbara Bush

I think for James' code, a correct arrangement would be like this:
Bob Dole
Barbara Bush
Bill Clinton
Joe Smith
Jane Smith
Jim Smith

The way you look at it, each person in your arrangement is the next
person's secret Santa, wrapping around the end of the array as needed,
right? Actually that's like putting people in a circle such that each
person's secret Santa is standing to his/her left (or right). But actually
that leaves out the arrangements with multiple smaller circles, so you
can't generate every solution this way. But James' solution does however.

> There is a 1/1 chance that SOMEONE will be picked for the first spot.
> There is a 3/5 chance that the next person will be of the opposite
> Smith/Non-Smith persuasion.
> There is a 2/4 chance that the next person will be of the opposite
> Non-Smith/Smith persuasion.
> There is a 2/3 chance for the next.
> There is a 1/2 chance for the next.
> There is a 1/1 chance for the last.
> The cumulative chance of all that occurring is the product:
> 3/5 * 2/4 * 2/3 * 1/2 = 1/10
>
> For an 8 person pool, the chances are:
> 4/7 * 3/6 * 3/5 * 2/4 * 2/3 * 1/2 = 1/35
> Re-arranged, that looks like:
> (4*3*3*2*2) / (7*6*5*4*3*2 )
> which is
> (4 * 3*2 * 3*2 ) / ( 7*6*5*4*3*2 )
> which is
> (4 * 2 * 3! ) / 7!
>
> Looking at this pattern, then, the chances of randomly picking a
> working pattern for pathological pool size of N seems to be:
>
> N/2 * 2 * ((N/2)-1)! / (N-1)! == N * ((N/2)-1)! / (N-1)!

The correct generalization is this:

  (2 * (N/2)! * (N/2)!) / N!

(This gives the same numbers as above for N = 3 and N = 4)

To see this: there are N! possible permutations of the N persons. The only
valid ones are the interleaved ones. There are 2 choices for the big
family: the odd or the even positions. Then there are two sets of N/2
persons who need to be assigned to N/2 positions each, with no
restrictions, which for each set can be done in (N/2)! ways. The total
number of valid combinations is 2*(N/2)!*(N/2)! out of N!.

For James' way of generating possibilities, he looses a factor 2, so only
(N/2)! * (N/2)! out of N! are OK. But for N = 10, he has 1 chance out of
252 to generate a working pattern. N = 12: 1 chance out of 924. For each
increase in N of 2, the chances get worse by about a factor 4. So it's not
that bad ;-)

Peter