ผลต่างระหว่างรุ่นของ "ตอนที่ 2: เจ้าเมืองจอมขี้เกียจ"
Parinya (คุย | มีส่วนร่วม) (→ปัญหา) |
Parinya (คุย | มีส่วนร่วม) (→ปัญหา) |
||
แถว 8: | แถว 8: | ||
พิจารณาปัญหาทั่วไปในปริภูมิ n มิติ <math>R^n</math> ต้องการวางจุดลงไป m จุด a_1, a_2, \ldots, a_m โดยที่มีเงื่อนไขดังนี้ | พิจารณาปัญหาทั่วไปในปริภูมิ n มิติ <math>R^n</math> ต้องการวางจุดลงไป m จุด a_1, a_2, \ldots, a_m โดยที่มีเงื่อนไขดังนี้ | ||
+ | |||
<math>||a_i - a_j|| = d_1</math> or <math>d_2</math> สำหรับทุกๆคู่จุด i,j | <math>||a_i - a_j|| = d_1</math> or <math>d_2</math> สำหรับทุกๆคู่จุด i,j | ||
+ | |||
ให้หาค่า m ที่มากที่สุดที่เป็นไปได้ | ให้หาค่า m ที่มากที่สุดที่เป็นไปได้ | ||
+ | |||
+ | ก่อนอื่นลองมาดูกรณีง่ายกว่านี้กันก่อน ถ้าให้ระยะทางที่เป็นไปได้มีเพียงแบบเดียว สังเกตว่าเราจะได้ | ||
+ | |||
+ | <math>m \le n+1 </math> | ||
+ | |||
+ | โดยที่กรณีที่ใส่จุดไปได้มากที่สุดคือ วางจุดลงไปบนจุดยอดของ regular simplex (ผู้อ่านลองคิดดู) | ||
+ | |||
+ | ทีนี้ลองกลับมาดูปัญหาของเรากันบ้าง หากระยะทางที่เป็นไปได้มีสองค่า วิธีที่ดีที่สุดจะไม่ชัดเจนเหมือนกับกรณีที่มีระยะทางค่าเดียวอีกต่อไป ความเป็นไปได้จะเพิ่มขึ้นอย่างมาก ก่อนจะอ่านเฉลย ผู้อ่านลองเดากันดูว่าคำตอบของ m ที่ดีที่สุดควรเป็นเท่าใด | ||
+ | |||
+ | == วิธีทำ == |
รุ่นแก้ไขเมื่อ 02:58, 25 พฤศจิกายน 2549
เกริ่น
มีเจ้าเมืองแห่งหนึ่ง นามว่าดนุพล มีนิสัยค่อนข้างเกียจคร้านและแปลกประหลาดยิ่งนัก เจ้าเมืองไม่ชอบให้บ้านในเมืองอยู่ห่างกันเกินไป จึงสั่งว่าให้ทุกบ้านในเมืองสร้างบ้านให้ระยะทางระหว่างสองบ้านใดๆเป็น 1 หรือ 2 เท่านั้น หากใครทำผิดกฎจะต้องโดนลงโทษอย่างรุนแรง ที่ต้องให้เป็นแค่สองค่า เพื่อที่จะให้ง่ายต่อเจ้าเมืองในการทำแผนที่ และการจำระยะทางระหว่างคู่บ้าน
นักคณิตศาสตร์ผู้หนึ่งมีไหวพริบเป็นเลิศจึงออกมาท้วงว่า หากเจ้าเมืองทำเช่นนั้น จำนวนบ้านที่สร้างได้จะไม่เกิน 8-9 หลังเท่านั้น หรืออาจจะน้อยกว่านั้น เจ้าเมืองรู้สึกเคืองเป็นอย่้างมากที่โดนขัดใจ จึงให้นักคณิตศาสตร์อธิบายว่า้เพราะอะไร
ปัญหา
พิจารณาปัญหาทั่วไปในปริภูมิ n มิติ ต้องการวางจุดลงไป m จุด a_1, a_2, \ldots, a_m โดยที่มีเงื่อนไขดังนี้
or สำหรับทุกๆคู่จุด i,j
ให้หาค่า m ที่มากที่สุดที่เป็นไปได้
ก่อนอื่นลองมาดูกรณีง่ายกว่านี้กันก่อน ถ้าให้ระยะทางที่เป็นไปได้มีเพียงแบบเดียว สังเกตว่าเราจะได้
โดยที่กรณีที่ใส่จุดไปได้มากที่สุดคือ วางจุดลงไปบนจุดยอดของ regular simplex (ผู้อ่านลองคิดดู)
ทีนี้ลองกลับมาดูปัญหาของเรากันบ้าง หากระยะทางที่เป็นไปได้มีสองค่า วิธีที่ดีที่สุดจะไม่ชัดเจนเหมือนกับกรณีที่มีระยะทางค่าเดียวอีกต่อไป ความเป็นไปได้จะเพิ่มขึ้นอย่างมาก ก่อนจะอ่านเฉลย ผู้อ่านลองเดากันดูว่าคำตอบของ m ที่ดีที่สุดควรเป็นเท่าใด