?

Log in

No account? Create an account
Nerdsnipe challenge! - Lindsey Kuper [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.)

LinkReply

Comments:
[User Picture]From: conform
2012-02-01 03:57 am (UTC)
It seems like your grouping method (A/D groups with both A/D and D/A) means that you don't have to consider the question and answer cards as distinct: everybody gets two non-duplicating cards and matches anyone with the same two cards. Yes?

There are also 8choose2 = 28 groups, so the average group has 4.86 members.

The most members any group could have, obviously, is 34, which means the fewest groups you could have is 4. The fewest members, then that any group could have, is 0.

How often will any given group be empty? For group AB, 34 players will have an A. In order for AB to be empty, none of them can draw B as their second card. For the first A-holder, there are 7*34 cards that can be drawn, and 6*34 of them are not Bs. For the second, there 7*34 - 1 cards, and 6*34 - 1 non-Bs. So on to the last A-holder, who has a mere (6*34 - 33)/(7*34 - 33) chance. Multiply all these chances together and you have the likelihood of a group being empty.

If I keep writing, it will become very clear that I've taken discrete math and thought plenty about combinatorial math, but have never studied statistics. So I'll stop here.

Edited at 2012-02-01 03:58 am (UTC)
(Reply) (Thread)
[User Picture]From: lindseykuper
2012-02-01 04:16 am (UTC)
I've taken discrete math and thought plenty about combinatorial math, but have never studied statistics.

Same here!
(Reply) (Parent) (Thread)
From: aleffert
2012-02-02 01:50 am (UTC)
Oh I guess mine is the expectation for non empty groups and I also need to add one to include the person whose perspective I was using.
(Reply) (Parent) (Thread)