ผลต่างระหว่างรุ่นของ "ตอนที่ 2: เจ้าเมืองจอมขี้เกียจ"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 7: แถว 7:
 
== ปัญหา ==
 
== ปัญหา ==
  
พิจารณาปัญหาทั่วไปในปริภูมิ n มิติ <math>R^n</math> ต้องการวางจุดลงไป m จุด a_1, a_2, \ldots, a_m โดยที่มีเงื่อนไขดังนี้  
+
พิจารณาปัญหาทั่วไปในปริภูมิ n มิติ <math>R^n</math> ต้องการวางจุดลงไป m จุด <math>a_1, a_2, \ldots, a_m</math> โดยที่มีเงื่อนไขดังนี้  
  
 
<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  
แถว 19: แถว 19:
 
โดยที่กรณีที่ใส่จุดไปได้มากที่สุดคือ วางจุดลงไปบนจุดยอดของ regular simplex (ผู้อ่านลองคิดดู)  
 
โดยที่กรณีที่ใส่จุดไปได้มากที่สุดคือ วางจุดลงไปบนจุดยอดของ regular simplex (ผู้อ่านลองคิดดู)  
  
ทีนี้ลองกลับมาดูปัญหาของเรากันบ้าง หากระยะทางที่เป็นไปได้มีสองค่า วิธีที่ดีที่สุดจะไม่ชัดเจนเหมือนกับกรณีที่มีระยะทางค่าเดียวอีกต่อไป ความเป็นไปได้จะเพิ่มขึ้นอย่างมาก ก่อนจะอ่านเฉลย ผู้อ่านลองเดากันดูว่าคำตอบของ m ที่ดีที่สุดควรเป็นเท่าใด  
+
ทีนี้ลองกลับมาดูปัญหาของเรากันบ้าง หากระยะทางที่เป็นไปได้มีสองค่า วิธีที่ดีที่สุดจะไม่ชัดเจนเหมือนกับกรณีที่มีระยะทางค่าเดียวอีกต่อไป ความเป็นไปได้จะเพิ่มขึ้นอย่างมาก ก่อนจะอ่านเฉลย ผู้อ่านลองเดากันดูว่าคำตอบของ m ที่ดีที่สุดควรเป็นเท่าใด
  
 
== วิธีทำ ==
 
== วิธีทำ ==

รุ่นแก้ไขเมื่อ 02:58, 25 พฤศจิกายน 2549

เกริ่น

มีเจ้าเมืองแห่งหนึ่ง นามว่าดนุพล มีนิสัยค่อนข้างเกียจคร้านและแปลกประหลาดยิ่งนัก เจ้าเมืองไม่ชอบให้บ้านในเมืองอยู่ห่างกันเกินไป จึงสั่งว่าให้ทุกบ้านในเมืองสร้างบ้านให้ระยะทางระหว่างสองบ้านใดๆเป็น 1 หรือ 2 เท่านั้น หากใครทำผิดกฎจะต้องโดนลงโทษอย่างรุนแรง ที่ต้องให้เป็นแค่สองค่า เพื่อที่จะให้ง่ายต่อเจ้าเมืองในการทำแผนที่ และการจำระยะทางระหว่างคู่บ้าน

นักคณิตศาสตร์ผู้หนึ่งมีไหวพริบเป็นเลิศจึงออกมาท้วงว่า หากเจ้าเมืองทำเช่นนั้น จำนวนบ้านที่สร้างได้จะไม่เกิน 8-9 หลังเท่านั้น หรืออาจจะน้อยกว่านั้น เจ้าเมืองรู้สึกเคืองเป็นอย่้างมากที่โดนขัดใจ จึงให้นักคณิตศาสตร์อธิบายว่า้เพราะอะไร

ปัญหา

พิจารณาปัญหาทั่วไปในปริภูมิ n มิติ ต้องการวางจุดลงไป m จุด โดยที่มีเงื่อนไขดังนี้

or สำหรับทุกๆคู่จุด i,j

ให้หาค่า m ที่มากที่สุดที่เป็นไปได้

ก่อนอื่นลองมาดูกรณีง่ายกว่านี้กันก่อน ถ้าให้ระยะทางที่เป็นไปได้มีเพียงแบบเดียว สังเกตว่าเราจะได้

โดยที่กรณีที่ใส่จุดไปได้มากที่สุดคือ วางจุดลงไปบนจุดยอดของ regular simplex (ผู้อ่านลองคิดดู)

ทีนี้ลองกลับมาดูปัญหาของเรากันบ้าง หากระยะทางที่เป็นไปได้มีสองค่า วิธีที่ดีที่สุดจะไม่ชัดเจนเหมือนกับกรณีที่มีระยะทางค่าเดียวอีกต่อไป ความเป็นไปได้จะเพิ่มขึ้นอย่างมาก ก่อนจะอ่านเฉลย ผู้อ่านลองเดากันดูว่าคำตอบของ m ที่ดีที่สุดควรเป็นเท่าใด

วิธีทำ