dirichlet

[cuong131hv]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

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

 

[naruto2001]

có tất cả 28 trận đấu , mà chỉ có 8 đội và ko có trận nào hòa nên phải có ít nhất 1 đội thắng nhiều hơn 3 trận , giả sử là đội A thắng ít nhất 3 đội B1,C1,D1
trong 3 trận đấu giữa B1,C1,D1
+ nếu B1 thắng C1, D1 thì B1 là đội B theo giả thiết . trong trận C1 gặp D1 , đội nào thắng là đội C , đội nào thua là đội D
vậy trong trường hợp này ta luôn có 4 đội A,B,C,D thỏa mãn bài toán
+ nếu B1 thua C1, thua D1 thì B1 là đội D , . trong trận C1 và D1 nếu đội nào thắng là đội B, đội nào thua là đội C
trong trường hợp này ta cũng có 4 đội A,B,C,D như bài toán
+ nếu B1 thua C1, thắng D1 thì B1 là đội C , còn trong trận C1 gặp D1 , nếu đội nào thắng thì là đội B , đội nào thua thì là đội D
trường hợp này ta cũng tìm dc 4 đội A,B,C,D thỏa mãn
+ Nếu B1 thắng C1 , thua D1 thì B1 là đội C . trong trận C1 và D1, đội nào thắng là đội B, đội nào thua là đội D
như vậy ta cũng tìm dc 4 đội A,B,C,D thỏa mãn
KL trong mọi trường hợp , với điều kiện của bài toán , ta luôn tìm được 4 đội A,B,C,D thỏa mãn đề


HM___________________________________________

 

[huynhbachkhoa23]

Ta có một kết quả mạnh hơn là có thể xếp 8 đội trên sao cho đội đứng trước thắng đội đứng sau.
Đầu tiên vì tồn tại cách xếp đội đứng trước thắng đội đứng sau nên tồn tại cách xếp $A_1,A_2,...,A_k$ sao cho $A_1$ thắng $A_2$, $A_2$ thắng $A_3$,..., $A_{k-1}$ thắng $A_k$ và cách xếp trên có nhiều đội nhất.
Giả sử tồn tại đội $B$ trong $8$ đội và không nằm trong cách xếp trên.
$B$ không thể thắng $A_1$ vì khi đó cách xếp $B,A_1,A_2,...,A_k$ có nhiều đội hơn cách xếp có nhiều đội nhất nên $B$ thua $A_1$, tương tự có $B$ thua $A_2, A_3,...,A_k$ nên ta có cách xếp $A_1,A_2,...,A_k,B$, điều này vô lý vì cách xếp này có nhiều đội hơn cách xếp có nhiều đội nhất.
Vậy ta có điều phải chứng minh.