Comments: 
 From: pmb 20120201 04:22 pm (UTC)
Simulation says  (Link)

I think the question and answers dichotomy is a red herring. I am pretty sure the situation you describe is the same as "there are 8 different cards, and 34 copies of each, everyone gets two nonequal cards." It seems like we might be requiring the dealer to have godlike (NPhard solving) abilities. Time for a simulation  http://pastie.org/3296593About half the time, the deal does wrong, and my simulation crashes with Traceback (most recent call last):
File "deal.py", line 8, in
l1, l2 = random.sample(cards, 2)
File "/usr/lib/python3.2/random.py", line 303, in sample
raise ValueError("Sample larger than population")
ValueError: Sample larger than population
But the other half of the time, we get output like: (2, 5) 9
(4, 6) 8
(3, 5) 7
(1, 7) 7
(0, 7) 7
(0, 3) 7
(3, 4) 6
(2, 6) 6
(1, 2) 6
(6, 7) 5
(5, 7) 5
(4, 7) 5
(1, 5) 5
(0, 2) 5
(0, 1) 5
(3, 7) 4
(3, 6) 4
(2, 4) 4
(1, 6) 4
(1, 4) 4
(0, 6) 4
(0, 4) 4
(5, 6) 3
(4, 5) 3
(2, 3) 3
(1, 3) 3
(0, 5) 2
(2, 7) 1 I have seen groups as small as size 1, and as large as 11.
 From: pmb 20120201 04:33 pm (UTC)
Re: Simulation says  (Link)

Just in case my intuition was wrong, because I kept thinking it might be, I rewrote this to exactly simulate the question you are asking. http://pastie.org/3296662Again, about half the time it doesn't work because the deal goes wrong. When it does work, however, its output is the same as above. I have seen groups as small as 1, and as large as 12
It seems like we might be requiring the dealer to have godlike (NPhard solving) abilities.
I don't see why. Suppose the dealer deals the 136 question cards first. They have to remember which card was dealt to which player (which takes linear space in the number of players). Then, to deal the answer cards, before dealing to a player, they can just look up what question card that player has, which would take constant time, and then remove the 17 matching answer cards from the deck before dealing that player an answer card (which would take linear time in the number of cards). So, dealing all the answer cards might be kinda slow (dealing each one takes linear time, so dealing them all takes quadratic time), but totally still polynomial time.
(But I'm glossing over the time complexity of, e.g., shuffling the deck before dealing. Is that where the 'N' is coming from?)
 From: pmb 20120205 03:43 pm (UTC)
Re: Simulation says  (Link)

I always model things as a graph, and so, if you think of a cardcombo dealt to a person as being an edge in a degree34 hypergraph, then the deal needs to construct a random regular degree34 hypergraph. Constructing graphs with a given degree distribution, particularly a given random degree distribution, is a problem in NP, but does not have a known polytime algorithm for all graph sizes ad degrees (it may be NPC, I forget).
So, if you had fewer people, or more cards, then it is quite possible that almost all of the deals would fail, instead of merely half, like they do in simulation.
What does it mean for a deal to fail? If a failed deal is one in which someone gets two cards that aren't supposed to go together, why isn't that fixable using a twostage dealing strategy like the one I described?
 From: pmb 20120205 04:34 pm (UTC)
Re: Simulation says  (Link)

You can end in the situation where you have only answers to A left to give out (you have been dealing randomly, so this is quite possible) and at least one of the people who has not yet received a card has an A question.
Basically, "the dealer makes sure that nobody gets a question and answer card that go with each other" is an operation that is surprisingly tricky. How do they do that? After they have done that, how can they be sure that their method of ensuring this property holds has kept it so that the resulting distribution of cards is a uniform sample of the possibilities?
Oops! Yeah, Alex just pointed out the flaw in my algorithm: you can back yourself into a corner. You already know this, but for the benefit of anyone else reading, here's a simple case: Suppose there are only 3 players. You deal the question cards first, and they get question cards A, B, and C, respectively. Now it's time to deal the answer cards. You remove answer card A from the deck and randomly deal one of B or C to player 1. Let's say it's B. Now, you put answer card A back in, take out answer card B, and randomly deal one of A or C to player 2. Let's say it's A. Now you're left with answer card C, but player 3 has question card C, so you're backed into a corner. (You can backtrack, but I think that that would mean crossing over into exponential time.)
I think it's cool how everyone is applying their own favorite hammer to this problem. Alex sees it as a constraint satisfaction problem, and from that angle, it's easier for me to see the NPness.
Edited at 20120205 05:16 pm (UTC)
 From: pmb 20120205 05:17 pm (UTC)
Re: Simulation says  (Link)

NPness! Tee hee hee...
my sense of humor should be more mature, but sometimes I fail my saving roll against immature homonyms  