ตอนที่ 2: เจ้าเมืองจอมขี้เกียจ

เกริ่น

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

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

ปัญหา

พิจารณาปัญหาทั่วไปในปริภูมิ n มิติ $R^{n}$ ต้องการวางจุดลงไป m จุด $a_{1},a_{2},\ldots ,a_{m}$ โดยที่มีเงื่อนไขดังนี้

$||a_{i}-a_{j}||=d_{1}$ or $d_{2}$ สำหรับทุกๆคู่จุด i,j

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

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

$m\leq n+1$

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

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

วิธีทำ

ปัญหานี้สามารถแก้ได้ในหลายๆทาง วิธีที่จะนำเสนอในที่นี้เป็นวิธีที่แสดงให้เห็นถึงการเชื่อมต่อของสองสิ่งที่ไม่น่าจะเข้ามาเกี่ยวข้องกันได้ (สิ่งนี้เป็นสิ่งที่มักจะเกิดขึ้นบ่อยๆในสาขาคณิตศาสตร์ซึ่งเป็นสาขาที่ไม่มีที่สิ้นสุด) หากอ่านโจทย์ดูคร่าวๆแล้ว ปัญหานี้เป็นปัญหาของ Geometry แต่วิธีที่จะนำเสนอนั้นแทบไม่เกี่ยวกับ Geometry เลยแม้แต่น้อย เราจะพิสูจน์ข้อความต่อไปนี้

ทฤษฎีบท 1: ค่าของ m ที่มากทีุ่สุดจะไม่เกิน $(n+1)(n+4)/2$

บทพิสูจน์: พิจารณาจุดสองจุด $x,y\in R^{n}$ เราอาจจะมองว่า $x=(x_{1},x_{2},\ldots ,x_{n})$ นิยามพหุนามหลายตัวแปร F ดังนี้

$F(x,y)=(||x-y||^{2}-d_{1}^{2})(||x-y||^{2}-d_{2}^{2})$

สังเกตว่าพหุนามมีคุณสมบัติคือ

$F(a_{i},a_{j})=\left\{{\begin{matrix}(d_{1}d_{2})^{2}{\mbox{ if }}i=j\\0\end{matrix}}\right.$

นิยามพหุนาม

$f_{i}=F(x,a_{i})$

ให้มองพหุนาม $f_{i}$ ในรูปแบบของเว็กเตอร์ (สำหรับคนที่ไม่คุ้นเคยกับแนวคิดแบบนี้ ตัวอย่างการมองพหุนามในแบบของเว็กเตอร์คือ การมอง $1+x+2x^{3}$ ในรูปของ $(1,1,0,2)$) ก่อนอื่นเราจะให้ผู้่อ่านเชื่อไปก่อนว่า $f_{1},f_{2},\ldots ,f_{m}$ เป็นเว็กเตอร์ที่ไม่ขึ้นต่อกันเชิงเส้น แล้วเราจะกลับมาพิสูจน์ข้อความนี้ทีหลัง

สังเกตว่าหากเรามีจุดที่อยู่ในปริภูมิทั้งหมด m จุด เราสามารถสร้างเวกเตอร์ที่ไม่ขึ้นต่อกันเชิงเส้นได้ m เวกเตอร์ ดังนั้นเราจะได้ว่า

$m\leq dim(V)$

เมื่อ V เป็นเซ็ตของพหุนามที่เป็นไปได้ทั้งหมด

$V=\{F(x,y):y\in R^{n}\}$

เราลองมาหาค่า dimension ของ V กัน จะตรวจสอบได้ไม่ยากว่าพหุนามในเซ็ต V จะอยู่ในรูปแบบต่อไปนี้

$(\sum _{j=1}^{n}x_{j}^{2})^{2}+\sum _{j=1}^{n}a_{j}x_{j}(\sum _{i=1}^{n}x_{i}^{2})+\sum _{i,j=1}^{n}b_{ij}x_{i}x_{j}+\sum _{j=1}^{n}c_{j}x_{j}+d$

สัมประสิทธ์ที่ไม่เป็นศูนย์ของพหุนามใน V มีได้มากที่สุดไม่เกิน

$1+n+n(n+1)/2+n+1={\frac {(n+1)(n+4)}{2}}$

ตำแหน่ง

Lower bound

เราได้เห็นกันแล้วว่าเราวางจุดลงไปได้ไม่มากนัก คราวนี้ลองมาดูกันบ้างว่าเราสามารถวางจุดลงไปได้อย่างน้อยกี่จุด เราจะได้มาเห็นวิธีคิดแบบไม่ยากนักที่ทำให้วางจุดลงไปได้ ${n+1 \choose 2}$ จุด

วิธีนี้สั้นอย่างมาก และผู้เขียนเองก็คงไม่สามารถค้นพบวิธีนี้ได้ด้วยตนเอง ก่อนอื่น ลองพยายามวางจุดลงไปใน $R^{n+1}$ จะเห็นว่า เราวางจุดต่อไปนี้ลงไปได้

$P=\{v\in \{0,1\}^{n+1}:\sum _{i=1}^{n+1}v_{i}=2\}$

พูดเป็นภาษามนุึษย์ก็คือ P เป็นเซ็ตของจุดที่มี 1 อยู่สองตำแหน่ง ที่เหลือเป็น 0

จะเห็นว่าระยะทางระหว่างคู่จุดใน P เป็น 2 หรือ ${\sqrt {2}}$ เท่านั้น แต่ยังติดปัญหาอย่างหนึ่งคือ จุดเหล่านี้อยู่ใน $R^{n+1}$ ไม่ใช่ $R^{n}$ ปัญหานี้จะหายไปทันที ด้วยข้อสังเกตว่าจุดเหล่านี้อยู่บน hyperplane $\sum _{i=1}^{n+1}x_{i}=2$ ดังนั้นมิติของเซ็ต P จึงไม่เกิน n ทำให้เซ็ต P สามารถมองว่าเป็นจุดบน $R^{n}$ ได้

โจทย์คิดเล่น

1. ให้แสดงว่าปัญหาของเจ้าเมืองดนุพลกับนักคณิตศาสตร์สามารถวางจุดลงไปได้ 5 จุด และไม่สามารถวางได้มากกว่า 5
2. พิสูจน์ว่าปัญหาของระยะทางแบบเดียว ไม่สามารถวางจุดได้มากกว่า n+1