Creating Groups, Minimal Overlap

[gumpzilla]

No, it isn't possible with four games. An easy way to see this is graphical. Consider six points A, B, C, D, E and F. When A, B and C play a game together, I'll draw a triangle connecting them. Your requirement that every team play every team at least once means that when I've put in all the triangles I'm going to put in, there is an edge connecting every two points. This requires 6*5/2 = 15 edges. But with four triangles I only have 12 edges. So it's impossible to have every player play a game with every other player at least once with four games.

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.

The format is

ABCDEF/GHIJKL/MNOPQR/STUVWX?

[TomCollins]

[ QUOTE ]
The format is

ABCDEF/GHIJKL/MNOPQR/STUVWX?

[/ QUOTE ]

Sure.

I just realized why I recognized the Kirkman Schoolgirl Problem, one of my old math prof's was the one who solved the general case for it in 1968.

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

[/ QUOTE ]

According to Wikipedia, Kathy Liebert and Todd Brunson played each other 4 times in the elimination matches, so they were pretty far from having a balanced schedule. Still, would your players mind that much if you gave up and used the PSI schedule?

[TomCollins]

I'd prefer something balanced, but if you have that schedule, I'll steal it.

Using gump's reasoning I think I can prove this is impossible.

You need to connect a total of (24*23)/2=276 pairs. Each game will involve 6 pairs, and there are 4 games at any given time with 6 sessions. Therefore you have 6*6*4 = 144 "edges."

144<276, so there are not nearly enough "edges" to accomodate your pairs.

Edit: This is wrong. You would draw lines between each pair, and there would be plenty enough lines. Rather than 6-sided figures, you would have lots and lots and lots of triangles. Back to the drawing board.

[Darryl_P]

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

[/ QUOTE ]

I think I can prove this is impossible.

Key reason: for any 6 players playing at a given table there are 15 possible pairs, of which 10 must recur at some point later. To see this, simply assume ABCDEF are playing at the same table in the first round, and note that in all subsequent rounds you must distribute these 6 players among 4 tables, leaving at least 2 groups of 2 or 1 group of 3. That's at least 2 recurring pairs per round which makes at least 10 recurring pairs in 5 rounds. So worded another way, if you want to make sure no pair gets repeated more than once, you can have at most 5 unique pairs at a given table in a given round.

There are 4 tables per round and 6 rounds in all which makes at most 4x6x5 = 120 unique pairs in all.

But the goal of the problem is to have all of the 276 possible pairs occuring at least once in a tournament format that involves a total of 360 pairs. There is only room for 84 duplicates which means that 192 pairs must be unique. Since you cannot exceed 120 unique pairs, this cannot be done.

[ QUOTE ]
I'd prefer something balanced, but if you have that schedule, I'll steal it.

[/ QUOTE ]

Here is the Wikipedia page about PSI, and the schedule for PSI 2 is about half way down the page.

Looking at it, it seems that they did a pretty bad job of scheduling, with some people playing 4 times. I am convinced that it should be fairly easy to make a better schedule with no two players meeting more than 3 times, but my first attempt failed and I don't really feel like spending too much time on it.