#1
|
||||
|
||||
TMO12
ให้ P={(x,y)|x,y เป็นสมาชิกของเซต {0,1,2,...,2015}} เป็นเซตของจุดบนระนาบนำเส้นลวดยาวเส้นละ 1 หน่วยมาวางเชื่อมจุดในเซต P ตามแนวนอน หรือแนวตั้ง โดยที่ทุกๆจุดใน P ต้องเป็นจุดปลายของลวดเส้นใดเส้นหนึ่ง และไม่มีเส้นลวดสองเส้นใดๆที่ใช้จุดปลายร่วมกัน
จงแสดงว่าไม่ว่าจะวางเส้นลวดตามเงื่อนไขดังกล่วอย่างไร จะสามารถลากเส้นตามแนวตั้ง หรือ แนวนอนให้ผ่านจุดศูนย์กลางของเส้นเชือกได้อย่างน้อย 506 เส้นเสมอ อยากได้วิธีคิดของข้อนี้ครับ |
#2
|
||||
|
||||
พิสูจน์ว่าจะมีเส้นที่ผ่านอย่างน้อย 505 เส้น สมมติว่าผ่าน 505 เส้นพอดี สมมติคือเส้น $y=i+ \frac{1}{2}$ แล้วพิจารณาจำนวนเส้นลวดที่อยู่บนเส้นตรง $y=i+\frac{1}{2}$
__________________
เหนือฟ้ายังมีอวกาศ 14 เมษายน 2016 14:50 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ กขฃคฅฆง |
#3
|
||||
|
||||
ขอ Hint อีกนิดนึงทีครับ ยังไม่ค่อยเข้าใจครับ 555+
|
#4
|
||||
|
||||
คือว่า ถ้าพิสูจน์ว่ามันผ่านอย่างน้อย 505 เส้นได้แล้ว
และผมก็พิสูจน์ได้แล้วว่ามันผ่านเป็นจำนวนคู่เส้นเสมอเลยได้ 506 แต่ขั้นตอนก่อนหน้านั้นน่ะครับยังไม่เข้าใจครับ |
#5
|
||||
|
||||
ใช้รังนกพิราบครับ
__________________
เหนือฟ้ายังมีอวกาศ |
#6
|
|||
|
|||
คือเส้นลวดจะมีทั้งหมด $2016^2/ 2$ เส้นถูกไหมครับ
แล้วมันก็จะมี 2 ประเภท คือที่วางตัวในแนวนอน กับประเกทที่วางตัวในแนวตั้ง โดยหลักรังนกพิราบ จะต้องมีเส้นลวดประเภทเดียวกัน $2016^2/4$ เส้น โดยไม่เสียนัยทั่วไป สมมติว่ามีเส้นลวดที่วางตัวในแนวนอนอย่างน้อย $2016^2/4$ เส้น เรามีเส้นดิ่งทั้งหมด 2015 เส้น และเส้นลวดที่วางตัวในแนวนอนจะต้องผ่าน 1 ใน 2015 เส้นนี้ โดยหลักรังนกพิราบอีกครั้ง จะมีเส้นดิ่งอย่างน้อย 1 เส้นที่ผ่านลวด $\left\lceil\dfrac{2016^2}{4\cdot 2015}\right\rceil=505$ เส้น ครับ |
#7
|
||||
|
||||
ออ เข้าใจแล้ว ขอบคุณทั้งสองท่านเลยนะครับ
|
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
TMO12 | Nonpawit12345 | เรขาคณิต | 1 | 27 ธันวาคม 2015 16:11 |
TMO12 | polsk133 | ข้อสอบโอลิมปิก | 20 | 28 มิถุนายน 2015 10:57 |
Fighting for TMO12 !! | FranceZii Siriseth | ข้อสอบโอลิมปิก | 63 | 15 มิถุนายน 2015 07:43 |
|
|