TMO12
 

ให้ P={(x,y)|x,y เป็นสมาชิกของเซต {0,1,2,...,2015}} เป็นเซตของจุดบนระนาบนำเส้นลวดยาวเส้นละ 1 หน่วยมาวางเชื่อมจุดในเซต P ตามแนวนอน หรือแนวตั้ง โดยที่ทุกๆจุดใน P ต้องเป็นจุดปลายของลวดเส้นใดเส้นหนึ่ง และไม่มีเส้นลวดสองเส้นใดๆที่ใช้จุดปลายร่วมกัน

จงแสดงว่าไม่ว่าจะวางเส้นลวดตามเงื่อนไขดังกล่วอย่างไร จะสามารถลากเส้นตามแนวตั้ง หรือ แนวนอนให้ผ่านจุดศูนย์กลางของเส้นเชือกได้อย่างน้อย 506 เส้นเสมอ


อยากได้วิธีคิดของข้อนี้ครับ :)

พิสูจน์ว่าจะมีเส้นที่ผ่านอย่างน้อย 505 เส้น สมมติว่าผ่าน 505 เส้นพอดี สมมติคือเส้น $y=i+ \frac{1}{2}$ แล้วพิจารณาจำนวนเส้นลวดที่อยู่บนเส้นตรง $y=i+\frac{1}{2}$

ขอ Hint อีกนิดนึงทีครับ ยังไม่ค่อยเข้าใจครับ 555+

คือว่า ถ้าพิสูจน์ว่ามันผ่านอย่างน้อย 505 เส้นได้แล้ว
และผมก็พิสูจน์ได้แล้วว่ามันผ่านเป็นจำนวนคู่เส้นเสมอเลยได้ 506
แต่ขั้นตอนก่อนหน้านั้นน่ะครับยังไม่เข้าใจครับ

ใช้รังนกพิราบครับ

คือเส้นลวดจะมีทั้งหมด $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$ เส้น ครับ

ออ เข้าใจแล้ว ขอบคุณทั้งสองท่านเลยนะครับ :)