1
$\begingroup$

So, my school is organizing a charity event for some children who are going to be split into teams and play minigames against each other. Naturally, we want all the teams to face every other team and ensure that each team plays every single minigame only once.

We have decided that there will be 12 teams (even number, so it should work well) as well as 6 different minigames.

I have tried to find a website/tournament scheduling software, but none are capable of ensuring each team plays a different minigame/at a different location.

Here is my attempted program/roster: http://tournamentscheduler.net/schedule/Mzg1OTk0ODE5MQ , however, not every team plays every minigame.

NOTE: The whole day is about 3 hours, so it isn't necessary that each team plays every other team, but it is essential that each team plays at every minigame station against different teams.

Thank you so much :) I look forward to any responses I will receive.

Kind Regards

Joshua Lochner

$\endgroup$
  • 1
    $\begingroup$ So each team plays exactly $6$ games total? $\endgroup$ – Chas Brown Jan 4 '17 at 22:20
  • $\begingroup$ Yes :) one at each minigame station $\endgroup$ – Joshua Lochner Jan 4 '17 at 22:23
  • $\begingroup$ @ChasBrown If each team plays exactly $6$ games total, then it's not possible for 'all the teams to face every other team'. That said, I admit the question as a whole is a little too vague. $\endgroup$ – Fimpellizieri Jan 4 '17 at 23:57
2
$\begingroup$

I don't think this can work if you have an even number of games. (Wrong: see edit below.) But if you have 5 or 7 games (with 10 or 14 teams), then Chas Brown's solution works perfectly. Here is the seating plan for 5 games (the game stations are named A through E, and the teams are numbered 1 to 10):

          A  B  C  D  E
          -------------
Round 1:  1  2  3  4  5
          6  7  8  9  10

Round 2:  2  3  4  5  1
          10 6  7  8  9


Round 3:  3  4  5  1  2
          9  10 6  7  8

Round 4:  4  5  1  2  3
          8  9  10 6  7

Round 5:  5  1  2  3  4
          7  8  9  10 6

This is the problem of designing pairings for duplicate bridge tournaments, where instead of different games, we have different deals. See this link for a discussion of the different strategies; and note that the Mitchell Movement with an even number of tables ends up with each pair having to skip one of the deals.

Edited to add: Especially Lime comments that a "perfect schedule" is possible when the number of games is a multiple of four (the so-called double-weave Mitchell Movement). Here is an example with eight games:

          A  B  C  D  E  F  G  H                A  B  C  D  E  F  G  H
          ----------------------                ----------------------
Round 1   1  2  3  4  5  6  7  8      Round 2   2  1  4  3  6  5  8  7
          9  10 11 12 13 14 15 16               16 11 10 13 12 15 14 9

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

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

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

Edited again to add: As Chas Brown points out in the comments, this problem is just another disguise for Graeco-Latin squares, which means we can construct perfect schedules for all sizes except $2$ and $6$. This paper by D.A. Preece and B.J. Vowden has examples of $10\times 10$ Graeco-Latin squares.

$\endgroup$
  • $\begingroup$ However in the standard Mitchell you want each pair playing each deal once, so have lots of deals. In the OP's case there are only six stations for the teams to play, so if each plays eleven games they will play some games twice. That was acceptable as long as they each play each game at least once. $\endgroup$ – Ross Millikan Jan 5 '17 at 1:01
  • $\begingroup$ @RossMillikan: The question is inconsistent on this. I went with the version where "each team plays every single minigame only once". $\endgroup$ – TonyK Jan 5 '17 at 1:10
  • $\begingroup$ I'm guessing that you are correct TonyK that it is possible for $n$ rounds, $n$ mini-games, and $2n$ teams if and only if $n$ is odd. I'm wondering if there is some easy parity consideration that makes it clear why that is the case (mostly, the 'only if' part). $\endgroup$ – Chas Brown Jan 5 '17 at 1:57
  • 1
    $\begingroup$ The discussion of Mitchell movements in the linked article is incomplete. Where the number of tables is a multiple of 4 it is possible to play a double-weave Mitchell, and this would work for 16 teams and 8 minigames. (See post #6 of this discussion for a description.) $\endgroup$ – Especially Lime Jan 5 '17 at 10:01
  • 1
    $\begingroup$ I don't know bridge; but I believe this problem is quite similar to the the Graeco-Latin square problem, and so is solvable unless $n=2$ or $n=6$ (although I doubt there's a simple 'ultra-Mitchell' approach for solutions for $n$ neither odd nor divisible by $4$!) $\endgroup$ – Chas Brown Jan 6 '17 at 2:19
0
$\begingroup$

(Ooops! BZZZT! Wrong...!!! Please un-vote me! In my 'solution' team 1 plays team 7 twice...)

Imagine seating the teams at a long table, with six seats on either side. Players on opposing seats will play games A, B, C, D, E, and F.

Start by seating teams 1-6 on one side of the table, and 7-12 on the other side.

After each round, each team player moves to the seat to THEIR right; with the person on the rightmost ends switching to the (now empty) leftmost seat on the SAME side of the table.

Then: each team plays each of the six games once; and no team plays the same opponent team twice. (I think that's what you want!)

$\endgroup$
  • $\begingroup$ Thank you very much for your comment :)... I'm sorry if it is too much to ask, but what would the final roster be? I am going to use this method to generate the roster, but if you could possibly just show the final output that would be absolutely amazing :). Thanks again $\endgroup$ – Joshua Lochner Jan 4 '17 at 22:45
  • 1
    $\begingroup$ Give me a moment... it's too much typing, so writing a quick python script. $\endgroup$ – Chas Brown Jan 4 '17 at 22:46
  • $\begingroup$ Haha thank you! You are so helpful :) $\endgroup$ – Joshua Lochner Jan 4 '17 at 22:46
  • $\begingroup$ Ahhh haha, any other solutions? :D $\endgroup$ – Joshua Lochner Jan 4 '17 at 22:55
  • $\begingroup$ Perhaps not... still looking. $\endgroup$ – Chas Brown Jan 4 '17 at 22:57
0
$\begingroup$

Okay, so it looks like the answer to your problem is probably: it can't be done, because there are $6$ mini-games.

The problem you pose is close to (but not exactly the same as: see below) the problem of Graeco-Latin squares. For purposes of finding a solution, each of your $2n$ teams is assigned to a 'League': $n$ teams are in the 'Latin' league (and given arbitrary names $A, B, C$, etc.); while the other $n$ teams are in the 'Graeco' League (and given arbitrary names $\alpha, \beta, \gamma,$ etc.). In my failed solution, one side of the table was the 'Latin' league, and the other was the 'Graeco' league.

Now, if it is possible to make an $n \times n$ Graeco-Latin square, then you have your tournament: each row is a round, each cell is a pair of teams that will compete, and the column identifies which mini-game they should play in that round.

As the Wikipedia article notes, this is always possible if $n \neq 2$ or $n \neq 6$.

Now there is a difference between the problem of Graeco-Latin squares and your actual problem: in the former, no two teams from the same 'League' can play against each other; whereas you don't have two leagues, so potentially there might be solutions to your problem that don't also work as a Graeco-Latin square (because you might have a 'cell' that contains two Latin or two Graeco letters in it).

For $n=2$, this doesn't matter; it's pretty easy to see that there are no solutions in any case.

That leaves the problem of $n=6$, which unfortunately is your case! :). I haven't been able to determine if there is a proof that if a solution exists, it must then also be a G-L square (after suitable partitioning of the teams into two groups). Looking at that now...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.