Social Golfer problem

One summer I spent working with a professor, the father of a friend heard my plans and remarked (to my friend, not to me)

I can't think of anything less intellectually stimulating than writing computer code for 7 hours a day.

After some thinking, my guess was they were probably confusing programming with data entry. Moments like these make me realize how much I take computer literacy for granted, especially among older folk. The Supreme Court makes similar mistakes, to much lulz.

I frequently find it helpful then to describe a problem that we work on, since lots of them can be easily described without mathematical notation. One of these has been a real hair-puller these last few days, called the Social Golfer Problem.

Problem Statement

The premise is this: you're organizing a golf tournament with 9 people in it. They play every week in groups of 3, and want to play for three weeks.

Here's the catch: they are social golfers, meaning if possible, they never want to play with the same people twice. Your job is to organize the tournament; you have to arrange who plays with whom every week.

So rather than use names, we'll just use numbers. The first week could look something like this:

	Group 1	Group 2	Group 3
Week 1	1   2   3	4   5   6	7   8   9

Since players 1, 2, and 3 are playing together in the first group, next week you need to organize the tournament a little differently to make sure 1 isn't in a group with 2 or 3, 5 isn't in a group with 4 or 6, and so on. A complete tournament schedule might look like this:

	Group 1	Group 2	Group 3
Week 1	1   2   3	4   5   6	7   8   9
Week 2	1   4   7	2   5   8	3   6   9
Week 3	1   5   9	2   6   7	3   4   8

So here's the question: could you organize a tournament like this with 100 people, in groups of 10, for 10 weeks?

Because if you could, you could get published in a Computer Science paper. Whether or not its even possible to schedule such a tournament is an open problem.

For Solving Hard Problems, we have to write a program that takes three numbers

• g - the number of groups in a week.


• s - the size of each group.


• w - the number of weeks.

and either prints a schedule for a social golfing tournament, or tells you its impossible.

It's a really cute problem. Hopefully in a few days, when it's done and gone, I can write about how I wrote the program. In the meantime, how would you go about it?