5
$\begingroup$

Consider the following tournament:

There are 12 teams, 6 disciplines and 6 rounds, each round and each event happens simultaneously. Is it possible to create a tournament such that no team does the same discipline twice nor meets a team they have already played. There is no reward for winning teams meeting winning teams.

This is a real live problem which bothers me quite a bit. It seems impossible (mostly due to trial and error and some trying to apply math) but I cannot prove it. Given it can not be solved I would of course like to see the argument. I do not know if such math exists, but some kind of formalised best tournament would also be interesting.

Edit: An example could be (assuming teams 1 to 12 are just numerated)

Round 1: Soccer 1 vs 2, Baseball 3 vs 4, Basketball 5 vs 6, Hockey 7 vs 8, Ultimate 9 vs 10, Football 11 vs 12

Round 2: Soccer 3 vs 6, Baseball 5 vs 8, Basketball 7 vs 10, Hockey 9 vs 12, Ultimate 11 vs 2, Football 1 vs 4 and so forth.

So the disciplines should preferably be simultaneous. Sorry for not writing that explicitly the first time.

$\endgroup$
  • $\begingroup$ I'm not familiar with the term "discipline" being used here. Perhaps it is an arbitrary designation, as the six rounds in which a team competes are not simultaneous (a team can only compete against one opponent at a time, correct?). $\endgroup$ – hardmath Aug 11 '14 at 1:01
  • $\begingroup$ Hmm i actually do not understand your description. An example could be (assuming teams 1 to 12 are just numerated) Round 1: Soccer 1 vs 2, Baseball 3 vs 4, Basketball 5 vs 6, Hockey 7 vs 8, Ultimate 9 vs 10, Football 11 vs 12 Round 2: Soccer 3 vs 6, Baseball 5 vs 8, Basketball 7 vs 10, Hockey 9 vs 12, Ultimate 11 vs 2, Football 1 vs 4 and so forth, they are indeed simultatnous. $\endgroup$ – Henrik Aug 11 '14 at 5:45
  • 1
    $\begingroup$ Generalising for 2n teams, n sports, n rounds: it's easy to draw up a table when n is odd. A little playing around will convince one it can't be done for n = 2 and 4 though. $\endgroup$ – Neil W Aug 11 '14 at 6:04
  • $\begingroup$ Thanks for the clarification, discipline = sport. Each round is conducted with all six sports being contested simultaneously. The same problem was posed previously, without a successful solution or proof of impossibility (partly because of the difficulty in explaining conditions). $\endgroup$ – hardmath Aug 11 '14 at 10:59
  • $\begingroup$ Apologies, you can schedule the n=4 case. $\endgroup$ – Neil W Aug 11 '14 at 13:10
3
$\begingroup$

I found a solution posted by Ian Wakeling on a Round Robin Tournament bulletin board in 2008.

I checked a bit by sight and then formatted it as Prolog facts to do a computer check:

/*
    Search for 12 team tournament with 6 rounds and 6 venues
    s.t. each team plays once in each round (against one opponent)
    and each venue is used once in each round.
*/

teams([a,b,c,d,e,f,g,h,i,j,k,l]).
rounds([1,2,3,4,5,6]).
venues([1,2,3,4,5,6]).

p(a,g,1,1). p(b,h,1,2). p(c,i,1,3). p(d,l,1,4). p(e,k,1,5). p(f,j,1,6). 
p(b,c,2,1). p(j,g,2,2). p(d,e,2,3). p(h,i,2,4). p(f,a,2,5). p(l,k,2,6). 
p(k,j,3,1). p(c,d,3,2). p(g,h,3,3). p(e,f,3,4). p(i,l,3,5). p(a,b,3,6). 
p(e,l,4,1). p(f,k,4,2). p(a,j,4,3). p(b,g,4,4). p(c,h,4,5). p(d,i,4,6). 
p(f,i,5,1). p(a,l,5,2). p(b,k,5,3). p(c,j,5,4). p(d,g,5,5). p(e,h,5,6). 
p(d,h,6,1). p(e,i,6,2). p(f,l,6,3). p(a,k,6,4). p(b,j,6,5). p(c,g,6,6). 

As required, each team plays once in each Round and once in each Venue, and each team has six distinct opponents. Naturally the roles of Round and Venue ("discipline") are interchangeable.

As the linked BB post observes, such a schedule is a Howell design $H(n,2n)$ for $n=6$. Alternatively it can be identified as a SOMA$(2,n)$, an acronym for "simple orthogonal multi-arrays" according to the history recounted in this 2006 dissertation by John Arhin. The similarity to mutually orthogonal latin squares is not coincidental in that MOLS are useful in constructing SOMA.

Indeed the existence of $H(n,2n)$ designs for all $n > 2$ is established by the above example together with the construction of such designs by combining (overlaying) two mutually orthogonal latin squares (MOLS) of size $n\times n$ with disjoint symbol sets (so pairs of symbols from $2n$ possibilities). This is an observation in Hung and Mendelsohn (1974), On Howell designs, using the fact that MOLS pairs exist for all $n \neq 2,6$. As Neil commented on the Question, there is no $H(2,4)$, but the example here shows, $H(6,12)$ designs exist despite the nonexistence of a pair of MOLS of order $n=6$.

$\endgroup$
  • $\begingroup$ Wow! Great thanks! $\endgroup$ – Henrik Aug 12 '14 at 6:05
  • $\begingroup$ That A- L / 1-6 grid is just what I have been looking for. Could you please do a draw for 14 teams/7 games? $\endgroup$ – Pamela Dec 30 '17 at 6:34
  • 1
    $\begingroup$ @Pamela I assumed this was intended to be a comment to Hardmath's answer, so I moved it there. I think that it may be better to post it as a new question. It may well be that solutions to 12/6 vs. 14/7 are totally different (or may be not, I'm not an expert). Also, that way all users will see your question, and you may get an answer faster. Do spend a little while studying our site norms so that you can formulate the question in a way that meets them. Have fun! $\endgroup$ – Jyrki Lahtonen Dec 30 '17 at 8:24
  • $\begingroup$ @Pamela: The schedule for 14 teams (playing 7 games) can be drawn up using two mutually orthogonal latin squares of order 7 (using disjoint symbol sets for the two squares). So while (as Jyrki suspects) the 12/6 solution doesn't help us get the 14/7 solution, the latter is comparatively easy to work out. I'll look for a separate Question from you. $\endgroup$ – hardmath Dec 30 '17 at 13:09
1
$\begingroup$

Assuming that in a round the twelve teams are separated into six pairs, then it is possible.

One way is simply to have every pair play the same discipline on the same round, with a different discipline in play each round. Then you rotate the team pairings so each team is match to a different partner.

$$\begin{array}{ccccccccccc} 1 & \rightarrow & 2 & \rightarrow & 3 & \rightarrow & 4 & \rightarrow & 5 & \rightarrow & 6 \\ \uparrow &&&&&&&&&&\downarrow \\ 12 & \leftarrow & 11 & \leftarrow & 10 & \leftarrow & 9 & \leftarrow & 8 & \leftarrow & 7 \end{array}$$

$\endgroup$
  • $\begingroup$ Hi Graham. Thanks for your answer, I am sorry to say that I do not understand the description. All 6 disciplines would preferably be played every time. $\endgroup$ – Henrik Aug 11 '14 at 5:46

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.