Log in

No account? Create an account
Nerdsnipe challenge! - Lindsey Kuper — LiveJournal [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Nerdsnipe challenge! [Jan. 31st, 2012|10:17 pm]
Lindsey Kuper

Each player in a game is dealt two cards: one question card chosen from a set of 8 questions, and one answer card chosen from a set of 8 answers. There are 17 copies of each card, so there are a total of 8 * 17 * 2 = 272 cards. Conveniently, there are 136 players, so there are exactly enough cards for everyone to get one question card and one answer card.

The question and answer cards correspond to each other (question A goes with answer A, question B with answer B, and so on), but the dealer makes sure that nobody gets a question and answer card that go with each other. That is, if I happen to have the card for question A, I won't also have the card for answer A. Instead, I'll have one of answer cards B through H. (We can assume that the cards are dealt randomly, except for the caveat that nobody ever gets a corresponding pair of question and answer.)

Once cards are dealt, players have to find and form groups with all the other players for whom one of the following is true:

  1. the other player has the same question and same answer.
  2. the other player has the corresponding question and corresponding answer.

For example, if I have question A and answer D, I should group up with any players I find who also have question A and answer D, and with any players I find who have answer A and question D. (But I don't group up with players who have, say, question A and answer B, or, say, answer A and question H.)

Players can talk to each other, show their cards freely, and so on. (Let's assume that players don't lie about their cards, withhold information from each other, or exchange cards.)

What I want to know is: how big are the groups that players form? And if not all the groups are the same size, how big are the smallest and largest groups?

This is actually a problem that arose in real life! But I won't tell how it came up until I start seeing your solutions. Go! Estimates are fine; precise solutions are also welcomed. (And feel free to ask clarifying questions; it's possible that I left out something.)


[User Picture]From: lindseykuper
2012-02-05 05:11 pm (UTC)

Re: Simulation says

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 NP-ness.

Edited at 2012-02-05 05:16 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2012-02-05 05:17 pm (UTC)

Re: Simulation says

NP-ness! Tee hee hee...

my sense of humor should be more mature, but sometimes I fail my saving roll against immature homonyms
(Reply) (Parent) (Thread)