(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. อันนี้ผมก็ไม่เข้าใจครับ