Chủ đề này có 1 trả lời

[Strygwyr]

Tám đội bóng tham gia giải vô địch trong đó hai đội bất kỳ phải gặp nhau đúng một lần. Biết rằng đến cuối giải không có trận nào kết thúc với tỉ số hoà. Chứng minh rằng trong tám đội nói trên, luôn tìm được bốn đội $A$, $B$, $C$, $D$ sao cho kết quả giữa các trận đấu của họ là $A$ thắng $B$, $C$, $D$; $B$ thắng $C$, $D$; $C$ thắng $D$

Bài viết đã được chỉnh sửa nội dung bởi namsub: 18-04-2013 - 17:27

[Zaraki]

Tám đội bóng tham gia giải vô địch trong đó hai đội bất kỳ phải gặp nhau đúng một lần. Biết rằng đến cuối giải không có trận nào kết thúc với tỉ số hoà. Chứng minh rằng trong tám đội nói trên, luôn tìm được bốn đội $A$, $B$, $C$, $D$ sao cho kết quả giữa các trận đấu của họ là $A$ thắng $B$, $C$, $D$; $B$ thắng $C$, $D$; $C$ thắng $D$

Lời giải. Gọi $8$ đội bóng đó là $X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8$.

Theo đề bài thì chắc chắn $X_1$ sẽ đấu với $7$ đội còn lại.

 

$\blacktriangleright$ Trường hợp 1. Nếu $X_1$ thắng ít nhất $3$ trong $7$ đội còn lại. Giả sử $X_1$ thắng $X_2,X_3,X_4$.

Trong ba đội $X_2,X_3,X_4$, theo nguyên lí Dirichlet thì sẽ tồn tại một đội hoặc thắng cả hai đội, hoặc thua cả hai đội. Không mất tính tổng quát, giả sử $X_2$ thắng $X_3,X_4$. Khi đó $\boxed{X_1,X_2,X_3,X_4}$ là bốn đội bóng thỏa mãn đề bài.

 

$\blacktriangleright$ Trường hợp 2. Nếu $X_1$ thắng $2$ trong $7$ đội còn lại. Giả sử $\begin{cases} X_1 \; \text{thắng} \; X_2,X_3 \\ X_1 \; \text{thua} \; X_4,X_5,X_6,X_7,X_8 \end{cases}$.

 

$\star$ Khả năng 1. Nếu $X_4,X_5,X_6,X_7,X_8$ lần lượt đấu với $X_2,X_3$ đều có ít nhất một lần thua $X_2,X_3$. 

Vì $5=2 \cdot 2+1$ nên khi đó theo nguyên lí Dirichlet thì tồn tại một trong hai đội $X_2,X_3$ thắng ít nhất $3$ trong $5$ đội $X_4,X_5,X_6,X_7,X_8$. Khi đó ta quay về trường hợp 1, bài toán đúng.

 

$\star$ Khả năng 2. Nếu $X_4,X_5,X_6,X_7,X_8$ lần lượt đấu với $X_2,X_3$ thì đều thắng. Ta có $X_4$ thắng $X_2,X_3,X_1$. Điều này cũng quay về trường hợp 1, bài toán đúng.

 

$\blacktriangleright$ Trường hợp 3. Nếu $X_1$ thắng $1$ trong $7$ đội còn lại. Giả sử $\begin{cases} X_1 \; \text{thắng} \; X_2 \\ X_1 \; \text{thua} \; X_3,X_4,X_5,X_6,X_7,X_8 \end{cases}$.

Xét các trận đấu giữa $X_2$ và $X_3,X_4,X_5,X_6,X_7,X_8$ thì nếu $X_2$ thắng ít nhất ba trong $6$ đội $X_3,X_4,X_5,X_6,X_7,X_8$ thì ta quay về trường hợp 1, hiển nhiên thỏa mãn.

 

Còn nếu $X_2$ thua ít nhất ba trong $6$ đội $X_3,X_4,X_5,X_6,X_7,X_8$. Lấy $X_2$ thua $X_3,X_4,X_5$. Trong ba đội $X_3,X_4,X_5$ thì theo nguyên lí Dirichlet sẽ tồn tại một đội trong ba đội trên thắng hai đội còn lại. Giả sử $X_3$ thắng $X_4,X_5$ và cả $X_1$. Ta quay về trường hợp 1.

 

Do $X_2$ đấu với $6$ đội $X_3,X_4,X_5,X_6,X_7,X_8$ thì ắt hẳn sẽ tồn tại ít nhất ba trận thắng hoặc ít nhất ba trận thua. Vậy trường hợp này cũng luôn tìm được $4$ đội thỏa mãn bài toán.

 

$\blacktriangleright$ Trường hợp 4. Nếu $X_1$ thua $7$ đội còn lại. Khi đó $X_1$ thua $X_2,X_3,X_4$. Trong ba đội $X_2,X_3,X_4$ thì theo nguyên lí Dirichlet sẽ tồn tại một trong ba đội thắng hai đội còn lại. Giả sử $X_2$ thắng $X_3,X_4$ và thắng cả $X_1$ nên ta quay về trường hợp 1, bài toán đúng.

 

Vậy ta có đpcm.

Bài viết đã được chỉnh sửa nội dung bởi Jinbe: 14-07-2013 - 09:47