Mathcenter Forum  

Go Back   Mathcenter Forum > คณิตศาสตร์โอลิมปิก และอุดมศึกษา > คอมบินาทอริก
สมัครสมาชิก คู่มือการใช้ รายชื่อสมาชิก ปฏิทิน ค้นหา ข้อความวันนี้ ทำเครื่องหมายอ่านทุกห้องแล้ว

ตั้งหัวข้อใหม่ Reply
 
เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
  #1  
Old 25 ธันวาคม 2016, 01:04
reve reve ไม่อยู่ในระบบ
หัดเดินลมปราณ
 
วันที่สมัครสมาชิก: 28 ตุลาคม 2016
ข้อความ: 34
reve is on a distinguished road
Default คอมบิ ทำไงครับ

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

29 ธันวาคม 2016 21:36 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ reve
ตอบพร้อมอ้างอิงข้อความนี้
  #2  
Old 25 ธันวาคม 2016, 18:37
Thgx0312555's Avatar
Thgx0312555 Thgx0312555 ไม่อยู่ในระบบ
กระบี่ประสานใจ
 
วันที่สมัครสมาชิก: 12 สิงหาคม 2011
ข้อความ: 885
Thgx0312555 is on a distinguished road
Default

สาเหตุที่มันแบ่งไม่ได้เพราะว่าการแบ่งแบบนี้เราอาจจะเลือก $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$ หายไปไหน
__________________
----/---~Alice~ จงรับรู้ไว้ ชื่อแห่งสีสันหนึ่งเดียวที่แสดงผล
---/---- ~Blue~ นี่คือ สีแห่งความหลังอันกว้างใหญ่ของเว็บบอร์ดนี้

25 ธันวาคม 2016 18:43 : ข้อความนี้ถูกแก้ไขแล้ว 5 ครั้ง, ครั้งล่าสุดโดยคุณ Thgx0312555
ตอบพร้อมอ้างอิงข้อความนี้
  #3  
Old 26 ธันวาคม 2016, 15:31
reve reve ไม่อยู่ในระบบ
หัดเดินลมปราณ
 
วันที่สมัครสมาชิก: 28 ตุลาคม 2016
ข้อความ: 34
reve is on a distinguished road
Default

ขอบคุณมากครับ
ตอบพร้อมอ้างอิงข้อความนี้
ตั้งหัวข้อใหม่ Reply


เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
ค้นหาในหัวข้อนี้:

ค้นหาขั้นสูง

กฎการส่งข้อความ
คุณ ไม่สามารถ ตั้งหัวข้อใหม่ได้
คุณ ไม่สามารถ ตอบหัวข้อได้
คุณ ไม่สามารถ แนบไฟล์และเอกสารได้
คุณ ไม่สามารถ แก้ไขข้อความของคุณเองได้

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
ทางลัดสู่ห้อง


เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 16:14


Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha