Creating Groups, Minimal Overlap

[TomCollins]

Suppose I have 6 letters, A-F.

I want to create 2 groups of 3 for each letter.

Is it possible to create 4 such groupings such that:
Every letter is in a group with every letter at least once but not more than twice?

I'm thinking its not, but can't quite prove it.

I'm creating a simplified version of creating 4 groups of 6 from 24, using 6 pairings such that every letter is matched with every other at least once but not twice. There has to be a good method to this.

[sweetjazz]

"I want to create 2 groups of 3 for each letter." What does this mean? Can you give an example?

And you want 4 such groupings, meaning you want 4 groups of 2 groups of 3? I am having a very hard time understanding what you are asking. (It might just be that I am dense. [img]/images/graemlins/smile.gif[/img] )

But I'd like to try to help if you could explain differently what it is you are looking for.

[TomCollins]

I probably explained this poorly.

Suppose I have a team game that takes 3 players at a time. I want to schedule a series of games that has each player be in a game with every other player at least once, but no more than twice.

For example:
Game 1 Game 2
ABC DEF
ADE BCF
ABF CDE

In this case, a plays everyone once, and B twice. But D plays E 3 times, and doesn't play B ever.

There has to be some math-y name for this type of thing.

For 6 players in 3-man games, I think you'd have to have 4 matches. But I'm not even sure I can satisfy the play once but not twice criteria.

If I understand you, this seems impossible with any number of groups.

In each grouping, one letter is paired with 2 other letters. But for each letter, there are 5 additional letters to be paired with. 2 groups will result in pairings with 4 letters (but not a fifth). 3 groups will result in a duplicate (there are 6 "slots" to pair the letter with, but only 5 letter to put into the pairs).

You could have ABC and ADE, but how will you pair A and F now? If you create a new set AFx where x is another letter, which letter is x? No matter what this will result in duplication.

[TomCollins]

[ QUOTE ]
If I understand you, this seems impossible with any number of groups.

In each grouping, one letter is paired with 2 other letters. But for each letter, there are 5 additional letters to be paired with. 2 groups will result in pairings with 4 letters (but not a fifth). 3 groups will result in a duplicate (there are 6 "slots" to pair the letter with, but only 5 letter to put into the pairs).

You could have ABC and ADE, but how will you pair A and F now? If you create a new set AFx where x is another letter, which letter is x? No matter what this will result in duplication.

[/ QUOTE ]

I'm allowing duplication of some, but never triplicaiton.

Okay. "At least once but not twice" threw me.

ABC ADE AFB BDE CDF CEF

Works if I'm not mistaken.

I don't think this can be done with 4 matches.

[sweetjazz]

[ QUOTE ]
I probably explained this poorly.

Suppose I have a team game that takes 3 players at a time. I want to schedule a series of games that has each player be in a game with every other player at least once, but no more than twice.

For example:
Game 1 Game 2
ABC DEF
ADE BCF
ABF CDE

In this case, a plays everyone once, and B twice. But D plays E 3 times, and doesn't play B ever.

There has to be some math-y name for this type of thing.

For 6 players in 3-man games, I think you'd have to have 4 matches. But I'm not even sure I can satisfy the play once but not twice criteria.

[/ QUOTE ]

Yeah, you can take your example and generalize it into an argument for impossibility.

Pick one team (call it 'A'). There must be some team they play twice (call them 'B'). In those two games, A plays B plus two other teams (call them 'C' and 'F'). Let 'D' and 'E' be the remaining teams. We know they play each other the two times that A plays B. But both D and E must play A once, and there is only game left for A, so that is the third time that D and E play.

I wonder if there is a quicker "slicker" way to prove this.

[gumpzilla]

You're being pretty vague in your requirements, but the following series of 6 games can ensure that everybody plays three games and plays everybody at least once and one player exactly twice:

ABC
ADE
AFB
BDE
CDF
CEF

The problem you're running into is because you insist that two games be played simultaneously so that all players are used. This can't work: once you have ABC, ADE, and AFB (I arbitrarily pick B as the person A plays twice, it doesn't matter what you name him), this forces BDE to make sure that B plays with the two people he hasn't yet, CDF and CEF are necessary for D and E respectively.

[TomCollins]

[ QUOTE ]
You're being pretty vague in your requirements, but the following series of 6 games can ensure that everybody plays three games and plays everybody at least once and one player exactly twice:

ABC
ADE
AFB
BDE
CDF
CEF

The problem you're running into is because you insist that two games be played simultaneously so that all players are used. This can't work: once you have ABC, ADE, and AFB (I arbitrarily pick B as the person A plays twice, it doesn't matter what you name him), this forces BDE to make sure that B plays with the two people he hasn't yet, CDF and CEF are necessary for D and E respectively.

[/ QUOTE ]

Is it possible with 4 games?

[ QUOTE ]

I'm creating a simplified version of creating 4 groups of 6 from 24, using 6 pairings such that every letter is matched with every other at least once but not twice. There has to be a good method to this.

[/ QUOTE ]

So your ultimate goal is the 24 team schedule, divided into groups of 6?

Unfortunately, the area of math that you are interested in (Combinatorial Design Theory) is more devoted to finding solutions that work out perfectly, i.e., when each team plays the others exactly once. For dividing into groups of 3, this is known as the Kirkman school girl problem and has a perfect solution if and only if you have 6n+3 teams. I'm assuming that you want each team to play at least once but no more than twice in your 24 team model because it is trivial to show that it isn't possible to have an exact solution, but that also means that the literature has tended to skip your problem.

I would be tempted to look at individual movements for 24 players at bridge and see if you get what you want from there. Have all the people playing N on board 1 be 1 group of 6, the people playing E on board 1 a 2nd group, etc. I don't know if this will work or not. A couple of different 24-player movements are at this webpage