Golf Tournament

Can one of you geniuses help me with a real-world problem?

Eight of us are soon going to Scotland to play golf for a week or so. How many rounds do we need to play to insure that each player plays in the same group with every other player exactly the same number of times during the trip? [note: a "group" on the golf course is 2,3, or 4 players].

My brother is considering going (which would make 9 of us). Same question. A general formula would help for the following year's trip, as the group seems to be getting bigger each year.

If one of you will solve this for me, I can spend more time practicing my chip shots before we go!

Originally posted by camilli
Can one of you geniuses help me with a real-world problem?

Eight of us are soon going to Scotland to play golf for a week or so. How many rounds do we need to play to insure that each player plays in the same group with every other player exactly the same number of times during the trip? [note: a "group" on the golf course is 2,3, or 4 players].

My ...[text shortened]... e of you will solve this for me, I can spend more time practicing my chip shots before we go!

Originally posted by PBE6
Let:

N = number of players in total
G = size of each group

Then there are N!/(G!*(N-G)!) or "N choose G" games to be played in total. Each player will participate in (N-1) choose (G-1) of those games. So, if 8 people play in foursomes, you will need to play 8 choose 4 or 70 games total, with each player playing 35 of those games. If your brother plays ...[text shortened]... tal, with each player playing 56 of those games.

I hope you bring your traveler's cheques.

I'll try a different way of looking at it...

n players, group size is g, r is the number of rounds. If we keep to a simple case where g divides into n exactly:

In any particular group each player effectively plays (g - 1) individual matches. So r(g - 1) matches in total. If you want each player to play each other exactly the same number of times, then we need r(g - 1) to be a multiple of (n - 1).

So, r = LCM(n - 1, g - 1)/(g - 1)

(This doesn't prove a solution exists, it just gives a way of eliminating some that definitely won't).

So with 8 players in 2 foursomes, we need 3r to be a multiple of 7. The minimum value of r that will do that is 7 - which matches your solution.

With 9 players we'd have to play threesomes. 2r is a multiple of 8. Which suggests you can do it in four rounds, with everyone playing each other once (and a little hand-calculation shows this is possible). Or you can have 8 rounds, 12 rounds, etc.

If you have a group size that doesn't divide the total number - I might have a go at that later!

OK, here's the extension. If you have group sizes g_i:

Number of individual matches in a group is g_i(g_i - 1)/2

Total number of individual matches = r.SUM[g_i(g_i - 1)/2]
But also, total number of individual matches is a multiple of n(n - 1)/2

So we need r.SUM[g_i(g_i - 1)] is a multiple of n(n - 1)

(This reduces to the same as before if g_i = g)

Let's say you decide to divide your 8 into groups of 3, 3, 2

=> 14r is a multiple of 56, which suggests it might be possible in 4 rounds.

And here's confirmation that it is:

ABC DEF GH
ADG BEH CF
AFH CEG BD
BFG CDH AE

Oh, and here's your 9 player, 4 round, all play all once:

ABC DEF GHI
ADG BEH CFI
AEI BFG CDH
AFH BDI CEG

Originally posted by mtthw
OK, here's the extension. If you have group sizes g_i:

Number of individual matches in a group is g_i(g_i - 1)/2

Total number of individual matches = r.SUM[g_i(g_i - 1)/2]
But also, total number of individual matches is a multiple of n(n - 1)/2

So we need r.SUM[g_i(g_i - 1)] is a multiple of n(n - 1)

(This reduces to the same as before if g_i = g ...[text shortened]... nds.

And here's confirmation that it is:

ABC DEF GH
ADG BEH CF
AFH CEG BD
BFG CDH AE