คอมบิ ทำไงครับ

[reve]

(VMO2007)Given 2007-n gon ให้หา k min ที่ใน k จุดยอดใดๆของรูปหลายเหลี่ยม จะมี 4 จุดยอดที่เป็นสี่เหลี่ยมนูน
ที่มีสามด้านร่วมกับรูปหลายเหลี่ยม

พอมองเป็น

จงหาจำนวนสมาชิกที่น้อยที่สุด(=k)ของสับเซตของเซต {1,2,...,2007} ซึ่งเมื่อหยิบสับเซตใดๆมาแล้ว
จะมีเลขเรียงกัน4ตัวเสมอ

เฉลยคือ 1506
พิสูจน์ได้ไม่ยากว่า<1506 ไม่สอดคล้องแล้วทีนี้เราจะพิสูจว่า k=1506 สอดคล้องได้ยังไงครับ

ผมลองใช้รังนกและแบ่งเซตแบบ {1,2,3,4},{5,6,7,8},...,{2001,2002,2003,2004},{2005,2006,2007}
มันไม่ได้อะครับ แล้วผมอ่านเฉลยของฝรั่งไม่ค่อยรู้เรื่อง

อันนี้เฉลยจาก aops ครับ: http://www.artofproblemsolving.com/c...h132552p750364
เฉลยอันนี้ผมสงสัยว่าแบ่งเซตแบบนั้นแล้ว 2005,2006,2007 หายไปไหนครับ

เฉลยอีกอันจากtextbook เล่มหนึ่ง: consider the 4-tuples of consecutive vertices. Each vertex uses 4
of these 4-tuples. Thus if 4k>3*2007 there is a 4-tuple with 4 of the k vertices . That is k>=1506. อันนี้ผมก็ไม่เข้าใจครับ

[Thgx0312555]

สาเหตุที่มันแบ่งไม่ได้เพราะว่าการแบ่งแบบนี้เราอาจจะเลือก $1,2,3,5,6,7,9,10,11,13,...,2005,2006,2007$ ได้โดยไม่ขัดแย้งใดๆครับ (แต่ในความเป็นจริง $2005,2006,2007,1$ ไม่ได้เพราะตัวเลขวนเป็นวงกลม)

ดังนั้นวิธีแก้ที่ผมใช้ส่วนใหญ่จะต่อเซต $\{2005,2006,2007,1\},\{2,3,4,5\},...$ ไปเรื่อยๆจนวน i.e หรือเขียนแบบนี้ก็ได้ เลือกเซต $\{1,2,3,4\},\{2,3,4,5\},\{3,4,5,6\},\{4,5,6,7\},...,\{2007,1,2,3\}$ ดังนั้นแต่ละตัวเลขจะปรากฎ $4$ ครั้ง ดังนั้นถ้าเราเลือก $1506$ ตัวเลขจะมีตัวเลขที่เราเลือกปรากฎทั้งหมด $6024$ ครั้งแล้วก็รังนกปกติเลยครับ

ถ้าเกิดงงวิธีนี้ก็มีวิธีแก้อีกวิธีนึงที่ใช้ได้ คือแบ่งเซตแบบเดิม
$\{1,2,3,4\},\{5,6,7,8\},...,\{2005,2006,2007\}$
แล้วใช้การที่สามารถสมมติโดยไม่เสียนัยทั่วไปให้ $2007$ ไม่ถูกเลือกได้
ดังนั้นเซตสุดท้ายจะถูกเลือกอย่างมาก $2$ จำนวน
เซตที่เหลือจะถูกเลือกอย่างน้อย $1504$ จำนวน ก็รังนกได้แล้วครับ


/ยังไม่เปิดดูลิงค์นะครับ เลยไม่รู้ว่าเขาทำวิธีไหน แต่เดาว่าเป็นหนึ่งในสองวิธีนี้แหละ

Edit 4: เปิดลิงค์ดูแล้วเห็นถึงความมั่วของเฉลยในนั้นครับ มันผิดตรงที่คุณว่าแหละ $2005,2006,2007$ หายไปไหน

[reve]

ขอบคุณมากครับ