Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$12$ gentlemen wish to play $7$ rounds of golf. They want to split into $3$ groups of $4$ and play a different group each time with as much variety as possible without playing the same individuals repetitively. What formula would they use to accomplish this?

share|improve this question
2  
Since you are new, I want to give you some advice about the site: To get the best possible answers, you should explain what your thoughts on the problem are so far. That way, people won't tell you things you already know, and they can write answers at an appropriate level; also, people tend to be more willing to help you if you show that you've tried the problem yourself. If this is homework, please add the [homework] tag; people will still help, so don't worry. –  Zev Chonoles Mar 30 '13 at 23:36
    
I think you'll need to quantify "with as much variety as possible" to make this a well-defined mathematical problem. –  joriki Mar 31 '13 at 0:07
    
I had the question wrong. The 12 golfers want to split into 3 groups of 4. Here is what I have so far: –  Carey Dodson Mar 31 '13 at 21:03
    
1,2,3,4| 5,6,7,8| 9,10,11,12|| 1,5,9,10| 2,6,11,12| 3,4,7,8|| 1,5,8,12| 2,7,10,11| 3,4,6,9|| 1,7,9,11| 2,4,6,8| 3,5,10,12|| 1,4,6,10| 2,3,5,7| 8,9,11,12|| 1,3,7,12| 2,8,9,12| 4,5,6,10|| 1,2,8,11| 3,5,6,12| 4,7,9,10|| –  Carey Dodson Mar 31 '13 at 21:04
    
I guess instead of "with as much variety as possible" I should say with the fewest amount of people repeating in groups of four. –  Carey Dodson Mar 31 '13 at 21:08

1 Answer 1

This question asks to find a edge covering of the complete graph $K_{12}$ using $7$ copies of $3K_4:=K_4 \cup K_4 \cup K_4$. There are $\binom{12}{2}=66$ edges in $K_{12}$ and $7 \times 3 \times 6=126$ edges in the $7$ copies of $3K_4$.

The above suggests the "best possible" might be when $6$ edges occur once and the other $60$ occur twice. But this is not actually achievable as we will now explain. Let $Z$ be one copy of $3K_4$ and $H$ be some induced $K_4$ subgraph in a copy of $3K_4$ other than $Z$. Then $Z$ and $H$ share at least one edge (by the pigeonhole principle). Thus, if $Y$ and $Z$ are two distinct copies of $3K_4$, then they must have at least $3$ edges in common. So there are at least $3 \times \binom{7}{2}=63$ duplicated edge-pairs.

This means the best possible is to have $9$ edges that occur once, $3$ edges to occur $3$ times and the remaining $54$ edges to occur twice (giving $54 \binom{2}{2}+3\binom{3}{2}=63$ duplicated edge-pairs).

The example below achieves this (found by a computer search in GAP).

[ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] ],
[ [ 1, 2, 5, 9 ], [ 3, 6, 7, 10 ], [ 4, 8, 11, 12 ] ],
[ [ 1, 2, 6, 11 ], [ 3, 5, 8, 12 ], [ 4, 7, 9, 10 ] ],
[ [ 1, 3, 7, 11 ], [ 2, 5, 10, 12 ], [ 4, 6, 8, 9 ] ],
[ [ 1, 4, 5, 10 ], [ 2, 7, 8, 11 ], [ 3, 6, 9, 12 ] ],
[ [ 1, 6, 8, 10 ], [ 2, 4, 7, 12 ], [ 3, 5, 9, 11 ] ], 
[ [ 1, 7, 9, 12 ], [ 2, 3, 8, 10 ], [ 4, 5, 6, 11 ] ]

In the example you give in the comments, the pair $\{4,6\}$ occurs $4$ times, and the pairs $\{3,11\}$, $\{4,11\}$, $\{4,12\}$, $\{5,12\}$ and $\{8,10\}$ don't occur at all, so it's suboptimal.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.