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

[huykinhcan99]

Trong một giải đấu bóng đá có 10 đội tham gia theo thể thức mỗi đội đều gặp đội khác một lần. Người ta nhận thấy một điều thú vị là với 3 đội bóng $A$, $B$, $C$ bất kỳ, nếu $A$ thắng $B$ và $B$ thắng $C$ thì $A$ thắng $C$. Chứng minh rằng ít nhất một trong hai điều sau phải xảy ra:

• Có 4 đội $A$, $B$, $C$, $D$ mà $A$ thắng $B$, $B$ thắng $C$ và $C$ thắng $D$.
• Có 4 đội mà các trận giữa họ đều hoà.

(Kỳ thi chọn học sinh giỏi môn Toán lớp 10, tỉnh Thái Nguyên, năm học 2016 - 2017)

Bài viết đã được chỉnh sửa nội dung bởi huykinhcan99: 07-04-2017 - 20:53

[xuanhoan23112002]

Ta chứng minh bài toán bằng phản chứng( cả 1 và 2 đều không xảy ra)

Gọi 10 đội bóng là a_i (i là số tự nhiên và i chạy từ 1 đến 10)

Giả sử a₁₀ là đội bóng có số trận thua nhiều nhất

Khi đó nếu tồn tại giá trị i từ 1 đến 9 mà a₁₀ thang a_i thì tất cả cả đội bóng mà a₁₀ thua thì a_i cũng thua (vô lí do a₁₀ có số trận thua nhiều nhất)

Suy ra a₁₀ thi đấu với các đội còn lại chỉ có thể hòa hoặc thua

Mà theo gia sư điều kiện 2 không xảy ra nên a₁₀ thua ít nhất 7 đội là a_j (j chạy từ 1 đến 7)

Lập luận tương tự như trên với a₇ là đội có số trận thua nhiều nhất trong 7 đội trên thì a₇ phải thừa ít nhất 4 đội giả sử là: a₁, a₂, a₃, a₄.

Lập luận tương tự như trên với a4 là đội có số trận thua nhiều nhất trong 4 đội trên thì a4 phải thừa ít nhất 1 đội giả sử là: a₁. 

Như vậy ta tìm được 4 đội: a₁, a₄, a₇, a₁₀, lập thành 4 đội thỏa mãn điều kiện 1( mâu thuẫn với giả sử)

Do đó giả sử sai. Ta có điều phải chứng minh

[CF Gauss]

Với mỗi đội bóng $x_1$, nếu dãy đội $(x_1, x_2,\dots x_n)$ sao cho $x_i$ thắng $x_{i-1}$ có độ dài lớn nhất thì $n$ được gọi là bậc của $x_i$. Nhận thấy rằng, nếu $x$ thắng $y$ và bậc của $y$ là $d$, thì bậc của $x$ tối thiểu phải là $d+1$. Mặt khác, tồn tại một đội có bậc bằng $0$, vì bậc của một đội thì hữu hạn. Vậy nếu điều thứ nhất ở trên không xảy ra, thì bậc của một đội chỉ có thể là $2, 1, 0$. Có $10$ đội tất cả, suy ra tồn tại bốn đội cùng bậc. Mà hai đội cùng bậc thi không thể thắng lẫn nhau, vì bậc của đội thắng luôn lớn hơn. Q.E.D