Lập lịch thi đấu 10 đội vòng tròn

Bài toán:

Hãy lập lịch thi đấu cho giải bóng đá có 10 đội tham gia theo thể thức vòng tròn một lượt

Giải

Cách 1 - Dùng hình học

Đặt mỗi đội tương ứng với 1 đỉnh của hình 9 cạnh đều và tâm của nó. 

Mỗi lượt thi đấu, ta dựng các đoạn thẳng song song nối các cặp đỉnh với nhau và đoạn thẳng nối tâm với đỉnh bị lẻ.

Ta có lịch thi đấu như sau (mỗi dòng là 1 vòng đấu)

$$\begin{matrix}(1,2) &(3,9) &(4,8) &(5,7) &(6,10) \\ (1,3)& (4,9) &(5,8) &(6,7) & (2,10)\\ (1,4) &(2,3) &(5,9) & (6,8) &(7,10) \\ (1,5)& (2,4) &(6,,9) &(7,8) &(3,10) \\ (1,6) &(2,5) &(3,4) &(7,9) &(8,10) \\ (1,7) &(2,6) &(3,5) & (8,9) & (4,10)\\ (1,8) & (2,7) & (3,6) & (4,5) &(9,10) \\ (1,9) & (2,8) &(3,7) &(4,6) &(5,10) \\ (1,10) &(2,9) &(3,8) &(4,7) &(5,6) \end{matrix}$$

Cách 2

Đặt tương ứng mỗi đội bóng với một phần tử của $A=\mathbb{Z}_9 \cup \{ a \}$

Xét các ánh xạ $f_i : A \to A, (i = 0,1,..,8)$ được xác định như sau:

$$f_i(x) = \left\{\begin{matrix}a & \text{khi } (x + x) \equiv i ( \mod 9) \\ y &\text{khi } (x + y) \equiv i ( \mod 9) \end{matrix}\right., \forall x \in \mathbb{Z}_9$$

Quy ước: 

$$f_i(a)=x \Leftrightarrow f(x)=a, \forall i$$

Dễ thấy $9$ ánh xạ $f_i$ kể trên thỏa mãn đồng thời các tính chất:

1) Là song ánh;

2) $f_i(x) = y \Leftrightarrow f_(y)=x, \forall x,y \in A;\forall i = 0,1,..,8$

3) $f_i(x) \neq f_j(x), \forall i \neq j$

Do đó, mỗi ánh xạ cho ta lịch thi đấu của một vòng đấu. Chẳng hạn, với $f_0$

$$f_0(1) = 8; f_0(2)=7;f_0(3) = 6; f_0(4)=5$$

$$f_0(5) = 4; f_0(6)=3;f_0(7) = 2; f_0(8)=1;f_0(9)=10$$

Ta có các cặp đấu:

$$(1,8), (2,7), (3,6), (4,5) ,(9,10) $$

Dễ thấy là đáp án của cách 1 và cách 2 giống nhau.

Cách 3
Ta sẽ lập lịch thi đấu cho giải đấu 3 đội, từ đó phát triển thành giải đấu 10 đội.
Lịch thi đấu của giải đấu 3 đội như sau (Đội đứng một mình là đội nghỉ lượt đấu đó)

$$\begin{matrix}(1,2) &(3,) \\(2,3) &(1,) \\(3,1) & (2,)\end{matrix}$$

Từ lịch thi đấu cho 3 đội, ta xây dựng lịch thi đấu cho 6 đội như sau. Chia 6 đội thành 2 nhóm (1,2,3) và (4,5,6). Trong 3 lượt đầu, hai nhóm thi đấu theo lịch như trên, hai đội lẻ thì gặp nhau. Trong 2 lượt sau, đội đứng thứ $i$ của nhóm 1 gặp đội đứng thứ $i+1$ của nhóm 2. Quy ước: đội thứ tư là đội thứ nhất. Ta có lịch thi đấu:
$$\begin{matrix}(1,2) &(3,6) &(4,5) \\(2,3) &(1,4) &(5,6) \\(3,1) & (2,5) & (6,4) \\ (1,5) & (2,6) & (3,4) \\ (1,6) & (2,4) & (3,5)\end{matrix}$$

Từ lịch thi đấu cho 6 đội, ta dễ dàng lập được lịch thi đấu cho 5 đội bằng cách bỏ đi đội 6.
$$\begin{matrix}(1,2) &(4,5) &(3,6) \\(2,3) &(1,4) &(5,) \\(3,1) & (2,5) & (4,) \\ (1,5) & (3,4)& (2,) \\ (2,4) & (3,5) & (1,) \end{matrix}$$

Từ lịch thi đấu cho 5 đội, bằng cách làm tương tự như trên, ta có lịch thi đấu của 10 đội:
$$\begin{matrix}(1,2) &(4,5) &(3,8) & (9,10) & (6,7) \\(1,4) &(2,3) &(5,10) & (7,8) & (6,9) \\ (1,3) &(2,5) &(4,9) & (7,10) & (6,8) \\ (1,5) &(3,4) &(2,7) & (8,9) & (6,10) \\ (2,4) &(3,5) &(1,6) & (8,10) & (7,9) \\ (1,7) &(2,8) &(3,9) & (4,10) & (5,6) \\ (1,8) &(2,9) &(3,10) & (4,6) & (5,7) \\ (1,9) &(2,10) &(3,6) & (4,7) & (5,8) \\ (1,10) &(2,6) &(3,7) & (4,8) & (5,9) \\ \end{matrix}$$