1) Bài toán xếp lịch thi đấu thể thao

Bài toán đặt ra là xếp lịch thi đấu vòng tròn 1 lượt cho n đấu thủ. Mỗi đấu thủ phải đấu với n-1 đấu thủ còn lại và mỗi đấu thủ chỉ đấu nhiều nhất là 1 trận mỗi ngày. Yêu cầu xếp lịch sao cho số ngày thi đấu là ít nhất.

Dễ dàng thấy rằng tổng số trận đấu là .

Như vậy nếu n chẵn, ta có thể xếp n/2 cặp đấu với nhau mỗi ngày và số ngày thi đấu ít nhất sẽ là n-1 ngày. Ngược lại nếu n lẻ, thì n-1 ta có thể xếp (n-1)/2 trận mỗi ngày và vì vậy chúng ta cần n ngày. Giả sử n = 2k thì n chẵn do đó ta cần ít nhất n – 1 ngày.

2. Giải thuật chia để trị cho bài toán xếp lịch thi đấu

– Giả sử lịch thi đấu là 1 bảng gồm n dòng (tương ứng với n đấu thủ) và n-1 cột (tương ứng với n-1 ngày). Ô (i,j) biểu diễn đấu thủ mà i phải đấu trong ngày j. Nhiệm vụ của chúng ta là lấp đầy các ô này sao cho quy tắc của bài toán.

– Chiến lược chia để trị như sau: thay vì xếp cho n người, ta sẽ xếp cho n/2 người sau đó dựa trên kết của lịch thi đấu của n/2 người ta xếp cho n người. Quá trình phân chia sẽ dừng lại khi ta phải xếp lịch cho 2 đấu thủ. Việc xếp lịch cho 2 đấu thủ rất dễ dàng: ta cho 2 đấu thủ này thi đấu 1 trận trong 1 ngày. Bước khó khăn nhất chính là bước xây dựng lịch cho 4, 8, 16, … đấu thủ từ lịch thi đấu của 2 đấu thủ.

 

3) Xây dựng lịch thi đấu

Lịch thi đấu của 2 người sẽ là bảng gồm 2 dòng và 1 cột: ô(1,1) = 2 (người 1 đấu với người 2 trong ngày 1) và ô(2,1) = 1 (người 2 đấu với người 1 trong ngày 1).

Lịch thi đấu của 4 người là bảng gồm 4 dòng và 3 cột. Lịch thi đấu của người 1 và người 2 trong ngày 1 là lịch thi đấu của 2 người. Lịch thi đấu của người 3 và người 4 được xây dựng tương tự lịch của người 1 và người 2. Lịch này có được bằng cách cộng lịch thi đấu của người 1 và người 2 với 2. Nghĩa là ô(3,1) = ô(1,1) + 2 = 4 và ô (4,1) = ô(2,1) + 2 = 3. Hai cột còn lại của bảng được lấp đầy theo quy tắt: lấy góc trên bên trái (tính luôn phần chỉ số dòng) lấp đầy góc dưới bên phải và lấy góc dưới bên trái lấp đầy góc trên bên phải.

Lịch thi đấu cho 8 đấu thủ cũng được xếp theo quy tắc tương tự: lấy lịch thi đấu của 4 đấu thủ lấp vào góc trên bên trái. Cộng thêm 8/2 = 4 vào các ô của góc trên bên trái để có góc dưới bên trái. Lấy góc trên bên trái lấp đầy góc dưới phải. Lấy góc dưới trái lấp đầy góc trên phải.