Re: [math-fun] Secret Santa problem
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, 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
=Dan Hoey If the population is odd, partition the group into [n/3] reds,...
I suppose more hats is progress, of a kind. Reference for large N: http://www.amazon.com/exec/obidos/tg/detail/-/039484484X But then the available derangements are further reduced.
That unfortunately removes the mystery from trios and the red member of quintets. And it spoils the seasonal color scheme.
Trios don't work in any scheme, but quintets, alas, are my driving interest. Did I mention the humanitarian dimension? Our waiter reported observing many other families arguing over their shredded place mats. A nice color scheme is gravy.
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
[My mailer seems fried, so apologies if you get this twice (or more!). It keeps claiming that it didn't deliver this mail to anyone]. 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
=Michael B Greenwald
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.
So far I follow...
Reveal it, add it to the red hat, and have that green person choose first, redrawing to avoid self-assignment.
Sorry, I'm pretty lost at this point. I think what you are describing involves, midway in the process for odd N, having a single element which has a tiny chance of picking itself, thus requiring a redraw in those rare cases. That's workable (though of course doesn't uniformly generate all derangements nor n-cycles).
(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.)
It's not the computation that I find unaesthetic so much as the intrusion of the omniscient outsider, whether it's a computer, a waiter or a guvmint key escrow officer. You may prefer to think of this as a crypto puzzle akin to an N-way public key digital signature swapfest with no central trusted server (even if it is only a PDA!<;-). But hey, maybe there's a commercial opportunity here to provide Secret Santa software for cell phones!
Thu, 08 Jan 2004 15:13:56 -0800 Marc LeBrun <mlb@fxpt.com> >=Michael B Greenwald > 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. So far I follow... > Reveal it, add it to the red > hat, and have that green person choose first, redrawing to avoid > self-assignment. Sorry, I'm pretty lost at this point. I think what you are describing involves, midway in the process for odd N, having a single element which has a tiny chance of picking itself, thus requiring a redraw in those rare cases. No, just a local redraw (i.e. the green person draws twice if the first is self assignment). You can avoid redraws by switching the order slightly and allowing a name to live outside of any hat for one draw: ... Reveal the remaining name, have the person named by that name draw from the red hat first, and *then* add the revealed name into the red hat. At that point the red hat only contains names of people who have already drawn, so self-assignment is impossible. Each person knows that their Secret Santa was one of floor(n/2) people, which works (up-to-a-point) for all n >= 4. No self assignments, no redraws. Personally, I thought a redraw preferable to a "3rd hat" [i.e. temporarily in neither hat], but preferences vary.
participants (3)
-
Dan Hoey -
Marc LeBrun -
Michael B Greenwald