USAMO $1989$, ปัญหา $2$

Aug 17 2020

ปัญหา $2$ จาก USAMO $1989$: $20$ สมาชิกของสโมสรเทนนิสท้องถิ่นได้กำหนดเวลาไว้อย่างแน่นอน $14$เกมสองคนระหว่างกันโดยสมาชิกแต่ละคนเล่นอย่างน้อยหนึ่งเกม พิสูจน์ว่าภายในกำหนดการนี้จะต้องมีเกมหกเกมด้วย$12$ ผู้เล่นที่แตกต่างกัน

ความพยายามของฉันในการแก้ปัญหา:เนื่องจากมี$20$ ผู้เล่นแต่ละคนเล่นมาแล้วอย่างน้อยหนึ่งเกมจำนวนการแข่งขันน้อยที่สุดที่จะต้องจัดเพื่อรองรับผู้เล่นทั้งหมดจะเป็น $10$. ตอนนี้$4$เหลือการแข่งขันอีกมากซึ่งสามารถเล่นได้มากที่สุด $8$ ของเหล่านี้ $20$ผู้เล่น ดังนั้นอย่างน้อย $12$ ของผู้เล่นได้เล่นไม่เกิน $1$การแข่งขันและด้วยเหตุนี้จึงต้องมีเกมหกเกมด้วย$12$ผู้เล่นที่แตกต่างกัน ฉันเชื่อว่านี่จะเป็นแนวทางในการพิสูจน์อย่างเข้มงวด

ฉันมีข้อสงสัยต่อไปนี้ทำให้จิตใจขุ่นมัว:

  1. เหตุผลของฉันฟังดูไม่มีข้อผิดพลาดหรือไม่
  2. ถ้าถูกต้องจะวางกรอบเหตุผลข้างต้นในการพิสูจน์อย่างเข้มงวดทางคณิตศาสตร์ได้อย่างไร?

แก้ไข:ตามที่เบ็นชี้ให้เห็นในความคิดเห็นข้อความที่เป็นตัวเอียงนั้นไม่ยุติธรรม ฉันมองข้ามความเป็นไปได้มากมายในขณะที่วางกรอบหลักฐานนี้ ดังนั้นฉันต้องการรับคำแนะนำเพื่อดำเนินการพิสูจน์ที่สมเหตุสมผลกว่านี้

คำตอบ

2 cgss Aug 17 2020 at 12:31

ฉันกลัวว่าจะมีหลุมพราง หากคุณพยายามพิสูจน์ว่ามี 6 เกมที่มีผู้เล่นแตกต่างกัน 12 คนในบรรดาผู้ที่เล่น 1 เกมคุณจะล้มเหลว นี่คือตัวอย่าง:

$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$

ในขณะที่มี 6 เกมที่มีผู้เล่น 12 คนที่แตกต่างกันมีเพียง 5 เกมเท่านั้นที่อยู่ระหว่างผู้เล่นกับเกมเดียว

ดังนั้นนี่คือคำแนะนำ: แบ่งผู้เล่นออกเป็นสองกลุ่มกลุ่มที่มีเกมเดียวและกลุ่มที่มีมากกว่านั้น จากนั้นจับคู่ผู้เล่นกับเกมหนึ่งหลังจากจับคู่ผู้เล่นกับเกมหนึ่งกับผู้เล่นที่มีผู้เล่นมากกว่าและสุดท้ายผู้เล่นที่มีเกมมากขึ้น

แก้ไข : แนวทางที่สอง

หากทุกคนถูกมองว่าเป็นจุดยอดและทุกเกมเป็นขอบคำถามจะขอให้พิสูจน์ว่ามีขนาดที่ตรงกันอย่างน้อยที่สุด $6$. ในทางเดียวกันเราสามารถพิสูจน์ได้ว่าขนาดของการจับคู่สูงสุด$MM$ มีขนาดอย่างน้อย $6$. โปรดทราบว่าพาร์ติชันที่ตรงกันสูงสุดจะแบ่งจุดยอดออกเป็นสองชุดโดยชุดหนึ่งมีขอบใน$MM$ขนาด $2\cdot |MM|$และอีกอันไม่มีขนาด $20 - 2\cdot |MM|$สำหรับปัญหาของเรา เนื่องจากจุดยอดทั้งหมดมีระดับเป็นอย่างน้อย$1$เราสรุปได้ว่ามีอย่างน้อย $20 - 2\cdot |MM|$ขอบระหว่างสองพาร์ติชัน ตอนนี้

$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$