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 ]

From:
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?
From:
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)
From:
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