Maximum socializing on the golf course

167 views
Skip to first unread message

Bigwind777

unread,
May 27, 1998, 3:00:00 AM5/27/98
to

Please help with this problem.

I have 32 golfers, individual play.

We will golf for 16 weeks.

I want to set up the foursomes so each person only golfs
with the same person once.

How many weeks can we do this before it starts to duplicate ?
Help !!

Is it only four?
It should be eight ?
I can't figure it out and neither can anyone else.


Warwick HARVEY

unread,
Jun 4, 1998, 3:00:00 AM6/4/98
to

In sci.op-research, bigwi...@aol.com (Bigwind777) writes:

>Please help with this problem.

>I have 32 golfers, individual play.

>We will golf for 16 weeks.

>I want to set up the foursomes so each person only golfs
>with the same person once.

>How many weeks can we do this before it starts to duplicate ?

I find this a very interesting problem, in particular trying to construct
a playing schedule for a given number of weeks such that no two golfers
share a group with each other on more than one occasion.

It seems to be a generalisation of the problem of constructing a
round-robin tournament schedule, where the number players in a "game" is
more than two.

Has anybody had any experience with this kind of problem? Any ideas on
good ways to model it?

Warwick

Mark Perkins

unread,
Jun 4, 1998, 3:00:00 AM6/4/98
to Warwick HARVEY

As a first cut, there are only certain combinations of weeks and players
which have a chance. Looking at it from my point of view, I will play
with three new golfers each week, so the number of golfers in the group
has to be:
1 + 3*weeks

However, the number of golfers must be a multiple of 4 in order to make
foursomes. The pairs which satisfy these two constraints are:

weeks golfers
------ ------
1 4 (I know the solution to this one)
5 16
9 28
13 40
4n+1 12n+4 for n = 4,5,6,...

Of course, just satisfying these two constraints does not mean that a
feasible solution can be constructed.

But, we can immediately answer the original question:
* For 32 golfers there is no schedule in which a player never plays with
another twice.
* For a 16 week schedule, there is no number of golfers for which a
schedule can be created in which a player never plays with another
twice.

Mark Perkins

Clark L. Coleman

unread,
Jun 4, 1998, 3:00:00 AM6/4/98
to

In article <3576F526...@cisco.com>, Mark Perkins <m...@cisco.com> wrote:
>>
>> In sci.op-research, bigwi...@aol.com (Bigwind777) writes:
>>
>> >Please help with this problem.
>>
>> >I have 32 golfers, individual play.
>>
>> >We will golf for 16 weeks.
>>
>> >I want to set up the foursomes so each person only golfs
>> >with the same person once.
>>
>> >How many weeks can we do this before it starts to duplicate ?
>As a first cut, there are only certain combinations of weeks and players
>which have a chance. Looking at it from my point of view, I will play
>with three new golfers each week, so the number of golfers in the group
>has to be:
> 1 + 3*weeks
>
>However, the number of golfers must be a multiple of 4 in order to make
>foursomes. The pairs which satisfy these two constraints are:
>
>weeks golfers
>------ ------
> 1 4 (I know the solution to this one)
> 5 16
> 9 28
> 13 40
>4n+1 12n+4 for n = 4,5,6,...
>
>Of course, just satisfying these two constraints does not mean that a
>feasible solution can be constructed.
>
>But, we can immediately answer the original question:
>* For 32 golfers there is no schedule in which a player never plays with
>another twice.
>* For a 16 week schedule, there is no number of golfers for which a
>schedule can be created in which a player never plays with another
>twice.
>

I am afraid that you are adding a new constraint: that every golfer
must play with every other golfer. That was not an original
requirement. Thus, your statement that the table above contains the
only solutions is false. Obviously, we could have 8 weeks and 28
golfers if we can have 9 weeks and 28 golfers. Just schedule the same
way as the first 8 weeks of the solution to the 9-week problem. The
original poster said that he knew he could not schedule 32 golfers for
16 weeks, so his question was how long could he schedule before
duplication occurs.

The statement that there is no solution for 32 golfers is true for a
certain number of weeks, as the original poster acknowledged, but is
not true in general. I can certainly construct schedules for 2 weeks,
3 weeks, etc. in which 32 golfers never have the same partner twice.
It cannot be done for as long as 16 weeks, as the original poster
acknowledged.

I would say that, with duplication inevitable in 16 weeks, that an
8-week solution could be devised for 32 players, and then
repeated. But then we would not necessarily "maximize" the
socializing.


Basil McMillan

unread,
Jun 5, 1998, 3:00:00 AM6/5/98
to

war...@cs.mu.oz.au (Warwick HARVEY) wrote:

>In sci.op-research, bigwi...@aol.com (Bigwind777) writes:
>
>>Please help with this problem.
>
>>I have 32 golfers, individual play.
>
>>We will golf for 16 weeks.
>
>>I want to set up the foursomes so each person only golfs
>>with the same person once.
>
>>How many weeks can we do this before it starts to duplicate ?

>.......


>It seems to be a generalisation of the problem of constructing a
>round-robin tournament schedule, where the number players in a "game" is
>more than two.
>
>Has anybody had any experience with this kind of problem? Any ideas on
>good ways to model it?

I had a quick hack at it using Excel, but ran out of number space and
time. Essentially, I associated each individual with a prime number,
and each combination of 4 with the product of primes and previous team
products. Factorizing then quickly provides ways to identify eligible
combinations. Using Excel does not work because it very quickly runs
out of number accuracy and size. Perhaps one of the languages that
can handle indefinite sized numbers would work. It certainly seemed
to be a viable approach


Warwick HARVEY

unread,
Jun 5, 1998, 3:00:00 AM6/5/98
to

Mark Perkins <m...@cisco.com> writes:

>As a first cut, there are only certain combinations of weeks and players
>which have a chance. Looking at it from my point of view, I will play
>with three new golfers each week, so the number of golfers in the group
>has to be:
> 1 + 3*weeks

Yes, but as another poster has already pointed out, there was no requirement
that every player play with every other player: only that they don't play
more than once.

>However, the number of golfers must be a multiple of 4 in order to make
>foursomes. The pairs which satisfy these two constraints are:

>weeks golfers
>------ ------
> 1 4 (I know the solution to this one)
> 5 16

... and I've written a program which yields a solution to this one (golfers
are labelled 1-9, A-G):

Week 1: 1234 5678 9ABC DEFG
Week 2: 159D 26AE 37BF 48CG
Week 3: 16BG 25CF 389E 47AD
Week 4: 17CE 28BD 35AG 469F
Week 5: 18AF 279G 36CD 45BE

This immediately yields a 5-week solution for 32 golfers, where you
replicate the above pattern for the other 16 golfers. This results in no
socialisation between the two groups of 16 (this isn't necessarily a
problem, just an observation). One would guess that by mixing all 8 groups
in together, one could obtain a solution for more than 5 weeks. Note that
you cannot just extend the 5-week solution I just described: you cannot form
a group of 4 in the 6th week where none of the golfers have played with
another from that group. This is because any group will have at least two
golfers from one half or the other, and all golfers in a given half have
already played with every other golfer in that half.

Anyway, I have my program chewing on a 6-week solution for 32 golfers. It
has already said "no" to an 8-week solution (after 9 hours of thinking :-),
but that could just be a bug (I intend to play with the problem by hand to
try to justify why there can be no 8-week solution, but if this seems
obvious to anybody out there, feel free to jump in and answer it for me!).


For anybody who is interested, I will present a discussion of my approach to
the problem and explain why I did things the way I did sometime in the next
few days (right now, I have to go home :-).

Warwick

davyN...@bu.edu

unread,
Jun 7, 1998, 3:00:00 AM6/7/98
to

In article <6l8bbs$534$1...@mulga.cs.mu.OZ.AU>,
war...@cs.mu.oz.au (Warwick HARVEY) wrote:
>Mark Perkins <m...@cisco.com> writes:


>This immediately yields a 5-week solution for 32 golfers, where you
>replicate the above pattern for the other 16 golfers. This results in no
>socialisation between the two groups of 16 (this isn't necessarily a
>problem, just an observation). One would guess that by mixing all 8 groups
>in together, one could obtain a solution for more than 5 weeks. Note that
>you cannot just extend the 5-week solution I just described: you cannot form
>a group of 4 in the 6th week where none of the golfers have played with
>another from that group. This is because any group will have at least two
>golfers from one half or the other, and all golfers in a given half have
>already played with every other golfer in that half.
>
>Anyway, I have my program chewing on a 6-week solution for 32 golfers. It
>has already said "no" to an 8-week solution (after 9 hours of thinking :-),
>but that could just be a bug (I intend to play with the problem by hand to
>try to justify why there can be no 8-week solution, but if this seems
>obvious to anybody out there, feel free to jump in and answer it for me!).
>
>
>For anybody who is interested, I will present a discussion of my approach to
>the problem and explain why I did things the way I did sometime in the next
>few days (right now, I have to go home :-).

I took a stab at it, and came up with a program to try and get an answer. It
took about one minute to get the following solution. If anyone is interested,
I can post the code, it is a partially random search with a very simple
scoring function. Here are the results.
- Dave

week 1
group 1
1 5 13 32
group 2
8 10 17 18
group 3
2 3 14 28
group 4
6 25 30 31
group 5
15 16 22 23
group 6
4 9 11 19
group 7
7 21 24 26
group 8
12 20 27 29
not placed:

week 2
group 1
3 8 19 26
group 2
5 9 22 24
group 3
1 15 17 28
group 4
2 16 18 31
group 5
10 13 20 21
group 6
14 27 30 32
group 7
4 6 7 12
group 8
11 23 25 29
not placed:

week 3
group 1
4 16 17 24
group 2
7 11 18 22
group 3
8 21 25 27
group 4
6 23 28 32
group 5
5 14 19 20
group 6
9 13 26 29
group 7
1 2 10 30
group 8
3 12 15 31
not placed:

week 4
group 1
12 18 23 24
group 2
1 14 25 26
group 3
3 4 5 27
group 4
6 9 10 15
group 5
7 8 16 28
group 6
13 17 19 31
group 7
2 11 20 32
group 8
21 22 29 30
not placed:

week 5
group 1
11 13 24 30
group 2
3 18 29 32
group 3
2 15 19 21
group 4
6 16 20 26
group 5
4 8 14 22
group 6
7 9 17 25
group 7
5 10 12 28
group 8
1 23 27 31
not placed:

week 6
group 1
20 22 28 31
group 2
3 7 23 30
group 3
9 12 21 32
group 4
14 15 24 29
group 5
10 16 19 27
group 6
2 5 17 26
group 7
4 13 18 25
group 8
1 6 8 11
not placed:

week 7
group 1
4 10 23 26
group 2
5 7 29 31
group 3
9 18 27 28
group 4
19 24 25 32
group 5
8 15 20 30
group 6
1 3 16 21
group 7
2 6 13 22
group 8
11 12 14 17
not placed:

week 8
group 1
2 8 9 23
group 2
7 10 32
group 3
5 6 18 21
group 4
3 20 25
group 5
11 15 26 27
group 6
1 12 19 22
group 7
13 14 16
group 8
4 28 29
not placed: 17 24 30 31

week 9
group 1
6 17 29
group 2
8 12 13
group 3
2 7 27
group 4
5 11 16
group 5
9 14 31
group 6
10 22 25
group 7
4 15 32
group 8
26 28 30
not placed: 1 3 18 19 20 21 23 24

week 10
group 1
7 13 15
group 2
9 16 30
group 3
17 22 27
group 4
14 21 23
group 5
8 24 31
group 6
3 10 11
group 7
2 12 25
group 8
1 18 20
not placed: 4 5 6 19 26 28 29 32

week 11
group 1
18 19 30
group 2
1 4
group 3
3 6 24
group 4
17 20 23
group 5
5 15 25
group 6
11 21 28
group 7
13 27
group 8
22 26 32
not placed: 2 7 8 9 10 12 14 16 29 31

week 12
group 1
4 21 31
group 2
6 14
group 3
5 23
group 4
24 27
group 5
8 29
group 6
1 7
group 7
9 20
group 8
3 22
not placed: 2 10 11 12 13 15 16 17 18 19 25 26 28
30 32

week 13
group 1
12 16
group 2
11 31
group 3
17 21
group 4
15 18
group 5
19 23
group 6
2 29
group 7
8 32
group 8
1 9
not placed: 3 4 5 6 7 10 13 14 20 22 24 25 26 27
28 30

week 14
group 1
10 14
group 2
3 9
group 3
19 28
group 4
12 26
group 5
7 20
group 6
13 23
group 7
2 24
group 8
5 8
not placed: 1 4 6 11 15 16 17 18 21 22 25 27 29 30
31 32

week 15
group 1
31 32
group 2
16 25
group 3
10 29
group 4
12 30
group 5
13 28
group 6
18 26
group 7
1 24
group 8
6 27
not placed: 2 3 4 5 7 8 9 11 14 15 17 19 20 21 22
23

week 16
group 1
1 29
group 2
2 4
group 3
10 24
group 4
26 31
group 5
3 17
group 6
5 30
group 7
16 32
group 8
6 19
not placed: 7 8 9 11 12 13 14 15 18 20 21 22 23 25
27 28

Reply all
Reply to author
Forward
0 new messages