#1
|
||||
|
||||
Ramsey's Number
ขอโทษนะครับ ช่วยไกด์วิธีพิสูจน์ว่า R(4,4)=18 โดยใช้หลักรังนกพิราบหน่อยครับ
__________________
Nothing is impossible.The word itself says"I'm possible!" ไปสอบเพื่อหาความรู้ หาประสบการณ์ ได้ไม่ได้รางวัลถือเป็นของแถม แต่.....ได้มาบ้างก็ดีนะ สู้ต่อไป เพื่ออนาคตที่ดีกว่า |
#2
|
|||
|
|||
เห็นบ่นจะสอบแล้วเอาเฉลยไปเลยละกัน
ไปหาโหลดหลังสือเล่มนี้มา Arthur Engel - Problem Solving Strategies (ถ้าในค่ายซื้อเล่มนี้มาแล้วก็เปิดดูเลย) เฉลยอยู่บท Box principle หน้า 77 ข้อ 42 แต่บทพิสูจน์ใช้กราฟนะ วิธีก็พยายามพิสูจน์ตัว bound ล่าง คือ $R(4,4) > 17$ ให้ไปชนกับตัว Bound บน ซึ่ง Bound บนก็มาจาก $R(r,s) \leq R(r-1,s)+R(r,s-1)$ ทีนี้ตัวเฉลยมันใช้ pigeon ไม่เด่นชัดเท่าไร (ลงผมยังไม่เห็นคำว่า pigeon ในเฉลยเลย) ตัว bound ล่างในเฉลย มันใช้วิธีสร้าง $G_{17}$ ขึ้นมาแล้วบอกว่า 17 node นี้ไม่มี $K_{4}$ ถ้าก๊อปแบบนี้ไปตอบต่อให้ได้คะแนนก็อาจจะได้ไม่เต็มข้อ เพราะงั้นพยายามใช้ pigeon ให้ได้ชัดๆซักที่ในการ claim โจทย์นะ ไม่รู้นะความคิดผม ผมก็ช่วยได้แค่นี้ ปล.เอ๊อ สอบเสร็จโพสต์ข้อสอบให้หน่อยนะ จะลองมาทำดู |
#3
|
||||
|
||||
Bound บน
จะแสดงว่า $R(r,s)\leqslant R(r-1,s)+R(r,s-1)$ สมมติระบายสีเส้นเชื่อมทุกเส้นใน Complete Graph ที่มี $R(r-1,s)+R(r,s-1)$ จุดยอด ด้วยสีแดง/น้ำเงิน เลือกจุดยอดมา 1 จุดเรียกว่า A จะได้ว่า เส้นเชื่อม $R(r-1,s)+R(r,s-1)-1$ เส้นที่ผ่านจุดยอดนั้น ต้องมีอย่างน้อย $R(r-1,s)$ เส้นเป็นสีแดง หรืออย่างน้อย $R(r,s-1)$ เส้นเป็นสีน้ำเงิน (Pigeonhole) ถ้าเป็นกรณีแรก (อย่างน้อย $R(r-1,s)$ เส้นเป็นสีแดง) ใน $R(r-1,s)$ จุดที่เชื่อมด้วยสีแดงกับ A จะต้องมี complete graph size r-1 สีแดง หรือ complete graph size s สีน้ำเงิน กรณี complete graph size r-1 สีแดง ใชัจุดทั้ง r-1 จุดนั้นกับ A จะได้ complete graph size r สีแดง กรณี complete graph size s สีน้ำเงิน เห็นได้ชัด กรณีที่สอง (อย่างน้อย $R(r,s-1)$ เส้นเป็นสีน้ำเงิน) เป็นไปในทำนองเดียวกับกรณีแรก ดังนั้น $R(4,4)\leqslant R(3,4)+R(4,3)=2R(3,4)$ จะแสดงว่า $R(4,3)\leqslant 9$ นั่นคือ Complete graph ขนาด 9 จะต้องมี 3-clique สีแดง / 4-clique สีน้ำเงิน ถ้ามีจุดที่เส้นเชื่อมเป็นสี แดง อย่างน้อย 4 จาก R(2,4)=4 จะต้องมี 3-clique สีแดง / 4-clique สีน้ำเงิน (วิธีเหมือนกับข้างบนในแต่ละกรณี) ถ้ามีจุดที่เส้นเชื่อมเป็นสี น้ำเงิน อย่างน้อย 6 จาก R(3,3)=6 จะต้องมี 3-clique สีแดง / 4-clique สีน้ำเงิน ถ้าเป็นสี แดง 3 น้ำเงิน 5 ทุกจุด จะได้ว่าผลรวมดีกรีสีแดง $=9\times 3=27$ จึงต้องมีเส้นเชื่อมสีแดง $27\div 2=13.5$ เส้น เป็นไปไม่ได้ Bound ล่าง คิดว่าน่าจะไม่มีวิธีที่ดีกว่ายกตัวอย่างกรณี 17
__________________
16.7356 S 0 E 18:17:48 14/07/15 |
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
Number (การหารลงตัว) | BLACK-Dragon | ทฤษฎีจำนวน | 7 | 26 มกราคม 2013 09:50 |
Number หารลงตัวและกำลังสองสมบูรณ์ | Pain 7th | ทฤษฎีจำนวน | 6 | 05 ธันวาคม 2012 09:03 |
Number | Thgx0312555 | ทฤษฎีจำนวน | 9 | 14 กรกฎาคม 2012 14:15 |
Number ที่คิดไม่ออก | tatari/nightmare | ทฤษฎีจำนวน | 20 | 26 กันยายน 2008 21:21 |
เกี่ยวกับ Number | tatari/nightmare | ทฤษฎีจำนวน | 3 | 12 กันยายน 2007 22:12 |
|
|