|
|
#1
11 สิงหาคม 2007, 21:33
|
||||
|
||||
อีกข้อนึงคับ
ในการแข่งขันหนึ่ง ทุกๆผู้เล่นสองคนจะเจอกันหมด เรียกผู้เล่น $A$ ว่า champion ถ้า $B$ เป็นทุกๆผู้แข่งขันที่ไม่ใช่ $A$ แล้ว $A$ ชนะ $B$ หรือ มีผู้เล่น $C$ ที่ $A$ ชนะ $C$ แล้ว $C$ ชนะ $B$
จงแสดงว่าถ้าในการแข่งขันนี้ $A$ เป็น champion เพียงคนเดียวแล้ว $A$ ชนะทุกคนทั้งหมด 
|
|
#4
06 มกราคม 2009, 21:55
|
||||
|
||||
|
อ้างอิง:
พิสูจน์ 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มาได้น่ะครับ
__________________
วะฮ่ะฮ่ะฮ่า
ข้าคืออุลตร้าแมน ทุกโพสเป็นไปเพื่อความสันติสุขของเหล่ามวลมนุษย์ อุลตร้าแมนจงเจริญ  06 มกราคม 2009 21:56 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ วะฮ่ะฮ่ะฮ่า
|
  |
|
|
