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

[nguyenbaohoang0208]

Có 2003 vận động viên thi đấu bóng bàn(kết quả chỉ có thắng hoặc thua , không có hòa) theo thể thức thi đấu vòng tròn (mỗi đấu thủ như vậy đều thi đấu với các đấu thủ còn lại).Chứng minh rằng có thể xếp tất cả 2003 vận động viên theo thứ tự hàng dọc sao cho người đứng trước thắng người đứng kề sau

[taconghoang]

Xét tất cả các cách xếp 1 số vận động viên theo hàng dọc sao cho người đứng trước thắng người đứng phía sau ( các cách xếp như vậy luôn tồn tại, chẳng hạn xếp 2 người, người thắng đứng trước người thua đứng sau ). vì số cách xếp như vậy là hữu hạn hên tồn tại cách xếp X có nhiều vận động viên nhất. Ta đi chứng minh cách xếp X có đủ cả 2003 vận động viên.

Giả sử trái lại, còn vận động viên A không được xếp trong cách xếp X. Giả sử trong cách xếp X có n người là $A_{1},A_{2},...,A_{n} (2\leq n\leq 2002)$ sao cho $A_{1}$ thắng $A_{2}$, $A_{2}$ thắng $A_{3}$, ..., $A_{n-1}$ thắng $A_{n}$. Vì đấu vòng tròn nên A phải đấu với $A_{1}$. Nếu A thắng $A_{1}$ thì cách xếp $X_{1}$ theo thứ tự $A,A_{1},A_{2},...,A_{n}$ có nhiều dộng viên hơn các xếp X, trái với cách chọn. Vậy A thua $A_{1}$

Lập luận tương tự ta suy ra A thua $A_{2},A_{3},A_{4},...,A_{n}$. Khi đó cách xếp $X_{2}$ theo thứ tự $A_{1},A_{2},A_{3},..,A_{n},A$ có nhiều vận động viên hơn cách xếp X, trái với cách chọn. Vậy cách xếp X có đủ cả 2003 vận động viên.