Social Golfer problem
Thursday, May 6, 2010 :: Tagged under: pablolife. ⏰ 2 minutes.
Hey! Thanks for reading! Just a reminder that I wrote this some years ago, and may have much more complicated feelings about this topic than I did when I wrote it. Happy to elaborate, feel free to reach out to me! 😄
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 in a group 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:
Week Number | Team 1 | Team 2 | Team 3 |
---|---|---|---|
1 | 1,2,3 | 4,5,6 | 7,8,9 |
And here's how it could look after three weeks:
Week Number | Team 1 | Team 2 | Team 3 |
---|---|---|---|
1 | 1,2,3 | 4,5,6 | 7,8,9 |
2 | 1,4,7 | 2,5,8 | 3,6,9 |
3 | 1,5,9 | 2,6,7 | 3,4,8 |
Notice that the player "1" played with two totally different people in week two, and in week three "1" didn't play with anyone they played with from weeks one and two.
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?
Thanks for the read! Disagreed? Violent agreement!? Feel free to join my mailing list, drop me a line at , or leave a comment below! I'd love to hear from you 😄