อีกข้อนึงคับ
 

ในการแข่งขันหนึ่ง ทุกๆผู้เล่นสองคนจะเจอกันหมด เรียกผู้เล่น $A$ ว่า champion ถ้า $B$ เป็นทุกๆผู้แข่งขันที่ไม่ใช่ $A$ แล้ว $A$ ชนะ $B$ หรือ มีผู้เล่น $C$ ที่ $A$ ชนะ $C$ แล้ว $C$ ชนะ $B$
จงแสดงว่าถ้าในการแข่งขันนี้ $A$ เป็น champion เพียงคนเดียวแล้ว $A$ ชนะทุกคนทั้งหมด

โอ้ข้อสอบโอลิมปิกที่เวียดนามเลยนะครับคุณ gool คงคิดกันใหญ่ครับ ยากเลยทีเดียว

ยากมากเลยครับ ข้อนี้ ผมเพิ่งเรียนเรื่องนี้ไปเองครับ

เดี่ยวผมจะเอาให้ดูsolotionที่ผมคิดค้นด้วยตัวเองเลยน่ะคัรบ

พิสูจน์

Lemma : ทุกๆกลุ่มที่มีคนอย่างน้อย 1 คนซึ่งพบกันหมด จะต้องมี champion เสมอ

พิสูจน์ Lemma
พิจารณาคนที่ชนะคนอื่นมากที่สุด ให้ชื่อว่า A (ไม่จำเป็นต้องมีคนเดียว เพียงแต่เลือกพิจารณาหนึ่งคน)
สมมติคนนั้นไม่ใช่ champion,
กล่าวคือ มี X ซึ่ง X ชนะ A และ ไม่มี Y ซึ่ง AชนะYและYชนะAพร้อมกัน
พิจารณากลุ่มของคนที่ A ชนะ จะได้ว่า ทุกคนในกลุ่ม แพ้ A
และถ้ามีสักคนในกลุ่มนั้นชนะ X จะเกิดข้อขัดแย้ง เพราะเกิดการชนะต่อกันเป็นทอด
ชนะ X ชนะทุกคนในกลุ่มนี้ และชนะ A ด้วย
ทำให้ X มีจำนวนคนที่ชนะ มากกว่า A อยู่อย่างน้อย 1 จึงเกิดข้อขัดแย้ง
นั่นคือ ทุกๆกลุ่มที่มีคนอย่างน้อย 1 คนซึ่งพบกันหมด จะต้องมี champion เสมอ จบการพิสูจน์ Lemma

สำหรับการแข่งขันนี้ ที่มี A เป็น champion เพียงคนเดียว
สมมติว่า A ไม่ได้ชนะทุกคน,
กล่าวคือ มี B ซึ่ง B ชนะ A และ ไม่มี K ซึ่ง A ชนะ K และ K ชนะ A พร้อมกัน
พิจารณากลุ่มของคนที่ A แพ้ (ซึ่งจากสมมติฐาน จึงมั่นใจว่ากลุ่มนี้ไม่ใช่เซตว่าง) เรียกว่า เซต$\mathbb{S}$
พิจารณา champion ของ $\mathbb{S}$ ซึ่งมีแน่นอนจาก Lemma
ให้ชื่อว่า M ดังนั้นทุกคนใน $\mathbb{S}$ จะแพ้ M หรือไม่ก็แพ้แบบส่งต่อ M ทั้งสิ้น
และเห็นได้ชัดว่า M ชนะ A
พิจารณากลุ่มที่แพ้ A ดังนั้น M ชนะคนกลุ่มนี้แบบสองต่อทั้งหมด
แสดงว่า M เป็น champion ด้วย ซึ่งจาก A ไม่ใช่ M ดังนั้นมี champion สองคน
เกิดข้อขัดแย้ง
แสดงว่า A ชนะทุกคน จบการพิสูจน์

ไม่เข่าใจส่งpmมาได้น่ะครับ