Link to home
Start Free TrialLog in
Avatar of GwynforWeb
GwynforWebFlag for Canada

asked on

12 people playing golf

12 people playing golf
groups of 4
4 rounds

Is it possible for everyone to play a golf game with every other person at least once, I'd be interested in a proof that it can not be done or a demonstration of  that it can.  I do not know the answer to this question. It is close to a Steiner system problem but is not quite.

Statements of the form "my mate Frank tried to do it but couldn't " are not considered proofs.
Avatar of d-glitch
d-glitch
Flag of United States of America image

I am sure it's impossible.
I believe you can play three very efficient rounds.
But the fourth round kills you.

Not a proof, but if you can see what's happening if you use
a matrix to do the scheduling.  

12 players would require 12x12 matrix, but you need are the
66 elements above or below the diagonal.


player 1 needs to play 11 games
           2                        10
          3                           9
etc
totaling 66 games as d-glitch said.
-
In the first round 18 games are played
But in the second there are only 16 pairs not already used possible
At most in the third is 14 pairs
At most in the fourth 12 pairs. for a total of 60.  Not enough
Avatar of Sean Stuber
Sean Stuber

player 1 doesn't need to play 11 games,  4 games is sufficient for 1 player.

12 players - abcdefghijkl  in groups of 4

abcd
aefg
ahij
akl   and one person can repeat playing with a.

the tricky part is getting everyone else to play exhaustive combinations
"player 1 doesn't need to play 11 games,  4 games is sufficient for 1 player."
Depends on your definition of game. Not being a golfer I do not know the definition. i was using pairings. In the first round I guess player one played one game but could be paired with three people. No matter what the definition is you run out of pairings because they come in groups of four
"Depends on your definition of game"

fair enough.

usually in golf groupings like this every player in the group is considered to have played the same game.

With "abcd"  "a" has played 1 game with 3 people (as have b,c and d)
So, there are no "pairings" to consider except to the evaluation of  2 players having played together at least once in any of their "groupings"

So,  with the list I sent above.  player "a" will have played with every other player in 4 games and one player from (b-j) twice.

But, that doesn't mean the other 11 players have played with everybody

The simple answer is, that any given player has to play with 3 different other players for 4 times, which would require 12 other players, but there are only 11 other players so it can't be done.
I don't think it's that simple there is no prohibition against playing with a player more than once.

The request is "at least once" with every other player.
Here are schedules for the first two days.
The chart can guide you in the scheduling for the third and fourth days.
You can try greedy algorithms.
You can try Monte Carlo techniques.

The missing Chart....
Golf-Schedule.jpg
With 12 players, there are only 5775 ways schedule a day of golf:

     (12!)/(4!*4!*4!*3!)

Should be possible to do an exhaustive search.  
That would be a proof, but just talking about it isn't.



ASKER CERTIFIED SOLUTION
Avatar of Sean Stuber
Sean Stuber

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial