?

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: 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)
[User Picture]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)
[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)
[User Picture]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)
[User Picture]From: cos
2012-02-01 06:55 am (UTC)
Would it make any difference if there were no question and answer cards, just 16 different cards (with one of 16 symbols or words or colors or numbers or anything), and you were guaranteed not to get two of the same, and had to group with everyone who had the same two cards as you have? I'm trying to convince myself that there's a meaningful difference between this and your scenario, but haven't managed to yet.
(Reply) (Thread)
(Deleted comment)
From: (Anonymous)
2012-02-01 03:35 pm (UTC)

Example

"For example, if I have question A and answer D, ... I don't group up with players who have ..., say, answer A and answer H."

How could a player have answer A and answer H? I thought each player was supposed to get one question card and one answer card.
(Reply) (Thread)
[User Picture]From: lindseykuper
2012-02-01 03:45 pm (UTC)

Re: Example

Sorry, that was a typo. I meant to say "answer A and question H". Fixed!
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2012-02-01 04:22 pm (UTC)

Simulation says

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 non-equal cards."

It seems like we might be requiring the dealer to have godlike (NP-hard solving) abilities. Time for a simulation - http://pastie.org/3296593

About 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.
(Reply) (Thread)
[User Picture]From: pmb
2012-02-01 04:33 pm (UTC)

Re: Simulation says

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/3296662

Again, 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
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2012-02-05 04:36 am (UTC)

Re: Simulation says

It seems like we might be requiring the dealer to have godlike (NP-hard 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?)
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2012-02-05 03:43 pm (UTC)

Re: Simulation says

I always model things as a graph, and so, if you think of a card-combo dealt to a person as being an edge in a degree-34 hypergraph, then the deal needs to construct a random regular degree-34 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 poly-time 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.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2012-02-05 04:10 pm (UTC)

Re: Simulation says

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 two-stage dealing strategy like the one I described?
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2012-02-05 04:34 pm (UTC)

Re: Simulation says

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?
(Reply) (Parent) (Thread)
[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)
From: (Anonymous)
2012-02-01 06:41 pm (UTC)
My solution is now up at

http://www.cs.grinnell.edu/~stone/misc/nerdsnipe.rkt

Short answer: The mean number
of other members in your group is
about 4.6, so the mean group size
is about 5.6.
(Reply) (Thread)
From: (Anonymous)
2012-02-01 08:51 pm (UTC)
'course, if you wanted to distribute the combinations equally you could just N print cards with each distinct question-answer combo (N*56 of them) and throw out the extras. Each group would end up being 4 to 5 people.
(Reply) (Thread)