Thu, 8 Jan 2004 14:57:36 -0500 (EST) Dan Hoey <Hoey@aic.nrl.navy.mil> Thu, 08 Jan 2004 11:18:25 -0800 Marc LeBrun <mlb@fxpt.com> Can you think of a way to generate secret derangements that's about as natural as drawing names from a hat? Thu, 08 Jan 2004 14:44:12 EST Michael B Greenwald <mbgreen@central.cis.upenn.edu> Drawing names from two hats? Split the names randomly, partitioning the group into reds and greens.... If the population is odd, Oops... not a big deal, just needs a minor tweak. The red people (the smaller group, always even) choose first. In the odd case one name remains in the green hat. Reveal it, add it to the red hat, and have that green person choose first, redrawing to avoid self-assignment. At this point there are an even number of people left, and all of the names in the hat belong to people who have already drawn (there are floor(n/2) names in the hat and ceil(n/2) people have already drawn). This has the advantage of being simpler and retaining a tiny bit more mystery than your scheme (for small n). (Incidentally, the spirit of this problem (i.e. keep this as "natural" as drawing names from a hat and not using "computation") seems UN-natural to me. PDA's are common enough to assume that some computation device (cell phone?) will be present.) partition the group into [n/3] reds, [(n+1)/3] greens, and [(n+2)/3] yellows. Yellows put their names into the red hat, with excess into the green; reds put their names into the green hat, with excess into the yellow; greens put their names into the yellow hat. Then each person draws from their own color of hat. That unfortunately removes the mystery from trios and the red member of quintets. And it spoils the seasonal color scheme. Dan