From: Carlos <angus@...>
Date: 2004-10-04T22:49:48+09:00
Subject: Re: [SOLUTION] Secret Santas (#2)

[Niklas Frykholm <niklas@kagi.com>, 2004-10-04 15.14 CEST]
> >I didn't participate, but I thought it was a trivial case of sorting the
> >families by number of members and start giving santas from the most 
> >populous
> >down. I should have tested that theory with code, but I didn't have time on
> >the weekend :(. How can it not work?
> 
> Assume three families with one member each A, B, C. Since the families 
> are the same size, sorting by size will not do anything. If we assign 
> randomly, only checking that the santa is not from the same family for 
> each assignment, we can get:
> 
>   A -> B
>   B -> A
> 
> Now we have an impossible situation, for C cannot be his own santa.

I see! :) Nothing trivial here.

I'll try to understand your analysis.

Thanks.