167 views

Skip to first unread message

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.

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

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

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.

>

>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.

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

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

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

Search

Clear search

Close search

Google apps

Main menu