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.)


From: aleffert
2012-02-01 03:46 am (UTC)
Well here is an approximation and it might be right, but I am pretty confident I am making invalid independence assumptions.

So, for a given player we can find the expected number that match with them = E(qaMatches) + E(aqMatches)

E(qaMatches) = E(aqMatches) since it's symmetric, so let's just do one and call it E(matches).

E[matches] = P(topMatches) * P(bottomMatches) * numberOfOtherPlayers = 1/8 * 1/8 * 135 = 2.11

so overall expectation is 4.22, which sounds vaguely plausible.

I think you should be able to have a group of size 1, but the explanation is too long to fit in the margin of this comment. And the largest group is worst case gonna be 34 (make all people with question A get answer B and vice versa).
(Reply) (Thread)
From: aleffert
2012-02-01 04:19 am (UTC)
Oh I guess P(topMatches) and P(bottomMatches) aren't actually 1/8, because we have to take ourselves out, so it's like 16 / 136, but in the flipped case, it's actually one bigger since we're taking out a nonmatched card.
(Reply) (Parent) (Thread)
[User Picture]From: conform
2012-02-01 04:51 am (UTC)
Group of size 1 is pretty easy to construct. Start with everybody sorted into 4 groups: AB, CD, EF, GH. Take one member each from the first three groups: {AB, CD, EF}, and have them each pass their answer cards to the right. Now you have one member each for groups AF, CB, and ED.
(Reply) (Parent) (Thread)