Mixing
Multi sports tournament $10$ teams $6$ sports simultaneous
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I'm hosting a bar sports tournament with $10$ teams and $6$ different sports (pool, darts, table tennis, foosball, beer pong and cornhole). Trying to get the fixtures as fair as possible so that each team plays each sport twice and playing against the same team multiple times is minimised. Are there any formulas to follow? There is potential for $11$ or $12$ teams to end up competing. I feel like having $12$ or $13$ would make this task a lot easier!
Edit: The plan is to have 12 rounds with each sport being played in each round. There is only one pool table, dart board etc available so the same sport cannot be played in the same round. Are there simpler solutions for say 12 teams?
Edit 2: I haven't done any mathematics beyond high school 10 years ago. I've just tried to figure it out as best I can drawing up tables and assigning teams against each other in different slots but ending up with teams playing the same sport or against each other again as there are limited playing slots. Ideally I'd like to know if there is a formula that can be applied to x amount of teams/sports/rounds for multi sports tournaments as all the fixture generators I've tried using only account for one sport being played.
combinatorics
asked Jul 18 at 2:58
J.Mac
112
add a comment |Â
up vote
2
down vote
favorite
I'm hosting a bar sports tournament with $10$ teams and $6$ different sports (pool, darts, table tennis, foosball, beer pong and cornhole). Trying to get the fixtures as fair as possible so that each team plays each sport twice and playing against the same team multiple times is minimised. Are there any formulas to follow? There is potential for $11$ or $12$ teams to end up competing. I feel like having $12$ or $13$ would make this task a lot easier!
Edit: The plan is to have 12 rounds with each sport being played in each round. There is only one pool table, dart board etc available so the same sport cannot be played in the same round. Are there simpler solutions for say 12 teams?
Edit 2: I haven't done any mathematics beyond high school 10 years ago. I've just tried to figure it out as best I can drawing up tables and assigning teams against each other in different slots but ending up with teams playing the same sport or against each other again as there are limited playing slots. Ideally I'd like to know if there is a formula that can be applied to x amount of teams/sports/rounds for multi sports tournaments as all the fixture generators I've tried using only account for one sport being played.
combinatorics
asked Jul 18 at 2:58
J.Mac
112
Let n be the number of teams, if n is even, n/2 vs. n/2 for 12 rounds. If n is odd, (n+1)/2 vs (n-1/2) for 12 rounds. Make sense?
– Nick
Jul 18 at 3:17
@Nick This doesn't really address the OP's problem. How to ensure that each team plays each game twice, while minimizing the number of times the same teams meet.
– saulspatz
Jul 18 at 3:26
Since each team plays $12$ times, I imagine you would like to get in done in $12$ rounds. Am I correct in assuming that each event (foosball, pool, etc.) can only be played once in a given round?
– saulspatz
Jul 18 at 3:35
@saulspatz This is a question about bracketing. It's taught in sports theory and such. 10 Team round robin would seem like a good strategy here but it doesn't account for the double play.
– Nick
Jul 18 at 4:17
2
@Nick It's easy to find a grouping where each team plays $6$ teams once and $3$ teams twice; just run the circle method for $3$ more rounds. Then in the first two rounds, every match is pool, in the next two, every match is darts, and so on. Now we have satisfied the requirements as to opponents and games, but there's only one pool table, say. We somehow have to distribute these matches in $12$ rounds so that no sport is played more than once in a single round, or at least, that's what I'm assuming. I don't know how bar sports tournaments work, so I could be all wrong about that.
– saulspatz
Jul 18 at 5:11
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm hosting a bar sports tournament with $10$ teams and $6$ different sports (pool, darts, table tennis, foosball, beer pong and cornhole). Trying to get the fixtures as fair as possible so that each team plays each sport twice and playing against the same team multiple times is minimised. Are there any formulas to follow? There is potential for $11$ or $12$ teams to end up competing. I feel like having $12$ or $13$ would make this task a lot easier!
Edit: The plan is to have 12 rounds with each sport being played in each round. There is only one pool table, dart board etc available so the same sport cannot be played in the same round. Are there simpler solutions for say 12 teams?
Edit 2: I haven't done any mathematics beyond high school 10 years ago. I've just tried to figure it out as best I can drawing up tables and assigning teams against each other in different slots but ending up with teams playing the same sport or against each other again as there are limited playing slots. Ideally I'd like to know if there is a formula that can be applied to x amount of teams/sports/rounds for multi sports tournaments as all the fixture generators I've tried using only account for one sport being played.
combinatorics
asked Jul 18 at 2:58
J.Mac
112
I'm hosting a bar sports tournament with $10$ teams and $6$ different sports (pool, darts, table tennis, foosball, beer pong and cornhole). Trying to get the fixtures as fair as possible so that each team plays each sport twice and playing against the same team multiple times is minimised. Are there any formulas to follow? There is potential for $11$ or $12$ teams to end up competing. I feel like having $12$ or $13$ would make this task a lot easier!
Edit: The plan is to have 12 rounds with each sport being played in each round. There is only one pool table, dart board etc available so the same sport cannot be played in the same round. Are there simpler solutions for say 12 teams?
Edit 2: I haven't done any mathematics beyond high school 10 years ago. I've just tried to figure it out as best I can drawing up tables and assigning teams against each other in different slots but ending up with teams playing the same sport or against each other again as there are limited playing slots. Ideally I'd like to know if there is a formula that can be applied to x amount of teams/sports/rounds for multi sports tournaments as all the fixture generators I've tried using only account for one sport being played.
combinatorics
asked Jul 18 at 2:58
J.Mac
112
edited Jul 18 at 11:57
asked Jul 18 at 2:58
J.Mac
112
asked Jul 18 at 2:58
J.Mac
112
asked Jul 18 at 2:58
J.Mac
112
112
Let n be the number of teams, if n is even, n/2 vs. n/2 for 12 rounds. If n is odd, (n+1)/2 vs (n-1/2) for 12 rounds. Make sense?
– Nick
Jul 18 at 3:17
@Nick This doesn't really address the OP's problem. How to ensure that each team plays each game twice, while minimizing the number of times the same teams meet.
– saulspatz
Jul 18 at 3:26
Since each team plays $12$ times, I imagine you would like to get in done in $12$ rounds. Am I correct in assuming that each event (foosball, pool, etc.) can only be played once in a given round?
– saulspatz
Jul 18 at 3:35
@saulspatz This is a question about bracketing. It's taught in sports theory and such. 10 Team round robin would seem like a good strategy here but it doesn't account for the double play.
– Nick
Jul 18 at 4:17
2
@Nick It's easy to find a grouping where each team plays $6$ teams once and $3$ teams twice; just run the circle method for $3$ more rounds. Then in the first two rounds, every match is pool, in the next two, every match is darts, and so on. Now we have satisfied the requirements as to opponents and games, but there's only one pool table, say. We somehow have to distribute these matches in $12$ rounds so that no sport is played more than once in a single round, or at least, that's what I'm assuming. I don't know how bar sports tournaments work, so I could be all wrong about that.
– saulspatz
Jul 18 at 5:11
add a comment |Â
Let n be the number of teams, if n is even, n/2 vs. n/2 for 12 rounds. If n is odd, (n+1)/2 vs (n-1/2) for 12 rounds. Make sense?
– Nick
Jul 18 at 3:17
@Nick This doesn't really address the OP's problem. How to ensure that each team plays each game twice, while minimizing the number of times the same teams meet.
– saulspatz
Jul 18 at 3:26
Since each team plays $12$ times, I imagine you would like to get in done in $12$ rounds. Am I correct in assuming that each event (foosball, pool, etc.) can only be played once in a given round?
– saulspatz
Jul 18 at 3:35
@saulspatz This is a question about bracketing. It's taught in sports theory and such. 10 Team round robin would seem like a good strategy here but it doesn't account for the double play.
– Nick
Jul 18 at 4:17
2
@Nick It's easy to find a grouping where each team plays $6$ teams once and $3$ teams twice; just run the circle method for $3$ more rounds. Then in the first two rounds, every match is pool, in the next two, every match is darts, and so on. Now we have satisfied the requirements as to opponents and games, but there's only one pool table, say. We somehow have to distribute these matches in $12$ rounds so that no sport is played more than once in a single round, or at least, that's what I'm assuming. I don't know how bar sports tournaments work, so I could be all wrong about that.
– saulspatz
Jul 18 at 5:11
Let n be the number of teams, if n is even, n/2 vs. n/2 for 12 rounds. If n is odd, (n+1)/2 vs (n-1/2) for 12 rounds. Make sense?
– Nick
Jul 18 at 3:17
Let n be the number of teams, if n is even, n/2 vs. n/2 for 12 rounds. If n is odd, (n+1)/2 vs (n-1/2) for 12 rounds. Make sense?
– Nick
Jul 18 at 3:17
@Nick This doesn't really address the OP's problem. How to ensure that each team plays each game twice, while minimizing the number of times the same teams meet.
– saulspatz
Jul 18 at 3:26
@Nick This doesn't really address the OP's problem. How to ensure that each team plays each game twice, while minimizing the number of times the same teams meet.
– saulspatz
Jul 18 at 3:26
Since each team plays $12$ times, I imagine you would like to get in done in $12$ rounds. Am I correct in assuming that each event (foosball, pool, etc.) can only be played once in a given round?
– saulspatz
Jul 18 at 3:35
Since each team plays $12$ times, I imagine you would like to get in done in $12$ rounds. Am I correct in assuming that each event (foosball, pool, etc.) can only be played once in a given round?
– saulspatz
Jul 18 at 3:35
@saulspatz This is a question about bracketing. It's taught in sports theory and such. 10 Team round robin would seem like a good strategy here but it doesn't account for the double play.
– Nick
Jul 18 at 4:17
@saulspatz This is a question about bracketing. It's taught in sports theory and such. 10 Team round robin would seem like a good strategy here but it doesn't account for the double play.
– Nick
Jul 18 at 4:17
2
2
@Nick It's easy to find a grouping where each team plays $6$ teams once and $3$ teams twice; just run the circle method for $3$ more rounds. Then in the first two rounds, every match is pool, in the next two, every match is darts, and so on. Now we have satisfied the requirements as to opponents and games, but there's only one pool table, say. We somehow have to distribute these matches in $12$ rounds so that no sport is played more than once in a single round, or at least, that's what I'm assuming. I don't know how bar sports tournaments work, so I could be all wrong about that.
– saulspatz
Jul 18 at 5:11
@Nick It's easy to find a grouping where each team plays $6$ teams once and $3$ teams twice; just run the circle method for $3$ more rounds. Then in the first two rounds, every match is pool, in the next two, every match is darts, and so on. Now we have satisfied the requirements as to opponents and games, but there's only one pool table, say. We somehow have to distribute these matches in $12$ rounds so that no sport is played more than once in a single round, or at least, that's what I'm assuming. I don't know how bar sports tournaments work, so I could be all wrong about that.
– saulspatz
Jul 18 at 5:11
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
Label the teams $0$ to $9$ and the sports $0$ to $5$. Here $k,%,6$ denotes the remainder of $k$ modulo $6$.
First let each team $i$ play each other team $j$ in the sport $i+j,%,6$:
$$
matrix&1&2&3&4&5&0&1&2&3\
matrix1&&3&4&5&0&1&2&3&4\
matrix2&3&&5&0&1&2&3&4&5\
matrix3&4&5&&1&2&3&4&5&0\
matrix4&5&0&1&&3&4&5&0&1\
matrix5&0&1&2&3&&5&0&1&2\
matrix0&1&2&3&4&5&&1&2&3\
matrix1&2&3&4&5&0&1&&3&4\
matrix2&3&4&5&0&1&2&3&&5\
matrix3&4&5&0&1&2&3&4&5&\
$$
The three sports that each team is missing are the ones that would have been on the diagonal and in the two columns you'd get if you'd extend the table to the right. With the diagonal in the first column and the two extension columns in the second and third column, this is:
$$
matrix
0&4&5\
2&5&0\
4&0&1\
0&1&2\
2&2&3\
4&3&4\
0&4&5\
2&5&0\
4&0&1\
0&1&2
$$
Now let each team $i$ for $0le ile8$ play team $i+1$ in sport $i+5,%,6$. That takes care of the second and third columns, except for the game in sport $4$ for team $0$ and the game in sport $2$ for team $9$. These two games together with the ten missing games from the diagonal in the first column are four games each in the sports $0$, $2$ and $4$, and you can form two pairs for each of these sports in whatever way you like because none of the possible pairs have played a second game yet.
answered Jul 18 at 4:21
joriki
164k10180328
This doesn't schedule the matches into rounds, does it? (I've been trying to do it assuming that there were $12$ rounds, with all teams playing in each round, and no sport played more than once in a round. I know this isn't specified in the OP's question, but that's how I interpreted it.) I came up with a solution much like yours, but I can't see any systematic way of organizing the matches into rounds. I haven't even any intuition about whether it's hard or easy.
– saulspatz
Jul 18 at 5:18
@saulspatz: You're right, it doesn't. It hadn't occurred to me that this was intended, though now that you bring it up and I imagine the practical conditions of a bar sports tournament, it seems plausible that it was :-). I also don't see an easy way to do that. You can take the top right quarter of the table as one set of rounds, and the games of $i$ against $i+1$ also naturally fall into two rounds; but that would leave teams $0$ and $9$ to play their game in sport $0$ in a round in which teams $1$ and $2$ are already playing sport $0$. Looks more like a computer problem to me...
– joriki
Jul 18 at 5:39
I'm planning to try it by computer, but it's too late here to start on it tonight. Doing a bit of research on the web, I see that my approach comes down to finding a perfect matching on a $5-$uniform hypergraph with $60$ vertices, which sounds forbiding, as I see the general problem is NP-complete. I'll post an answer if I find anything interesting.
– saulspatz
Jul 18 at 5:48
2
@J.Mac: You should add that requirement to the question. It may be obvious to you since you're thinking of the practicalities of the tournament you're organizing, but, this being a math site, we solve problems according to the stated mathematical premises and don't (at least I don't) spend too much time thinking what other premises might be useful under real-world considerations. People won't read through all the comments to discover the new premise here; they should be able to understand the entire problem unambiguously just from the statement of the question.
– joriki
Jul 18 at 8:17
1
@J. Mac I don't think more teams will make things simpler, at least, not with the approach I have in mind. I'm planning on a computer program, and more teams will just make it run longer. If you get more teams, fine, you'll sell more beer, but don't recruit them specifically to simplify the problem. :-)
– saulspatz
Jul 18 at 13:38
 |Â
show 3 more comments
up vote
0
down vote
I've spent a good deal of time on this, and I haven't been able to do it, so in one sense, this isn't an answer at all, more of a progress report. On the other hand, someone may be able to suggest a modification to the method that will allow for solution. I tried it with both $10$ teams and $12$ teams, without success. I don't even have a viable approach in mind for an odd number of teams.
With $10$ teams each playing $12$ games, we will have $60$ matches. I determined a possible set of $60$ where each team played $9$ teams once and $3$ teams twice, and no two matches were identical. I then computed all possible rounds of $5$ matches chosen from among these $60,$ where a legitimate round includes all teams, and no game is played twice. With $10$ players, there were $172$ such rounds. Then I tried to choose $12$ rounds from among these $172$ that would partition the $60$ matches, but that was impossible. The result for $12$ teams was similar.
My program uses Knuth's dancing links algorithm for (generalized) set exact cover problems, so it's not apparent how to come up with some kind of approximate solution.
I've been wondering about trying different sets of $60$ matches, but there are so many isomorphisms! The program runs in a second or so, so trying lots of sets of matches isn't a concern, but of course, I'd like to generate non-isomorphic sets, if possible. At the moment, I don't see any quick way even to tell if two sets are isomorphic. (By isomorphic, I mean that one set of matches can be obtained from the other by permutation of the sports and of the teams.) I would welcome any suggestions about the isomorphism problem.
Failing this, there may be some acceptable relaxation of the conditions.
One thing that occurs to me is to go for as many full rounds as possible, and then hope that there aren't too many conflicts at the end. For example, suppose we could go for $11$ rounds, but not $12$. If the last $5$ games were all pool, that would be a problem, but if two were pool and the remaining ones were different games, that wouldn't be so bad. I'd like to know the OP's opinion of this approach.
EDIT
I modified the program to keep track of the maximum number of compatible rounds, and it was only $5$. Very discouraging. It is, however, possible to do this for an $8-$team tournament.
Round 1
T0 vs T2 at table tennis
T3 vs T6 at beer pong
T1 vs T4 at darts
T7 vs T5 at cornhole
Round 2
T0 vs T1 at beer pong
T4 vs T2 at table tennis
T6 vs T7 at pool
T5 vs T3 at foosball
Round 3
T0 vs T4 at foosball
T7 vs T3 at darts
T2 vs T5 at beer pong
T1 vs T6 at cornhole
Round 4
T0 vs T3 at table tennis
T7 vs T5 at darts
T4 vs T2 at pool
T1 vs T6 at beer pong
Round 5
T0 vs T4 at pool
T5 vs T6 at table tennis
T1 vs T2 at darts
T7 vs T3 at foosball
Round 6
T0 vs T6 at darts
T2 vs T7 at beer pong
T1 vs T4 at cornhole
T5 vs T3 at pool
Round 7
T0 vs T6 at cornhole
T4 vs T7 at table tennis
T2 vs T3 at darts
T5 vs T1 at pool
Round 8
T0 vs T5 at foosball
T7 vs T1 at pool
T6 vs T4 at darts
T2 vs T3 at cornhole
Round 9
T0 vs T3 at pool
T6 vs T7 at table tennis
T4 vs T5 at beer pong
T1 vs T2 at foosball
Round 10
T0 vs T7 at beer pong
T3 vs T1 at table tennis
T2 vs T5 at cornhole
T6 vs T4 at foosball
Round 11
T0 vs T7 at cornhole
T3 vs T4 at beer pong
T6 vs T2 at foosball
T5 vs T1 at table tennis
Round 12
T0 vs T5 at darts
T3 vs T4 at cornhole
T6 vs T2 at pool
T7 vs T1 at foosball
Here each team plays $5$ teams twice and $2$ teams once.
answered Jul 20 at 9:38
saulspatz
10.7k21323
@J.Mac While it doesn't solve the mathematical problem, it occurs to me that if you can get 12 teams, you can have two flights of 6 teams each. Each team would play 3 teams twice and 2 teams 3 times. It's easy to arrange that the two flights would never be playing the same game in the same round.
– saulspatz
Jul 20 at 11:34
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Label the teams $0$ to $9$ and the sports $0$ to $5$. Here $k,%,6$ denotes the remainder of $k$ modulo $6$.
First let each team $i$ play each other team $j$ in the sport $i+j,%,6$:
$$
matrix&1&2&3&4&5&0&1&2&3\
matrix1&&3&4&5&0&1&2&3&4\
matrix2&3&&5&0&1&2&3&4&5\
matrix3&4&5&&1&2&3&4&5&0\
matrix4&5&0&1&&3&4&5&0&1\
matrix5&0&1&2&3&&5&0&1&2\
matrix0&1&2&3&4&5&&1&2&3\
matrix1&2&3&4&5&0&1&&3&4\
matrix2&3&4&5&0&1&2&3&&5\
matrix3&4&5&0&1&2&3&4&5&\
$$
The three sports that each team is missing are the ones that would have been on the diagonal and in the two columns you'd get if you'd extend the table to the right. With the diagonal in the first column and the two extension columns in the second and third column, this is:
$$
matrix
0&4&5\
2&5&0\
4&0&1\
0&1&2\
2&2&3\
4&3&4\
0&4&5\
2&5&0\
4&0&1\
0&1&2
$$
Now let each team $i$ for $0le ile8$ play team $i+1$ in sport $i+5,%,6$. That takes care of the second and third columns, except for the game in sport $4$ for team $0$ and the game in sport $2$ for team $9$. These two games together with the ten missing games from the diagonal in the first column are four games each in the sports $0$, $2$ and $4$, and you can form two pairs for each of these sports in whatever way you like because none of the possible pairs have played a second game yet.
answered Jul 18 at 4:21
joriki
164k10180328
This doesn't schedule the matches into rounds, does it? (I've been trying to do it assuming that there were $12$ rounds, with all teams playing in each round, and no sport played more than once in a round. I know this isn't specified in the OP's question, but that's how I interpreted it.) I came up with a solution much like yours, but I can't see any systematic way of organizing the matches into rounds. I haven't even any intuition about whether it's hard or easy.
– saulspatz
Jul 18 at 5:18
@saulspatz: You're right, it doesn't. It hadn't occurred to me that this was intended, though now that you bring it up and I imagine the practical conditions of a bar sports tournament, it seems plausible that it was :-). I also don't see an easy way to do that. You can take the top right quarter of the table as one set of rounds, and the games of $i$ against $i+1$ also naturally fall into two rounds; but that would leave teams $0$ and $9$ to play their game in sport $0$ in a round in which teams $1$ and $2$ are already playing sport $0$. Looks more like a computer problem to me...
– joriki
Jul 18 at 5:39
I'm planning to try it by computer, but it's too late here to start on it tonight. Doing a bit of research on the web, I see that my approach comes down to finding a perfect matching on a $5-$uniform hypergraph with $60$ vertices, which sounds forbiding, as I see the general problem is NP-complete. I'll post an answer if I find anything interesting.
– saulspatz
Jul 18 at 5:48
2
@J.Mac: You should add that requirement to the question. It may be obvious to you since you're thinking of the practicalities of the tournament you're organizing, but, this being a math site, we solve problems according to the stated mathematical premises and don't (at least I don't) spend too much time thinking what other premises might be useful under real-world considerations. People won't read through all the comments to discover the new premise here; they should be able to understand the entire problem unambiguously just from the statement of the question.
– joriki
Jul 18 at 8:17
1
@J. Mac I don't think more teams will make things simpler, at least, not with the approach I have in mind. I'm planning on a computer program, and more teams will just make it run longer. If you get more teams, fine, you'll sell more beer, but don't recruit them specifically to simplify the problem. :-)
– saulspatz
Jul 18 at 13:38
 |Â
show 3 more comments
up vote
2
down vote
Label the teams $0$ to $9$ and the sports $0$ to $5$. Here $k,%,6$ denotes the remainder of $k$ modulo $6$.
First let each team $i$ play each other team $j$ in the sport $i+j,%,6$:
$$
matrix&1&2&3&4&5&0&1&2&3\
matrix1&&3&4&5&0&1&2&3&4\
matrix2&3&&5&0&1&2&3&4&5\
matrix3&4&5&&1&2&3&4&5&0\
matrix4&5&0&1&&3&4&5&0&1\
matrix5&0&1&2&3&&5&0&1&2\
matrix0&1&2&3&4&5&&1&2&3\
matrix1&2&3&4&5&0&1&&3&4\
matrix2&3&4&5&0&1&2&3&&5\
matrix3&4&5&0&1&2&3&4&5&\
$$
The three sports that each team is missing are the ones that would have been on the diagonal and in the two columns you'd get if you'd extend the table to the right. With the diagonal in the first column and the two extension columns in the second and third column, this is:
$$
matrix
0&4&5\
2&5&0\
4&0&1\
0&1&2\
2&2&3\
4&3&4\
0&4&5\
2&5&0\
4&0&1\
0&1&2
$$
Now let each team $i$ for $0le ile8$ play team $i+1$ in sport $i+5,%,6$. That takes care of the second and third columns, except for the game in sport $4$ for team $0$ and the game in sport $2$ for team $9$. These two games together with the ten missing games from the diagonal in the first column are four games each in the sports $0$, $2$ and $4$, and you can form two pairs for each of these sports in whatever way you like because none of the possible pairs have played a second game yet.
answered Jul 18 at 4:21
joriki
164k10180328
This doesn't schedule the matches into rounds, does it? (I've been trying to do it assuming that there were $12$ rounds, with all teams playing in each round, and no sport played more than once in a round. I know this isn't specified in the OP's question, but that's how I interpreted it.) I came up with a solution much like yours, but I can't see any systematic way of organizing the matches into rounds. I haven't even any intuition about whether it's hard or easy.
– saulspatz
Jul 18 at 5:18
@saulspatz: You're right, it doesn't. It hadn't occurred to me that this was intended, though now that you bring it up and I imagine the practical conditions of a bar sports tournament, it seems plausible that it was :-). I also don't see an easy way to do that. You can take the top right quarter of the table as one set of rounds, and the games of $i$ against $i+1$ also naturally fall into two rounds; but that would leave teams $0$ and $9$ to play their game in sport $0$ in a round in which teams $1$ and $2$ are already playing sport $0$. Looks more like a computer problem to me...
– joriki
Jul 18 at 5:39
I'm planning to try it by computer, but it's too late here to start on it tonight. Doing a bit of research on the web, I see that my approach comes down to finding a perfect matching on a $5-$uniform hypergraph with $60$ vertices, which sounds forbiding, as I see the general problem is NP-complete. I'll post an answer if I find anything interesting.
– saulspatz
Jul 18 at 5:48
2
@J.Mac: You should add that requirement to the question. It may be obvious to you since you're thinking of the practicalities of the tournament you're organizing, but, this being a math site, we solve problems according to the stated mathematical premises and don't (at least I don't) spend too much time thinking what other premises might be useful under real-world considerations. People won't read through all the comments to discover the new premise here; they should be able to understand the entire problem unambiguously just from the statement of the question.
– joriki
Jul 18 at 8:17
1
@J. Mac I don't think more teams will make things simpler, at least, not with the approach I have in mind. I'm planning on a computer program, and more teams will just make it run longer. If you get more teams, fine, you'll sell more beer, but don't recruit them specifically to simplify the problem. :-)
– saulspatz
Jul 18 at 13:38
 |Â
show 3 more comments
up vote
2
down vote
up vote
2
down vote
Label the teams $0$ to $9$ and the sports $0$ to $5$. Here $k,%,6$ denotes the remainder of $k$ modulo $6$.
First let each team $i$ play each other team $j$ in the sport $i+j,%,6$:
$$
matrix&1&2&3&4&5&0&1&2&3\
matrix1&&3&4&5&0&1&2&3&4\
matrix2&3&&5&0&1&2&3&4&5\
matrix3&4&5&&1&2&3&4&5&0\
matrix4&5&0&1&&3&4&5&0&1\
matrix5&0&1&2&3&&5&0&1&2\
matrix0&1&2&3&4&5&&1&2&3\
matrix1&2&3&4&5&0&1&&3&4\
matrix2&3&4&5&0&1&2&3&&5\
matrix3&4&5&0&1&2&3&4&5&\
$$
The three sports that each team is missing are the ones that would have been on the diagonal and in the two columns you'd get if you'd extend the table to the right. With the diagonal in the first column and the two extension columns in the second and third column, this is:
$$
matrix
0&4&5\
2&5&0\
4&0&1\
0&1&2\
2&2&3\
4&3&4\
0&4&5\
2&5&0\
4&0&1\
0&1&2
$$
Now let each team $i$ for $0le ile8$ play team $i+1$ in sport $i+5,%,6$. That takes care of the second and third columns, except for the game in sport $4$ for team $0$ and the game in sport $2$ for team $9$. These two games together with the ten missing games from the diagonal in the first column are four games each in the sports $0$, $2$ and $4$, and you can form two pairs for each of these sports in whatever way you like because none of the possible pairs have played a second game yet.
answered Jul 18 at 4:21
joriki
164k10180328
Label the teams $0$ to $9$ and the sports $0$ to $5$. Here $k,%,6$ denotes the remainder of $k$ modulo $6$.
First let each team $i$ play each other team $j$ in the sport $i+j,%,6$:
$$
matrix&1&2&3&4&5&0&1&2&3\
matrix1&&3&4&5&0&1&2&3&4\
matrix2&3&&5&0&1&2&3&4&5\
matrix3&4&5&&1&2&3&4&5&0\
matrix4&5&0&1&&3&4&5&0&1\
matrix5&0&1&2&3&&5&0&1&2\
matrix0&1&2&3&4&5&&1&2&3\
matrix1&2&3&4&5&0&1&&3&4\
matrix2&3&4&5&0&1&2&3&&5\
matrix3&4&5&0&1&2&3&4&5&\
$$
The three sports that each team is missing are the ones that would have been on the diagonal and in the two columns you'd get if you'd extend the table to the right. With the diagonal in the first column and the two extension columns in the second and third column, this is:
$$
matrix
0&4&5\
2&5&0\
4&0&1\
0&1&2\
2&2&3\
4&3&4\
0&4&5\
2&5&0\
4&0&1\
0&1&2
$$
Now let each team $i$ for $0le ile8$ play team $i+1$ in sport $i+5,%,6$. That takes care of the second and third columns, except for the game in sport $4$ for team $0$ and the game in sport $2$ for team $9$. These two games together with the ten missing games from the diagonal in the first column are four games each in the sports $0$, $2$ and $4$, and you can form two pairs for each of these sports in whatever way you like because none of the possible pairs have played a second game yet.
answered Jul 18 at 4:21
joriki
164k10180328
edited Jul 18 at 4:26
answered Jul 18 at 4:21
joriki
164k10180328
answered Jul 18 at 4:21
joriki
164k10180328
answered Jul 18 at 4:21
joriki
164k10180328
164k10180328
This doesn't schedule the matches into rounds, does it? (I've been trying to do it assuming that there were $12$ rounds, with all teams playing in each round, and no sport played more than once in a round. I know this isn't specified in the OP's question, but that's how I interpreted it.) I came up with a solution much like yours, but I can't see any systematic way of organizing the matches into rounds. I haven't even any intuition about whether it's hard or easy.
– saulspatz
Jul 18 at 5:18
@saulspatz: You're right, it doesn't. It hadn't occurred to me that this was intended, though now that you bring it up and I imagine the practical conditions of a bar sports tournament, it seems plausible that it was :-). I also don't see an easy way to do that. You can take the top right quarter of the table as one set of rounds, and the games of $i$ against $i+1$ also naturally fall into two rounds; but that would leave teams $0$ and $9$ to play their game in sport $0$ in a round in which teams $1$ and $2$ are already playing sport $0$. Looks more like a computer problem to me...
– joriki
Jul 18 at 5:39
I'm planning to try it by computer, but it's too late here to start on it tonight. Doing a bit of research on the web, I see that my approach comes down to finding a perfect matching on a $5-$uniform hypergraph with $60$ vertices, which sounds forbiding, as I see the general problem is NP-complete. I'll post an answer if I find anything interesting.
– saulspatz
Jul 18 at 5:48
2
@J.Mac: You should add that requirement to the question. It may be obvious to you since you're thinking of the practicalities of the tournament you're organizing, but, this being a math site, we solve problems according to the stated mathematical premises and don't (at least I don't) spend too much time thinking what other premises might be useful under real-world considerations. People won't read through all the comments to discover the new premise here; they should be able to understand the entire problem unambiguously just from the statement of the question.
– joriki
Jul 18 at 8:17
1
@J. Mac I don't think more teams will make things simpler, at least, not with the approach I have in mind. I'm planning on a computer program, and more teams will just make it run longer. If you get more teams, fine, you'll sell more beer, but don't recruit them specifically to simplify the problem. :-)
– saulspatz
Jul 18 at 13:38
 |Â
show 3 more comments
This doesn't schedule the matches into rounds, does it? (I've been trying to do it assuming that there were $12$ rounds, with all teams playing in each round, and no sport played more than once in a round. I know this isn't specified in the OP's question, but that's how I interpreted it.) I came up with a solution much like yours, but I can't see any systematic way of organizing the matches into rounds. I haven't even any intuition about whether it's hard or easy.
– saulspatz
Jul 18 at 5:18
@saulspatz: You're right, it doesn't. It hadn't occurred to me that this was intended, though now that you bring it up and I imagine the practical conditions of a bar sports tournament, it seems plausible that it was :-). I also don't see an easy way to do that. You can take the top right quarter of the table as one set of rounds, and the games of $i$ against $i+1$ also naturally fall into two rounds; but that would leave teams $0$ and $9$ to play their game in sport $0$ in a round in which teams $1$ and $2$ are already playing sport $0$. Looks more like a computer problem to me...
– joriki
Jul 18 at 5:39
I'm planning to try it by computer, but it's too late here to start on it tonight. Doing a bit of research on the web, I see that my approach comes down to finding a perfect matching on a $5-$uniform hypergraph with $60$ vertices, which sounds forbiding, as I see the general problem is NP-complete. I'll post an answer if I find anything interesting.
– saulspatz
Jul 18 at 5:48
2
@J.Mac: You should add that requirement to the question. It may be obvious to you since you're thinking of the practicalities of the tournament you're organizing, but, this being a math site, we solve problems according to the stated mathematical premises and don't (at least I don't) spend too much time thinking what other premises might be useful under real-world considerations. People won't read through all the comments to discover the new premise here; they should be able to understand the entire problem unambiguously just from the statement of the question.
– joriki
Jul 18 at 8:17
1
@J. Mac I don't think more teams will make things simpler, at least, not with the approach I have in mind. I'm planning on a computer program, and more teams will just make it run longer. If you get more teams, fine, you'll sell more beer, but don't recruit them specifically to simplify the problem. :-)
– saulspatz
Jul 18 at 13:38
This doesn't schedule the matches into rounds, does it? (I've been trying to do it assuming that there were $12$ rounds, with all teams playing in each round, and no sport played more than once in a round. I know this isn't specified in the OP's question, but that's how I interpreted it.) I came up with a solution much like yours, but I can't see any systematic way of organizing the matches into rounds. I haven't even any intuition about whether it's hard or easy.
– saulspatz
Jul 18 at 5:18
This doesn't schedule the matches into rounds, does it? (I've been trying to do it assuming that there were $12$ rounds, with all teams playing in each round, and no sport played more than once in a round. I know this isn't specified in the OP's question, but that's how I interpreted it.) I came up with a solution much like yours, but I can't see any systematic way of organizing the matches into rounds. I haven't even any intuition about whether it's hard or easy.
– saulspatz
Jul 18 at 5:18
@saulspatz: You're right, it doesn't. It hadn't occurred to me that this was intended, though now that you bring it up and I imagine the practical conditions of a bar sports tournament, it seems plausible that it was :-). I also don't see an easy way to do that. You can take the top right quarter of the table as one set of rounds, and the games of $i$ against $i+1$ also naturally fall into two rounds; but that would leave teams $0$ and $9$ to play their game in sport $0$ in a round in which teams $1$ and $2$ are already playing sport $0$. Looks more like a computer problem to me...
– joriki
Jul 18 at 5:39
@saulspatz: You're right, it doesn't. It hadn't occurred to me that this was intended, though now that you bring it up and I imagine the practical conditions of a bar sports tournament, it seems plausible that it was :-). I also don't see an easy way to do that. You can take the top right quarter of the table as one set of rounds, and the games of $i$ against $i+1$ also naturally fall into two rounds; but that would leave teams $0$ and $9$ to play their game in sport $0$ in a round in which teams $1$ and $2$ are already playing sport $0$. Looks more like a computer problem to me...
– joriki
Jul 18 at 5:39
I'm planning to try it by computer, but it's too late here to start on it tonight. Doing a bit of research on the web, I see that my approach comes down to finding a perfect matching on a $5-$uniform hypergraph with $60$ vertices, which sounds forbiding, as I see the general problem is NP-complete. I'll post an answer if I find anything interesting.
– saulspatz
Jul 18 at 5:48
I'm planning to try it by computer, but it's too late here to start on it tonight. Doing a bit of research on the web, I see that my approach comes down to finding a perfect matching on a $5-$uniform hypergraph with $60$ vertices, which sounds forbiding, as I see the general problem is NP-complete. I'll post an answer if I find anything interesting.
– saulspatz
Jul 18 at 5:48
2
2
@J.Mac: You should add that requirement to the question. It may be obvious to you since you're thinking of the practicalities of the tournament you're organizing, but, this being a math site, we solve problems according to the stated mathematical premises and don't (at least I don't) spend too much time thinking what other premises might be useful under real-world considerations. People won't read through all the comments to discover the new premise here; they should be able to understand the entire problem unambiguously just from the statement of the question.
– joriki
Jul 18 at 8:17
@J.Mac: You should add that requirement to the question. It may be obvious to you since you're thinking of the practicalities of the tournament you're organizing, but, this being a math site, we solve problems according to the stated mathematical premises and don't (at least I don't) spend too much time thinking what other premises might be useful under real-world considerations. People won't read through all the comments to discover the new premise here; they should be able to understand the entire problem unambiguously just from the statement of the question.
– joriki
Jul 18 at 8:17
1
1
@J. Mac I don't think more teams will make things simpler, at least, not with the approach I have in mind. I'm planning on a computer program, and more teams will just make it run longer. If you get more teams, fine, you'll sell more beer, but don't recruit them specifically to simplify the problem. :-)
– saulspatz
Jul 18 at 13:38
@J. Mac I don't think more teams will make things simpler, at least, not with the approach I have in mind. I'm planning on a computer program, and more teams will just make it run longer. If you get more teams, fine, you'll sell more beer, but don't recruit them specifically to simplify the problem. :-)
– saulspatz
Jul 18 at 13:38
 |Â
show 3 more comments
up vote
0
down vote
I've spent a good deal of time on this, and I haven't been able to do it, so in one sense, this isn't an answer at all, more of a progress report. On the other hand, someone may be able to suggest a modification to the method that will allow for solution. I tried it with both $10$ teams and $12$ teams, without success. I don't even have a viable approach in mind for an odd number of teams.
With $10$ teams each playing $12$ games, we will have $60$ matches. I determined a possible set of $60$ where each team played $9$ teams once and $3$ teams twice, and no two matches were identical. I then computed all possible rounds of $5$ matches chosen from among these $60,$ where a legitimate round includes all teams, and no game is played twice. With $10$ players, there were $172$ such rounds. Then I tried to choose $12$ rounds from among these $172$ that would partition the $60$ matches, but that was impossible. The result for $12$ teams was similar.
My program uses Knuth's dancing links algorithm for (generalized) set exact cover problems, so it's not apparent how to come up with some kind of approximate solution.
I've been wondering about trying different sets of $60$ matches, but there are so many isomorphisms! The program runs in a second or so, so trying lots of sets of matches isn't a concern, but of course, I'd like to generate non-isomorphic sets, if possible. At the moment, I don't see any quick way even to tell if two sets are isomorphic. (By isomorphic, I mean that one set of matches can be obtained from the other by permutation of the sports and of the teams.) I would welcome any suggestions about the isomorphism problem.
Failing this, there may be some acceptable relaxation of the conditions.
One thing that occurs to me is to go for as many full rounds as possible, and then hope that there aren't too many conflicts at the end. For example, suppose we could go for $11$ rounds, but not $12$. If the last $5$ games were all pool, that would be a problem, but if two were pool and the remaining ones were different games, that wouldn't be so bad. I'd like to know the OP's opinion of this approach.
EDIT
I modified the program to keep track of the maximum number of compatible rounds, and it was only $5$. Very discouraging. It is, however, possible to do this for an $8-$team tournament.
Round 1
T0 vs T2 at table tennis
T3 vs T6 at beer pong
T1 vs T4 at darts
T7 vs T5 at cornhole
Round 2
T0 vs T1 at beer pong
T4 vs T2 at table tennis
T6 vs T7 at pool
T5 vs T3 at foosball
Round 3
T0 vs T4 at foosball
T7 vs T3 at darts
T2 vs T5 at beer pong
T1 vs T6 at cornhole
Round 4
T0 vs T3 at table tennis
T7 vs T5 at darts
T4 vs T2 at pool
T1 vs T6 at beer pong
Round 5
T0 vs T4 at pool
T5 vs T6 at table tennis
T1 vs T2 at darts
T7 vs T3 at foosball
Round 6
T0 vs T6 at darts
T2 vs T7 at beer pong
T1 vs T4 at cornhole
T5 vs T3 at pool
Round 7
T0 vs T6 at cornhole
T4 vs T7 at table tennis
T2 vs T3 at darts
T5 vs T1 at pool
Round 8
T0 vs T5 at foosball
T7 vs T1 at pool
T6 vs T4 at darts
T2 vs T3 at cornhole
Round 9
T0 vs T3 at pool
T6 vs T7 at table tennis
T4 vs T5 at beer pong
T1 vs T2 at foosball
Round 10
T0 vs T7 at beer pong
T3 vs T1 at table tennis
T2 vs T5 at cornhole
T6 vs T4 at foosball
Round 11
T0 vs T7 at cornhole
T3 vs T4 at beer pong
T6 vs T2 at foosball
T5 vs T1 at table tennis
Round 12
T0 vs T5 at darts
T3 vs T4 at cornhole
T6 vs T2 at pool
T7 vs T1 at foosball
Here each team plays $5$ teams twice and $2$ teams once.
answered Jul 20 at 9:38
saulspatz
10.7k21323
@J.Mac While it doesn't solve the mathematical problem, it occurs to me that if you can get 12 teams, you can have two flights of 6 teams each. Each team would play 3 teams twice and 2 teams 3 times. It's easy to arrange that the two flights would never be playing the same game in the same round.
– saulspatz
Jul 20 at 11:34
add a comment |Â
up vote
0
down vote
I've spent a good deal of time on this, and I haven't been able to do it, so in one sense, this isn't an answer at all, more of a progress report. On the other hand, someone may be able to suggest a modification to the method that will allow for solution. I tried it with both $10$ teams and $12$ teams, without success. I don't even have a viable approach in mind for an odd number of teams.
With $10$ teams each playing $12$ games, we will have $60$ matches. I determined a possible set of $60$ where each team played $9$ teams once and $3$ teams twice, and no two matches were identical. I then computed all possible rounds of $5$ matches chosen from among these $60,$ where a legitimate round includes all teams, and no game is played twice. With $10$ players, there were $172$ such rounds. Then I tried to choose $12$ rounds from among these $172$ that would partition the $60$ matches, but that was impossible. The result for $12$ teams was similar.
My program uses Knuth's dancing links algorithm for (generalized) set exact cover problems, so it's not apparent how to come up with some kind of approximate solution.
I've been wondering about trying different sets of $60$ matches, but there are so many isomorphisms! The program runs in a second or so, so trying lots of sets of matches isn't a concern, but of course, I'd like to generate non-isomorphic sets, if possible. At the moment, I don't see any quick way even to tell if two sets are isomorphic. (By isomorphic, I mean that one set of matches can be obtained from the other by permutation of the sports and of the teams.) I would welcome any suggestions about the isomorphism problem.
Failing this, there may be some acceptable relaxation of the conditions.
One thing that occurs to me is to go for as many full rounds as possible, and then hope that there aren't too many conflicts at the end. For example, suppose we could go for $11$ rounds, but not $12$. If the last $5$ games were all pool, that would be a problem, but if two were pool and the remaining ones were different games, that wouldn't be so bad. I'd like to know the OP's opinion of this approach.
EDIT
I modified the program to keep track of the maximum number of compatible rounds, and it was only $5$. Very discouraging. It is, however, possible to do this for an $8-$team tournament.
Round 1
T0 vs T2 at table tennis
T3 vs T6 at beer pong
T1 vs T4 at darts
T7 vs T5 at cornhole
Round 2
T0 vs T1 at beer pong
T4 vs T2 at table tennis
T6 vs T7 at pool
T5 vs T3 at foosball
Round 3
T0 vs T4 at foosball
T7 vs T3 at darts
T2 vs T5 at beer pong
T1 vs T6 at cornhole
Round 4
T0 vs T3 at table tennis
T7 vs T5 at darts
T4 vs T2 at pool
T1 vs T6 at beer pong
Round 5
T0 vs T4 at pool
T5 vs T6 at table tennis
T1 vs T2 at darts
T7 vs T3 at foosball
Round 6
T0 vs T6 at darts
T2 vs T7 at beer pong
T1 vs T4 at cornhole
T5 vs T3 at pool
Round 7
T0 vs T6 at cornhole
T4 vs T7 at table tennis
T2 vs T3 at darts
T5 vs T1 at pool
Round 8
T0 vs T5 at foosball
T7 vs T1 at pool
T6 vs T4 at darts
T2 vs T3 at cornhole
Round 9
T0 vs T3 at pool
T6 vs T7 at table tennis
T4 vs T5 at beer pong
T1 vs T2 at foosball
Round 10
T0 vs T7 at beer pong
T3 vs T1 at table tennis
T2 vs T5 at cornhole
T6 vs T4 at foosball
Round 11
T0 vs T7 at cornhole
T3 vs T4 at beer pong
T6 vs T2 at foosball
T5 vs T1 at table tennis
Round 12
T0 vs T5 at darts
T3 vs T4 at cornhole
T6 vs T2 at pool
T7 vs T1 at foosball
Here each team plays $5$ teams twice and $2$ teams once.
answered Jul 20 at 9:38
saulspatz
10.7k21323
@J.Mac While it doesn't solve the mathematical problem, it occurs to me that if you can get 12 teams, you can have two flights of 6 teams each. Each team would play 3 teams twice and 2 teams 3 times. It's easy to arrange that the two flights would never be playing the same game in the same round.
– saulspatz
Jul 20 at 11:34
add a comment |Â
up vote
0
down vote
up vote
0
down vote
I've spent a good deal of time on this, and I haven't been able to do it, so in one sense, this isn't an answer at all, more of a progress report. On the other hand, someone may be able to suggest a modification to the method that will allow for solution. I tried it with both $10$ teams and $12$ teams, without success. I don't even have a viable approach in mind for an odd number of teams.
With $10$ teams each playing $12$ games, we will have $60$ matches. I determined a possible set of $60$ where each team played $9$ teams once and $3$ teams twice, and no two matches were identical. I then computed all possible rounds of $5$ matches chosen from among these $60,$ where a legitimate round includes all teams, and no game is played twice. With $10$ players, there were $172$ such rounds. Then I tried to choose $12$ rounds from among these $172$ that would partition the $60$ matches, but that was impossible. The result for $12$ teams was similar.
My program uses Knuth's dancing links algorithm for (generalized) set exact cover problems, so it's not apparent how to come up with some kind of approximate solution.
I've been wondering about trying different sets of $60$ matches, but there are so many isomorphisms! The program runs in a second or so, so trying lots of sets of matches isn't a concern, but of course, I'd like to generate non-isomorphic sets, if possible. At the moment, I don't see any quick way even to tell if two sets are isomorphic. (By isomorphic, I mean that one set of matches can be obtained from the other by permutation of the sports and of the teams.) I would welcome any suggestions about the isomorphism problem.
Failing this, there may be some acceptable relaxation of the conditions.
One thing that occurs to me is to go for as many full rounds as possible, and then hope that there aren't too many conflicts at the end. For example, suppose we could go for $11$ rounds, but not $12$. If the last $5$ games were all pool, that would be a problem, but if two were pool and the remaining ones were different games, that wouldn't be so bad. I'd like to know the OP's opinion of this approach.
EDIT
I modified the program to keep track of the maximum number of compatible rounds, and it was only $5$. Very discouraging. It is, however, possible to do this for an $8-$team tournament.
Round 1
T0 vs T2 at table tennis
T3 vs T6 at beer pong
T1 vs T4 at darts
T7 vs T5 at cornhole
Round 2
T0 vs T1 at beer pong
T4 vs T2 at table tennis
T6 vs T7 at pool
T5 vs T3 at foosball
Round 3
T0 vs T4 at foosball
T7 vs T3 at darts
T2 vs T5 at beer pong
T1 vs T6 at cornhole
Round 4
T0 vs T3 at table tennis
T7 vs T5 at darts
T4 vs T2 at pool
T1 vs T6 at beer pong
Round 5
T0 vs T4 at pool
T5 vs T6 at table tennis
T1 vs T2 at darts
T7 vs T3 at foosball
Round 6
T0 vs T6 at darts
T2 vs T7 at beer pong
T1 vs T4 at cornhole
T5 vs T3 at pool
Round 7
T0 vs T6 at cornhole
T4 vs T7 at table tennis
T2 vs T3 at darts
T5 vs T1 at pool
Round 8
T0 vs T5 at foosball
T7 vs T1 at pool
T6 vs T4 at darts
T2 vs T3 at cornhole
Round 9
T0 vs T3 at pool
T6 vs T7 at table tennis
T4 vs T5 at beer pong
T1 vs T2 at foosball
Round 10
T0 vs T7 at beer pong
T3 vs T1 at table tennis
T2 vs T5 at cornhole
T6 vs T4 at foosball
Round 11
T0 vs T7 at cornhole
T3 vs T4 at beer pong
T6 vs T2 at foosball
T5 vs T1 at table tennis
Round 12
T0 vs T5 at darts
T3 vs T4 at cornhole
T6 vs T2 at pool
T7 vs T1 at foosball
Here each team plays $5$ teams twice and $2$ teams once.
answered Jul 20 at 9:38
saulspatz
10.7k21323
I've spent a good deal of time on this, and I haven't been able to do it, so in one sense, this isn't an answer at all, more of a progress report. On the other hand, someone may be able to suggest a modification to the method that will allow for solution. I tried it with both $10$ teams and $12$ teams, without success. I don't even have a viable approach in mind for an odd number of teams.
With $10$ teams each playing $12$ games, we will have $60$ matches. I determined a possible set of $60$ where each team played $9$ teams once and $3$ teams twice, and no two matches were identical. I then computed all possible rounds of $5$ matches chosen from among these $60,$ where a legitimate round includes all teams, and no game is played twice. With $10$ players, there were $172$ such rounds. Then I tried to choose $12$ rounds from among these $172$ that would partition the $60$ matches, but that was impossible. The result for $12$ teams was similar.
My program uses Knuth's dancing links algorithm for (generalized) set exact cover problems, so it's not apparent how to come up with some kind of approximate solution.
I've been wondering about trying different sets of $60$ matches, but there are so many isomorphisms! The program runs in a second or so, so trying lots of sets of matches isn't a concern, but of course, I'd like to generate non-isomorphic sets, if possible. At the moment, I don't see any quick way even to tell if two sets are isomorphic. (By isomorphic, I mean that one set of matches can be obtained from the other by permutation of the sports and of the teams.) I would welcome any suggestions about the isomorphism problem.
Failing this, there may be some acceptable relaxation of the conditions.
One thing that occurs to me is to go for as many full rounds as possible, and then hope that there aren't too many conflicts at the end. For example, suppose we could go for $11$ rounds, but not $12$. If the last $5$ games were all pool, that would be a problem, but if two were pool and the remaining ones were different games, that wouldn't be so bad. I'd like to know the OP's opinion of this approach.
EDIT
I modified the program to keep track of the maximum number of compatible rounds, and it was only $5$. Very discouraging. It is, however, possible to do this for an $8-$team tournament.
Round 1
T0 vs T2 at table tennis
T3 vs T6 at beer pong
T1 vs T4 at darts
T7 vs T5 at cornhole
Round 2
T0 vs T1 at beer pong
T4 vs T2 at table tennis
T6 vs T7 at pool
T5 vs T3 at foosball
Round 3
T0 vs T4 at foosball
T7 vs T3 at darts
T2 vs T5 at beer pong
T1 vs T6 at cornhole
Round 4
T0 vs T3 at table tennis
T7 vs T5 at darts
T4 vs T2 at pool
T1 vs T6 at beer pong
Round 5
T0 vs T4 at pool
T5 vs T6 at table tennis
T1 vs T2 at darts
T7 vs T3 at foosball
Round 6
T0 vs T6 at darts
T2 vs T7 at beer pong
T1 vs T4 at cornhole
T5 vs T3 at pool
Round 7
T0 vs T6 at cornhole
T4 vs T7 at table tennis
T2 vs T3 at darts
T5 vs T1 at pool
Round 8
T0 vs T5 at foosball
T7 vs T1 at pool
T6 vs T4 at darts
T2 vs T3 at cornhole
Round 9
T0 vs T3 at pool
T6 vs T7 at table tennis
T4 vs T5 at beer pong
T1 vs T2 at foosball
Round 10
T0 vs T7 at beer pong
T3 vs T1 at table tennis
T2 vs T5 at cornhole
T6 vs T4 at foosball
Round 11
T0 vs T7 at cornhole
T3 vs T4 at beer pong
T6 vs T2 at foosball
T5 vs T1 at table tennis
Round 12
T0 vs T5 at darts
T3 vs T4 at cornhole
T6 vs T2 at pool
T7 vs T1 at foosball
Here each team plays $5$ teams twice and $2$ teams once.
answered Jul 20 at 9:38
saulspatz
10.7k21323
edited Jul 20 at 11:19
answered Jul 20 at 9:38
saulspatz
10.7k21323
answered Jul 20 at 9:38
saulspatz
10.7k21323
answered Jul 20 at 9:38
saulspatz
10.7k21323
10.7k21323
@J.Mac While it doesn't solve the mathematical problem, it occurs to me that if you can get 12 teams, you can have two flights of 6 teams each. Each team would play 3 teams twice and 2 teams 3 times. It's easy to arrange that the two flights would never be playing the same game in the same round.
– saulspatz
Jul 20 at 11:34
add a comment |Â
@J.Mac While it doesn't solve the mathematical problem, it occurs to me that if you can get 12 teams, you can have two flights of 6 teams each. Each team would play 3 teams twice and 2 teams 3 times. It's easy to arrange that the two flights would never be playing the same game in the same round.
– saulspatz
Jul 20 at 11:34
@J.Mac While it doesn't solve the mathematical problem, it occurs to me that if you can get 12 teams, you can have two flights of 6 teams each. Each team would play 3 teams twice and 2 teams 3 times. It's easy to arrange that the two flights would never be playing the same game in the same round.
– saulspatz
Jul 20 at 11:34
@J.Mac While it doesn't solve the mathematical problem, it occurs to me that if you can get 12 teams, you can have two flights of 6 teams each. Each team would play 3 teams twice and 2 teams 3 times. It's easy to arrange that the two flights would never be playing the same game in the same round.
– saulspatz
Jul 20 at 11:34
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855142%2fmulti-sports-tournament-10-teams-6-sports-simultaneous%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Let n be the number of teams, if n is even, n/2 vs. n/2 for 12 rounds. If n is odd, (n+1)/2 vs (n-1/2) for 12 rounds. Make sense?
– Nick
Jul 18 at 3:17
@Nick This doesn't really address the OP's problem. How to ensure that each team plays each game twice, while minimizing the number of times the same teams meet.
– saulspatz
Jul 18 at 3:26
Since each team plays $12$ times, I imagine you would like to get in done in $12$ rounds. Am I correct in assuming that each event (foosball, pool, etc.) can only be played once in a given round?
– saulspatz
Jul 18 at 3:35
@saulspatz This is a question about bracketing. It's taught in sports theory and such. 10 Team round robin would seem like a good strategy here but it doesn't account for the double play.
– Nick
Jul 18 at 4:17
2
@Nick It's easy to find a grouping where each team plays $6$ teams once and $3$ teams twice; just run the circle method for $3$ more rounds. Then in the first two rounds, every match is pool, in the next two, every match is darts, and so on. Now we have satisfied the requirements as to opponents and games, but there's only one pool table, say. We somehow have to distribute these matches in $12$ rounds so that no sport is played more than once in a single round, or at least, that's what I'm assuming. I don't know how bar sports tournaments work, so I could be all wrong about that.
– saulspatz
Jul 18 at 5:11