Wednesday, February 18, 2009

The Volleyball Problem

My friend Koa, a volleyball coach, called me up today and asked me a question to help him coach his team. He has 14 players, and wants to create groups of 3 such that every player plays with every other player at least once. How does he go about creating those groups?

My first thought was to create a circle with each players name around the circle and draw lines which indicate who'd they'd be playing with.

But this creates problems because as you can see that means there are 364 different ways of grouping 3 people together amongst the 14 so that every players plays with another player at least once. (or so I think, I took Combinatorics too many years ago). I thought to myself, there must be some mistake, perhaps this model doesn't take into account duplicates. So I worked out an easier case: 2 person groups amongst a pool of 4 people.
Since order doesn't matter, all we are worried about is the fact that player 1 plays with player 2 at least once, duplicate entries do exist. moreover, this seems to be a horrid way of grouping folks together.

Perhaps a better method would be to have the 14 players count off to 5's, and group the 3 1's together, the 3 2's together, and so on. But how would you mix the players after they've played one set so that every player plays with every other player. The problem still stands. Any thoughts, ideas or solutions?

4 comments:

T Lit said...

my face just melted.

Anonymous said...

i think i've got a method. i'll try and post this afternoon when i get off. - Matt

Anonymous said...

take 14 index cards and writes names on them, then number them 1 to 14. arrange in 3 rows as follows:

1 2 3 4
9 8 7 6 5
10 11 12 13 14

group by columns. (5 and 14 get byes)
then shift as follows:

14 1 2 3
8 7 6 5 4
9 10 11 12 13

iterate.
conjecture: after 14 iterations each group composition will have been attained with no repeats.

i think i've got a proof that all compositions are attained. haven't worked out the no repeats part tho.

- Matt

Said said...

Matt,

That is very clever. nice job. I'd be interested in seeing the proof. email me at thebigrokh@gmail.com

Do you have any formal mathematical education?

-S