Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Linear Algebra - Basic Structures - Groups and Fields

Tournaments in Groups

[previous page] [next page] [table of contents][page overview]
Imagine you have to organize a ,,round robin`` tournament among 9 teams. The tournament is to be held in Stuttgart, Munich and Berlin on 4 fixed dates. Thus, for each tournament date you have to form 3 groups consisting of 3 teams. The teams of each group will have their matches in one of the 3 towns. When forming the $ 3\cdot 4$ groups, the difficulty consists in avoiding 'overlappings'. That is, any two of the nine teams should have exactly one meeting.

The problem can be described in mathematical terms as follows: Find $ 3$-element sets

$\displaystyle S_{0,k}\cup S_{1,k} \cup S_{2,k} = \{1,\ldots,9\},\quad k=0,\ldots,3\, , $

so that the intersection of two of them contains at most one element. By this condition we avoid that sets corresponding to groups on different tournament dates contain a common pair of teams.

The sets $ S_{j,k}$ can be constructed by means of the prime field $ \mathbb{Z}_3$. For this purpose we identify the team numbers $ 1,\ldots,9$ with the points

$\displaystyle (\alpha,\beta),\quad \alpha,\,\beta\in\mathbb{Z}_3 $

of a $ 9$-element ,,finite plane`` and we identify the sets with lines in this plane:
$\displaystyle S_{j,k}$ $\displaystyle =$ $\displaystyle \{(\alpha,k*\alpha+j\,$mod$\displaystyle \,3):\ \alpha = 0,1,2\},\quad ($lines with slope$\displaystyle \ k=0,1,2)$  
$\displaystyle S_{j,3}$ $\displaystyle =$ $\displaystyle \{(j,\alpha):\ \alpha = 0,1,2\}\quad ($perpendicular lines$\displaystyle )\, .$  

This partition into groups is pictured in the following figure.

\includegraphics[width=.9\linewidth]{ebenen}

The same problem for 16 teams, 4 towns and 5 tournament dates can be resolved in an analogous way. For this purpose the $ 4$-element Galois field GF[$ 2^2$] is used and we obtain the following partition into groups

  town 1 town 2 town 3 town 4
1. date 1,2,3,4 5,6,7,8 9,10,11,12 13,14,15,16
2. date 1,6,11,16 5,2,15,12 9,14,3,8 13,10,7,4
3. date 1,10,15,8 5,14,11,4 9,2,7,16 13,6,3,12
4. date 1,14,7,12 5,10,3,16 9,6,15,4 13,2,11,8
5. date 1,5,9,13 2,6,10,14 3,7,11,15 4,8,12,16

Generally, the above reasoning applies to analogous problems with $ q^2$ teams and $ q$ towns, where $ q$ is a power of a prime number because for such $ q$ the field GF[$ q$] exists.

  automatically generated 4/21/2005