Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are:

  • 14 teams $t$ numbered from 0 to 13
  • 13 different games $g$ numbered from 0 to 12
  • 13 rounds $r$ numbered from 0 to 12

I want to make a planning such that:

  • each team plays against each other team
  • each team plays all 13 games
  • 2 times the same game during one round is not allowed

Is there an efficient way to construct such a planning?

Is there a way to define a "simple" function $f(t,r)$ that returns the game $g $ played by team t in round r.

I am more interested in how to approach the problem than in the actual solution.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

Yes, the bridge players call this a Howell movement. You can see this particular example at this site or this site. Your games are the pairs of boards. Basically 13 of the pairs (your teams) move one direction around the room (the other is stationary) and the boards move the other direction around the room. It gets more complicated if the number of teams is 4n or 4n-1.

You can think of seating the teams at a long table. The team at one end is stationary and the rest rotate. Each team plays the team across the table from it. The games rotate around the matches, in the opposite direction from the teams, with a pile sitting out not being played (only 7 are played each round).

Note your games and rounds should be numbered 0 to 12 or 1 to 13.

share|improve this answer

Using the rotation-with-one-fixed-player method in Ross Millikan's answer or in http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm I believe we can write an explicit function to generate these pairings.

I started by trying the smaller case of $8$ teams. Consider the following starting configuration:

7 6 5 4
0 1 2 3

Holding team $7$ fixed and rotating everyone else clockwise, we find the following pairing list:

             Round number (r)
           0  1  2  3  4  5  6
           -------------------
        0| 7  2  4  6  1  3  5
        1| 6  7  3  5  0  2  4
        2| 5  0  7  4  6  1  3
 Team   3| 4  6  1  7  5  0  2
  (t)   4| 3  5  0  2  7  6  1
        5| 2  4  6  1  3  7  0
        6| 1  3  5  0  2  4  7
        7| 0  1  2  3  4  5  6

The pattern is evident. Team $7$'s opponent is simply $r$. For everyone else, the round $0$ opponent is $7-t$ and the following rounds the opponent increments by $2$ each time (with the exception of the round which would by that pattern have a team play itself, during which the team plays team $7$ instead).

The function is:

$$f(t, r, n) = \left\{ \begin{array}{lr} n - 1 & : t = r\\ r & : t = n - 1\\ (2*r - t)\bmod{(n-1)} : \hspace{10 mm} t\neq r\hspace{4 mm} \And \hspace{4 mm} t\neq n - 1\\ \end{array} \right.$$

where $t$ is team number, $r$ is round number, and $n$ is the number of teams. The function is defined for positive even integer $n$, nonnegative integer $t$ where $t<n$, and nonnegative integer $r$ where $r<n-1$.

share|improve this answer
    
The problem is that you also need to schedule the games. The usual approach is to have them rotate the other way around the room, but with a multiple of 4 teams the team meets the same game half way through. Bridge clubs deal with this by having a double shift half way through and leaving one combination unplayed. That is why it works well for 4n+1 or 4n+2 teams, not so well for 4n or 4n+3. –  Ross Millikan Jul 27 '12 at 20:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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