Ken's POTW


Nine Rounds
Nine friends decide to play golf over nine weeks. Each week, two foursomes will play on different courses, and one of the nine friends will stay home. At the end of nine weeks, each person will have played golf eight times, and will have played with three playing partners each time, for a total of 24 playing partners. Can you build a schedule so that each person will have each of the other people as a playing partner exactly three times? Or, can you prove it can't be done?

Source: Jon Abraham's friend's mother-in-law's golfing group.

Solution:
I have received three so far. They are attached, followed by my solution.
From Jon Abraham, the puzzle poser. I gave him a hint toward the solution I found (below) and he used a computer program to do the rest: 
Well, given your hint, I came up with a solution!!!!!  Thank you!

Here it is:     2345.6789       1 sits out
                1367.4589       2 sits out
                1289.4567       3 sits out
                1568.2379       4 sits out
                1479.2368       5 sits out
                1359.2478       6 sits out
                1348.2569       7 sits out
                1257.3469       8 sits out
                1246.3578       9 sits out

Once I assumed that no "trio" was used more than once, it became very
easy.  My solution is a computerized trial-and-error approach, certainly
nothing elegant.  I suspect there are many more solutions (for instance,
if you just swap every "1" in the above solution with every "2", I think
you get a different solution).  How many more?  I'll give that some
thought.  Thanks again for bringing this very frustrating puzzle to
closure for me!
From Hayim Even Zoahr: 
My solution is simply a result of some trials. Therefore I can't give you
anything but my way of thinking:
        
First of all, I looked at the three first rounds (1-3, that means:
1-3 are the player that don't play in these rounds). If I can make
a "pair" in those rounds (like 8 and 9 that are together ),
in the other rounds that include them both (4-7) they must
be separate. This gives me much less choices, so it is 
easier to find the right one.
So I made the pairs 4-5, 6-7, 8-9 and every pair was one round 
of the three with the rest (2 from 1-2-3).
Now come the 6 other rounds. Every one consists of five players
from the 4-5-6-7-8-9.
I must put them in 2/3 separation, for the 1/4 make the 1-2-3
players always together. 
The 4-5-6-7-8-9 can make 8 different groups of 3:
4-6-8   4-6-9   4-7-8   4-7-9   5-6-8   5-6-9   5-7-8   5-7-9
I need only 6 so I don't take 4-6-8 and 5-7-9 that consist of 
all the six numbers. (why? only a trial and it sounds logical)
From now I stop thinking and keep trying till the end.
(I believe there is more then one solution but they are
all the same if you replace the numbers.)
                                                        Hayim

        ps - I like your site.  [Thanks again. - KD]

> Here is a possible solution:
>
> (1) 2345 , 6789
> (2) 1389 , 4567
> (3) 1267 , 4589
> (4) 2379 , 1568
> (5) 2368 , 1479
> (6) 1259 , 3478
> (7) 1248 , 3569
> (8) 1357 , 2469
> (9) 1346 , 2578
>                                               Hayim Even Zohar
From Yaacov Weiss: 
out     game1   game2
1       2345    6789
2       8945    6731
3       8921    6745
4       8651    9723
5       8623    9741
6       8742    9513
7       8413    9652
8       7512    9643
9       8753    6412
Ken Duisenberg's Answer: 
Answer:
abcd    efgh    i
abef    dghi    c
abgh    cefi    d
acfg    bdei    h
achi    bdfg    e
adeh    bcgi    f
adfi    bceh    g
aegi    cdfh    b
bfhi    cdeg    a
Solution: I labeled the players a-i.
There are (9 choose 2) = 36 pairs.
There are (4 choose 2)*2*9 = 108 pairs in the games, just right.
There are (9 choose 3) = 84 trios possible.
There are (4 choose 3)*2*9 = 72 trios in the games.

I assumed that no trio would play together more than once. I don't know if this is a necessary condition, but it led to a solution. [I later (8/18/97) received a note from Craig Gentry saying this is a necessary condition - see below.] Each pair will play in three foursomes, thus playing with 6 other players. So for each pair, there are 6 trios, but this counts each trio three times, for a total of 72 unique trios playing.

Given the above knowledge, I started working out the possibilities. The fact that only unique trios would play led to a systematic solution: 
    A    B  Out
1. abcd efgh i
2. ab.. .... .
3. ab.. .... .
4. ac.. .... .
5. ac.. .... .
6. ad.. .... .
7. ad.. .... .
8. ae.i .... .
9. b... .... a
First assume the initial two foursomes. Then, since we know we need person 'a' to play with b, c, and d two more times each, we just place them. In a's eighth game, he can't play with any of bcd, so he must play with members from the first group B (I chose e). To avoid a repeated trio in that game, another member of that game must be 'i'. In the ninth games, 'a' sits out. 
    A    B  Out
1. abcd efgh i
2. abef ...i .
3. abgh ...i .
4. ac.. ...i .
5. achi .... .
6. ad.. ...i .
7. adfi .... .
8. aegi .... .
9. b... .... a
'a' must play with 'i' two more times, but the unique-trios rule means with unique other players. I chose c and d (rounds 5 and 7). Doing this placed 'i' in all the other B-groups in rounds 1-8. Since 'i' is not in the A group for rounds 2 and 3, the B1 players are, so I placed 'ef' and 'gh'. Since 'aef' and 'agh' played in A2 and A3, the remaining player in A8 is either g or h. Since they were still interchangeable, I chose 'g'. This left the remaining players in A5 and A7 as 'f' and 'h'. I chose to put 'f' in A7 and 'h' in A5. 
    A    B  Out Remaining
1. abcd efgh i
2. abef ...i .  c d g h
3. abgh ...i .  c d e f
4. acfg b..i .  d e h
5. achi .... .  b d e f g
6. adeh b..i .  c f g
7. adfi .... .  b c e g h
8. aegi .... .  b c d f h
9. b..i .... a  c d e f g h
Since the following were used: A8:aeg, A2:aef, A3:agh, A5:ach; the remaining players in A4 could only be 'fg'. The remaining players in A6 could only be 'eh'.
Since b and i must play together three times, b plays in B4 and B6, and i plays in A9. The remainging players are shown. 
    A    B  Out Remaining
1. abcd efgh i
2. abef dg.i .  c h
3. abgh ce.i .  d f
4. acfg b..i .  d e h
5. achi dg.. .  b e f
6. adeh b..i .  c f g
7. adfi ce.. .  b g h
8. aegi fh.. .  b c d
9. bfhi cdeg a
Since 'c' and 'e' must play together three times, they must play in B3 and B7 (and in round 9.) Since 'd' and 'g' must play together, they must play in B2 and B5 (and in round 9). Since 'f' and 'h' must play together two more times, they must play in B8 (and in round 9.)

Since B2 and B3 already used trios 'dgi' and 'cei', 'dg' and 'ce' can't be placed in A9, so 'fh' is in A9. 
    A    B  Out
1. abcd efgh i
2. abef dghi c
3. abgh cefi d
4. acfg bdei h
5. achi bdgf e
6. adeh bcgi f
7. adfi bceh g
8. aegi cdfh b
9. bfhi cdeg a
Since 'bfh' is used in A9, 'b' is out of B8 and in B5 and B7. Since 'bfi' is used in A9, f is out of B6 and in B3 and B5. Since 'bhi' is used in A9, h is out of B4 and is in B2 and B7.

Simple checking will show that this solution meets the requirements.

Craig Gentry sent this follow-up:

Your intuition was right - a given trio can play together only once. Consider the trio A, B, and C. There are 6 rounds, say the first six rounds, in which players A, B and C all play.

If they all play together in each of the first three rounds, then, because AB and AC have both gone 3 times already, A cannot play with either B or C in subsequent rounds. But this means that B and C must play together in the non-A groups. B and C therefore end up playing together more than 3 times.

If A, B and C all play together in each of the first 2 rounds, then there must be exactly one more round, say round 3, in which A and B play together and exactly one more round, say round 4, in which A and C play together. Because A cannot play with either B or C in rounds 5 or 6, B and C must play together in these rounds. B and C therefore play at least 4 times together.

Conclusion - no threesome can play more than one round together. -Craig Gentry

Mail to Ken