I got lots of responses to my challenge problem last week. Thanks for playing! I was going to call this post "Nerdsnipe challenge!: postmortem", but as it turns out, this won't be the end of it.
I claimed that the problem came up in real life, but that depends on what you want to count as "real". It came up while I was working with the folks at Studio Cypher to design a cooperative puzzle game for the InWIC conference next weekend. I don't want to give away any details about the game, since it's supposed to be a surprise for the InWIC attendees, but hopefully it won't be too enormous of a spoiler for me to say that the first part of the game involves...*drumroll*...dividing players up into teams! We decided that for this game, the ideal team size was 5, so that meant dividing the 136 players into 24 teams of 5, plus 4 teams of 4, for a total of 28 teams. (Exercise for the reader: if 5 is the ideal team size and also a hard limit on team size, prove or disprove that this is the optimal way to divide up 136 players.)
As part of the team creation stage, we had the idea of having players match questions up with answers. We could have come up with one question/answer pair for each team and then given each player just one question card or answer card, but coming up with 28 question/answer pairs would have been too much work for us as game designers. (The question/answer pairs are, in fact, beautifully crafted brainteaser puzzles that the Studio Cypher folks have put a lot of time into.) The advantage of giving players two cards each is a combinatorial reduction in the amount of question/answer creation that the game designers have to do: we only have to come up with 8 question/answer pairs. (We could have saved even more work by giving each player three or more cards, but we figured that then, things would get annoying for the players! After all, the team-creation stuff is all just setup so that the *real* fun can begin.)
So, although I didn't quite say so in my post last Tuesday, one of the things I really wanted to know was whether the procedure I outlined there (which was what I thought Studio Cypher was proposing) would actually make sense as a way to divide players into teams of the size we wanted. I thought that it was likely to result in teams that were were pretty far off from the ideal size of 5, and that turns out to be correct. But it wasn't Studio Cypher's fault -- I had misunderstood what they were proposing. In fact, they didn't intend there to be any randomness involved in the pairing of question and answer cards. Instead, they figured that we'd deliberately pair the cards up before handing them out to the players in a way that would result in groups that were as evenly-sized as possible. It's interesting to think about how that might work: as an anonymous commenter pointed out, there are 56 valid question-answer pairings (question A can go with answers B-H, question B can go with answer A and answers C-H, and so on). Let's use the notation 'X/Y' to mean a pairing of question X and answer Y. If we hand the 56 valid pairings out to 56 players, they'll form groups of 2: no two players will have the same pairing, but A/B groups up with B/A, and so on. If we generate two sets of the 56 pairings -- that is, 112 pairings -- and hand them out to 112 players, now there will be two players with each pairing and two players with the corresponding pairing, so we'll get groups of 4. (And there will be 28 groups, since 112/4 = 28.) But we need 136 pairings for the 136 players. What should the additional 24 pairings be?
We could start generating a third set of 56 pairings, and just stop when we have 24 -- this is more or less what the anonymous commenter suggested. But we have to be careful here! Let's use the notation 'X/Y-Y/X' for the group that contains all of the X/Y pairs as well as the Y/X pairs. Suppose we generate the pairings in the following order, which seems pretty reasonable:
A/B, A/C, A/D, A/E, A/F, A/G, A/H (7 pairings)
B/A, B/C, B/D, B/E, B/F, B/G, B/H (7 pairings)
C/A, C/B, C/D, C/E, C/F, C/G, C/H (7 pairings)
D/A, D/B, D/C (3 pairings)
Recall that our groups already had 4 players each -- for instance, the A/B-B/A group already had 4 players in it. We've now added *two* more players to that group: an A/B and a B/A. In fact, if my calculations are right, using this strategy, we end up adding players to the existing groups as follows:
2 to A/B-B/A
2 to A/C-C/A
2 to A/D-D/A
1 to A/E-E/A
1 to A/F-F/A
1 to A/G-G/A
1 to A/H-H/A
2 to B/C-C/B
2 to B/D-D/B
1 to B/E-E/B
1 to B/F-F/B
1 to B/G-G/B
1 to B/H-H/B
2 to C/D-D/C
1 to C/E-E/C
1 to C/F-F/C
1 to C/G-G/C
1 to C/H-H/C
and *none* to D/E-E/D, or any of the rest! So we end up with 6 groups of 6, 12 groups of 5, and 10 groups of 4. This violates the hard limit of 5 on group size, and the variation in group size is bigger than it needs to be.
To avoid this problem, we need to generate at least the last set of pairings in a different way. This would work:
A/B, A/C, A/D, A/E, A/F, A/G, A/H (7 pairings)
B/C, B/D, B/E, B/F, B/G, B/H (6 pairings)
C/D, C/E, C/F, C/G, C/H (5 pairings)
D/E, D/F, D/G, D/H (4 pairings)
E/F, E/G (2 pairings)
Then, finally, we're adding 1 player each to 24 of the groups, and leaving the remaining groups alone. We're left with 24 groups of 5 and 4 groups of 4, just like we wanted. The average group size is therefore 136/28, or about 4.85.
Now, as for the question I asked a week ago, about the average group size if cards are given out randomly: My original back-of-envelope answer for average group size, which I think is similar in spirit if not in letter to what Akiva came up with, went like this: Suppose I have question A and answer B. There are 16 other people who've drawn question A, and each of them has an answer card. There are 7 possible answer cards (B through H) that they might have, so for each person, there's a 1 in 7 chance that the answer card they have is B. 1/7 * 16 is about 2.3, so an average of 2.3 of those people will end up in my group. Likewise, there are 17 people out there who've drawn answer A, and a 1 in 7 chance that they have question B. 1/7 * 17 is about 2.4, so an average of 2.4 of them will end up in my group. Adding myself, there's an average group size of 5.7.
**But this answer is wrong for at least two reasons**, which I'll write about in a future post!
Whenever I post one of these challenges, it's exciting to see the diversity of approaches that people take in responding to them. The comments are always fun to read (despite, or perhaps because of, their inevitable degeneration into dick jokes). But as much as I might have nerdsniped some of you with this, the person I nerdsniped the hardest was myself. I've been thinking about this strange little problem nonstop for a week. Incidentally, we decided that the paired puzzle cards, whether pre-paired or not, would be too much work and too error-prone, and we came up with an entirely different way to get players into teams of appropriate sizes. So I'm not actually giving away anything about the game by posting all of this, plus, we're no longer plodding through the dismal realm of Applicable to a Real Situation and, instead, are frolicking through the grassy meadow of Just For The Hell Of It. Hooray! |