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.

[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.

Okay, I'm dumb.

So all six players are in each game. It's 3v3 and you want to divide the teams up so that each player is on another player's team at least once (but no more than twice). Correct?

It's impossible with 3 or with 4 games. This is because the "second game" must mirror the "first game."

I'm struggling to make this "slick" too, so I'll just have to be a bit sloppy.

A must play against one other player twice (call it B). In those games, A will play against two other players (C and D) once each. Since the other team mirrors the first team we can assemble the first two games.

ABC/DEF
ABD/CEF

Now since E and F have been paired already, A can only use one of them at a time. AEx and AFy. x and y must be C and/or D, as B has already been paired twice with A. A has already been combined with C and D, so "game AE" (game 3) and "game AF" (game 4) must involve different players.

If A plays EC in game 3, A must play FD in game 4. But if this is true, then B must play FD in game 3, and B must play EC in game 4. That is, once E and F are paired with D and C, those pairs remain the same in games 3 and 4.

The problem is that D and C have already been paired with E and F. Since they must pair twice again in games 3 and 4, this means our E/F+C/D pairs must triple up.

Example:

ABC/DEF
ABD/CEF
AEC/BFD
AFD/BEC

EC and FD are triple matches here.

Edit: Gump beat me to it. Nice graph!

[TomCollins]

Did anyone watch Poker Superstars II? It's basically like that.

6 man tourney. I have 24 players. I want to have each player play against every other player at least. I don't want anyone playing against a particular player more than twice. I want each player to play 6 games.

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.

[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.