9
$\begingroup$

I am trying to put together a Munchkin game tournament where I am assuming I will have 16 people coming to my tournament. As part of that, I want to have as many games as possible where people are not playing against the same player twice. (So, every combination is unique.)

I can easily come up with these groups for three rounds of the tournament. Is it possible to do more? If so, can you point me in the right direction? Unfortunately, I think I am confusing my combinations and permutations and it's leaving me stumped.

  • 0
    To make sure, it seems that 4 people play Munchkin at a time?2011-06-08
  • 0
    @mixedmath @DJC - 4 players per game, 4 games per round. (All 16 players should be playing at the same time.)2011-06-08
  • 0
    I'm sure my explicit answer can fixed, but Gerry's answer is better.2011-06-08

4 Answers 4

12

Identify the players with elements of ${\bf Z}_2^4$ (that is, with ordered 4-tuples of zeros and ones, where addition of 4-tuples is done component-wise and using mod $2$ arithmetic). There are $5$ subgroups of $4$ elements each such that no two subgroups have any element in common other than $(0,0,0,0)$. Each subgroup, together with its cosets, gives you one round of your tournament, so this is a way to go $5$ rounds.

  • 0
    @Gerry: I think that's very pretty. How did you do that?2011-06-08
  • 0
    @Gerry - I apologize for being a bit of a math noob...I'm not sure I understand the explanation.2011-06-08
  • 3
    Wow, this is incredibly slick! +12011-06-08
  • 0
    @JasCav: I'm working on writing up the brackets that Gerry's method gives you. Stay tuned!2011-06-08
  • 0
    If I get it right, a set of subgroups is (each with 0000 added): 1000,0100,1100; 0010,0001,0011; 1001,0110,1111; 1010,1101,0111; and 0101,1011,1110. Taking the first, the first round has 0000,1000,0100,1100; 0001,1001,0101,1101; 0010,1010,0110,1110; 0011,1011,0111,1111. You take a subgroup as one game, then add a player not yet playing to each element of the subgroup to get another game in that round, repeat twice more adding a player to the subgroup, and there you are.2011-06-08
  • 2
    A way of realizing this is that the five subgroups are the 5 lines (4 points on each) thru the origin in the 2-dimensional vector space over the finite field $GF(4)$.2011-06-08
  • 0
    @Jyrki, yes, I thought about presenting it that way, it's even slicker than the way I chose, but I thought it might be easier explaining ${\bf Z}_2^4$ than explaining the field of four elements.2011-06-08
  • 0
    @Gerry, I understand and agree with your decision. You wanted to keep it as simple as possible and not introduce any more machinery than is absolutely necessary.2011-06-08
8

This is nothing more than Gerry's answer made explicit. (I apologize if I've made any mistakes or typos... Any mistakes are mine, not Gerry's!)

Label your 16 players with the letters A,B, ..., P. Then your rounds should have the following games of 4 players:

Round 1 {A,B,C,D} {E,F,G,H} {I,J,K,L} {M,N,O,P}

Round 2 {A,E,I,M} {B,F,J,N} {C,G,K,O} {D,H,L,P}

Round 3 {A,F,K,P} {B,E,L,O} {C,H,I,N} {D,G,J,M}

Round 4 {A,J,O,H} {B,I,P,G} {C,L,M,F} {D,K,N,E}

Round 5 {A,G,L,N} {B,H,K,M} {C,E,J,P} {D,F,I,O}

4

These kinds of problems can be difficult; see the discussion Math Games: Social Golfer Problem about scheduling threesomes as well as foursomes playing concurrently, a topic called resolvable Steiner systems. The case of 16 people in foursomes over 5 days is shown (both as a listing of 4-sets and as a strange diagram) in nearly the middle of that page/article.

Day 1: ABCD EFGH IJKL MNOP Day 2: AEIM BFJN CGKO DHLP Day 3: AFKP BELO CHIN DGJM Day 4: AGLN BHKM CEJP DFIO Day 5: AHJO BGIP CFLM DEKN 
  • 1
    Interesting that this solution matches Gerry's/Jeff's with just days 4 and 5 swapped. No relabeling required.2011-06-08
0

See Creating combinations that have no more than one intersecting element.