|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
|||
|
|||
The Pigeonhole Principle
ผมไม่ได้เข้ามาเว็บบอร์ดหลายเดือนแล้ว เพราะว่ามัวแต่เข้าค่ายอยู่เลยไม่ว่าง
แต่ตอนนี้กำลังดูเนื้อหาเรื่องหลักการรังนกพิราบอยู่ เลยมีโจทย์มาถามครับ 1. ในกลุ่มคน 6 คนโดยที่คนแต่ละคู่รู้จักกันหรือไม่รู้จักกัน จงแสดงว่ามี 3 คนที่รู้จักกันหรือมี 3 คนที่ไม่รู้จักกัน 2. นายดนัยต้องการซ้อมเทนนิสก่อนการแข่งขัน ซึ่งมีเวลาซ้อม 30 วัน โดยที่นายดนัยวางแผนการซ้อมว่าต้องเล่นวันละอย่างน้อย 1 เกมส์แต่ทั้งหมดรวมไม่เกิน 45 เกมส์ จงแสดงว่าไม่ว่านายดนัยวางแผนการซ้อมอย่างไรก็ตามต้องมีช่วงวันที่ติดต่อกันที่นายดนัยเล่นได้ 14 เกมส์พอดี 3. เลือกจำนวนเต็ม 201 จำนวน มาจาก {1,2,3,...,400} จงแสดงว่าในบรรดาจำนวนเต็ม 201 จำนวนที่เลือกมานั้นจะต้องมีจำนวนเต็มสองจำนวนซึ่งจำนวนหนึ่งหารอีกจำนวนหนึ่งลงตัว |
#2
|
|||
|
|||
ข้อ 1 เรื่องกราฟ ปะ
จะพิสูจน์แย้งนะครับ (ใช่เรียกแบบนี้รึเปล่า) สมมติว่าแต่ละคนมีชื่อว่า A B C D E และ F แต่ละคู่จะมีเส้นเชื่อมต่อกัน ถ้าเป็นเส้นทึบแสดงว่ารู้จักกัน ถ้าเป็นเส้นประ แสดงว่าไม่รู้จักกันนะ A ต้องลาก 5 เส้นแล้ว อย่างน้อย ต้องเส้นทึบ มากกว่าหรือเท่ากับ 3 หรือ เส้นประ มากกว่าหรือเท่ากับ 3 ดูกรณีแรกก่อนละกัน อย่างน้อยที่สุด คือมีเส้นทึบ สามเส้น สมมติลากไป A---B A---C และ A---D เพื่อไม่ให้เกิดสามคนที่รู้จักกัน ก็ต้องลากเส้นประ B- - -C B- - -D C- - -D แต่จะเกิด B- - -C- - -D ที่เป็นกลุ่มสามคนที่ไม่รู้จักกัน อีกกรณีก็คล้ายๆกัน ลองวาดรูปประกอบดูครับ
__________________
[[:://R-Tummykung de Lamar\\::]] || (a,b,c > 0,a+b+c=3) $$\sqrt a+\sqrt b+\sqrt c\geq ab+ac+bc$$ 13 มีนาคม 2005 13:25 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ R-Tummykung de Lamar |
#3
|
|||
|
|||
ข้อ 1 เป็นปัญหาที่เรียกโดยทั่วไปว่าปัญหา Ramsey Number ครับ เป็นปัญหาที่ยากและมีพัฒนาการน้อยมากเมื่อเทียบกับงานวิจัยในเรื่องอื่นๆ แต่ปัญหาข้อนี้มีวิธีคิดได้หลายแบบครับ อาจจะใช้ Pigeonhole Principle(หรือ Dirichlet Drawer Principle) หรืออาจจะเป็นเรื่องของ Complete bipartite graph ก็ได้ครับ ไม่แน่ใจว่าจะใช้พวก Coloring ได้รึปล่าว แต่คิดว่าน่าจะใช้ได้นะ
__________________
site:mathcenter.net คำค้น |
#4
|
||||
|
||||
ข้อ 3 ก่อนนะครับ.
ปัญหาข้อนี้ใช้ Trick ที่ว่า จำนวนเต็มใด n ใดๆ จะสามารถเขียนได้ในรูปของ 2p ดq เสมอ เมื่อ p ฮ {0, 1, 2, ... } หรือ จำนวนเต็มที่มากกว่าหรือเท่ากับศูนย์ และ q ฮ {..., -3, 1, 1, 3, ...} หรือ จำนวนเต็มคี่ใด ๆ เช่น 12 = 22 ด 3 24 = 23 ด 3 27 = 20 ด 27 เหตุผลง่าย ๆ ก็คือ ถ้า n เป็นจำนวนคี่ ก็สามารถเขียนได้ว่า n = 20 ด n แต่ถ้า n เป็นจำนวนเต็มคู่ เราก็จะนำ 2 ไปหารเรื่อย ๆ จนกว่าจะได้จะจำนวนคี่ ดังนั้น q ทั้งหมดที่เป็นไปได้จะมีตั้งแต่ 1, 3, 5, ... , 399 รวมทั้งหมด 200 จำนวน สมมติให้มีรังนกทั้งหมด 200 รัง โดยที่แต่ละรัง แทนจำนวนคี่ตั้งแต่ 1, 3, 5, ... , 399 ดังนั้น ถ้าเราหยิบจำนวนเต็มใด ๆ 201 จำนวน จากเซต {1, 2, 3, ... , 400} แล้วเขียนจำนวนดังกล่าวในรูป ของ 2p ด q เราก็จะได้ว่า จะต้องมีอย่างน้อย 2 จำนวน ที่มีค่า q เท่ากัน (คือเป็นจำนวนเต็มคี่ตัวเดียวกัน) แต่ p ไม่เท่ากัน (เพราะถ้าทั้ง q และ p เท่ากัน แสดงว่าเป็นจำนวนเดียวกัน) สมมติว่าเป็น 2a ด q และ 2b ด q จะเห็นได้เมื่อนำจำนวนทั้งสองมาหารกัน จำนวนที่มีเลขชี้นกำลังของ 2 มากกว่า ก็จะหาร จำนวนที่มีเลขชี้กำลังของ 2 น้อยกว่าได้ลงตัว เสมอ |
#5
|
||||
|
||||
ข้อ 1 version P.P.
ในข้อนี้จะแบ่งปัญหาออกเป็น 2 แบบ แบบแรก มีอยู่ 3 คนที่รู้จักกัน และ แบบที่สองมีอยู่ 3 คน ที่ไม่รู้จักกันเลย สมมติให้ x เป็นคน ๆ หนึ่งในกลุ่มดังกล่าว ดังนั้นจะเหลือคนอยู่ 5 คน ซึ่งแบ่งออกเป็น 2 ประเภท คือ ประเภทที่รู้จักกับ x กับ ประเภทไม่รู้จักกับ x ในที่นี้มีรังอยู่ 2 รัง คือ รังที่รู้จักกับ x กับ รังที่ไม่รู้จักกับ x และ มีนกอยู่ 5 ตัว โดยหลักรังนกพิราบ จะได้ว่า จะมีนกอย่างน้อย 3 ตัวที่อยู่รังเดียวกัน กรณีที่ 1 : นกอย่างน้อย 3 ตัวที่ว่าอยู่รังที่รู้จักกับ x นกกลุ่มนี้ก็จะแบ่งออกเป็น 2 กรณีใหญ่ ๆ คือ กรณีที่มีนก 2 ตัวใด ๆ รู้จักกัน กับ ไม่มีนก 2 ตัวใดเลยที่รู้จักกัน กรณีที่ 1.1 ถ้ามีนก 2 ตัวใด ๆ ที่รู้จักกัน เมื่อรวมกับนก x ก็จะรู้จักกันรวมกันเป็น 3 ตัวพอดี ซึ่งเป็นแบบแรก กรณีที่ 1.2 ถ้าไม่มีนก 2 ตัวใดเลยที่รู้จักกัน ก็จะไปเข้าแบบหลัง คือ ไม่มีนกที่รู้จักกันเลย 3 ตัว ก็จะเป็นแบบหลัง กรณีที่ 2 นกอย่างน้อย 3 ตัว อยู่รังที่ไม่รู้จักกับ x นกกลุ่มนี้ก็จะแบ่งออกเป็น 2 กรณีใหญ่ ๆ คือ กรณีที่มีนก 2 ตัวใด ๆ ไม่รู้จักกัน กับ กรณีที่ นกทุกตัวรู้จักกันหมด กรณีที่ 2.1 ถ้ามีนก 2 ตัวใด ๆ ที่ไม่รู้จักกัน เมื่อรวมกับ x ด้วย ก็จะไม่รู้จักกันรวม 3 ตัวพอดี ซึ่งเป็นแบบหลัง กรณีที่ 2.2 ถ้านกทุกตัวรู้จักกันหมด ก็จะเป็นแบบแรก |
#6
|
|||
|
|||
ก็พอจะทำได้แล้วนะครับ ทั้งหมดเลย
ขอบคุณสำหรับแนวคิดนะครับ |
#7
|
||||
|
||||
ข้อ 2 น้อง Tony ทำอย่างไงครับ. อธิบายแนวคิดให้ฟังหน่อยสิ.
|
#8
|
|||
|
|||
ให้ ai = จำนวนทั้งหมดจนถึงวันที่ i
จะได้ 1ฃ a1,a2,a3,...,a30ฃ45 พบว่าเป็นลำบเพิ่มอย่างแท้จริง aiนaj a1+4,a2+14,a3+14,...,a30+14ฃ59 1ฃ a1,a2,a3,...,a30,a1+4,a2+14,a3+14,...,a30+14ฃ59 แสดงว่ามีอยู่ ai=aj+14 ai-14=aj นั่นคือ จำนวนวันตั้งแต่วันที่ j ถึงวันที่ i มี 14 เกม |
#9
|
||||
|
||||
ท่าทางน้อง Tony น่าจะบรรลุุเรื่องนี้แล้ว. ขอบคุณที่มาแสดงวิธีคิดนะครับ.
|
#10
|
|||
|
|||
ว้าว...ที่แท้ข้อ 2. ก็ทำอย่างนี้นี่เอง รอดูเฉลยมานานแล้วครับ ขอบคุณ คุณ Tony หลายๆเด้อ
|
|
|