Here’s Question #19 from the Google Labs Marketing Test:
“‘Tis known in refined company, that choosing K things out of N can be done in ways as many as choosing N minus K from N: I pick K, you the remaining.
Find though a cooler bijection, where you show a knack uncanny, of making your choises contain all K of mine. Oh, for pedantry: let K be no more than half N.”
I had two reactions to this question, in order:
Reaction #1) If any dungeons-and-dragons-playing, Society for Creative Anachronism-attending, faux-medieval geekboy ever asks me an interview question phrased like this, he’d better be wearing some really complicated leggings and accompanying himself on the lute as he speaks, or I will fall deeply and sinfully into the state known to medieval theologians as “wrath”. (I might also regretfully conclude that the corporate culture was not for me.)
Reaction #2) Hmm, now how would you do that? (Semi-spoilers follow.)
Here’s a sketch of solution that I think works, though I’m not happy with it:
To translate our earnest court jester’s question, we’re looking for a one-to-one mapping from subsets of size K to subsets of size N-K, where N is the size of the set, K
Tim Converse 