ก่อนถึงคำถาม
ขอ Happiizz Birth Day พี่นวย นะครับ
มีความสุขมาก ๆ นะครับผม ^^
พอดีวันนี้มีน้องไปสอบโควต้า ดาวพฤหัสมา
เค้าถามว่า
มีทีมฟุตบอล 20 ทีม มี 5 ทีมต้องแข่ง 10 นัด
ถ้ามีการแข่งอย่างน้อย 70 นัด ทีมที่เหลือแข่งคนละกี่นัด
ใช่เรื่อง ทฤษฎีกราฟป่ะครับ ?
พอดีที่ รร อาจารย์ข้ามเรื่องนี้ไป
เลยไม่สมารถเฉลยได้
รบกวนพี่นวยด้วยนะครับบบ
NayKungStyle
ขอบคุณสำหรับคำอวยพร (อีกครั้งแล้ว :P) นะครับ
แหม่มีโจทย์ข้อสอบฉลองวันเกิดด้วย แหะๆๆๆ
ข้อนี้เป็นเรื่องทฤษฎีกราฟจริงๆ ครับ.. โดยทีมฟุตบอล 20 ทีม เปรียบเสมือนมีจุดยอด 20 จุด
มี 5 ทีมที่แข่ง 10 นัด ก็คือมี 5 จุดยอด ที่มีดีกรี 10 (หมายถึงมีปลายเส้นลากมาเชื่อม จุดละ 10 เส้น)
การแข่งทั้งหมดมีอย่างน้อย 70 ครั้ง หมายความว่า จำนวนเส้นเชื่อมทั้งหมด อย่างน้อย 70 เส้น
แต่เรามีหลักอยู่ว่า จำนวนเส้นเชื่อม เท่ากับ ดีกรีรวม/2 เสมอครับ (เพราะหนึ่งเส้นต้องมีสองปลาย)
สมมติว่า ทีมที่เหลือ 15 ทีม แข่งทีมละ x ครั้ง (นั่นคือ 15 จุดที่เหลือ มีดีกรีเป็น x เท่ากัน)
ก็จะได้สมการจำนวนเส้นเชื่อมเป็น (15x + 50) / 2 >= 70
แก้ได้ x >= 6 ครับ แสดงว่า ทีมทีเหลือแต่ละทีมต้องแข่งอย่างน้อย 6 ครั้งคร้าบ :]
นวย