วางจุดบนตารางหมากรุก (Points on Grid)

โจทย์

มีจุดทั้งหมด 3 จุด แต่ละจุดจะอยู่บนพิกัดที่ทั้ง x และ y เป็นจำนวนเต็ม

เราให้ระยะห่างคือผลต่างของพิกัด x รวมกับผลต่างของพิกัด y (Manhattan Distance)

เราต้องการเลือกพิกัดให้จุดเหล่านี้ โดยที่ระยะห่างระยะทางคู่จุดทุกคู่ต้องเท่ากับ 5 ถามว่ามีวิธีที่สามารถทำได้มั้ย หากทำได้ให้ระบุวิธี หากทำไม่ได้ให้ระบุเหตุผล

---

วิเคราะห์โจทย์

จริงๆ แล้ว ไม่ว่ายังไงมันก็ไม่มีทางทำได้แหละ แต่เพราะอะไรล่ะ?

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

บอกก่อนว่า: เราจะพยายามเขียนให้เข้าใจกันได้ง่ายที่สุดโดยที่จะไม่ลง proof ที่ formal มากนักอ่ะนะ แต่ถ้าอยากได้ formal proof ทักมาได้เหมือนกัน ถ้ามีเยอะๆเดี๋ยวจะมาอัพเดทหน้านี้อีกที

1. Proof จากสมการ

ก่อนอื่นเลย เรามากำหนดสัญลักษณ์เพื่อให้เรียกง่ายๆก่อน

โดยเราจะให้

• $d_{i,j}$ แทนระยะห่างของจุดที่ $i$ กับจุดที่ $j$ และ
• ($x_i,y_i$) คือพิกัดของจุดที่ $i$

ทีนี้ตัวโจทย์เราใช้ Manhattan Distance คือคิดระยะทางจากผลรวมของผลต่างของพิกัด x กับผลต่างของพิกัด y ซึ่งเขียนเป็นสมการระยะทางของจุด $i$ ไปจุด $j$ ได้ว่า

ซึ่งจากตัวเนื้อหาโจทย์ที่บอกว่าจุดทั้งสามต้องมีระยะห่างเท่ากันที่ 5 หน่วย เราจะเขียนสมการได้ว่า

ทีนี้ถ้าเราลองเอาสมการ $d_{1,2}, d_{2,3}, d_{1,3}$ ทั้ง 3 สมการมาบวกกันจะได้ว่า

เราสามารถจัดกลุ่มพจน์ที่มี x ให้อยู่ในกลุ่มเดียวกันและพจน์ที่มี y อยู่อีกกลุ่มนึงได้เป็น

ซึ่งเราจะพิสูจน์ได้ว่าไม่กลุ่ม x ก็กลุ่ม y ต้องมีซักกลุ่มที่มีค่าเป็นจำนวนคี่แล้วอีกกลุ่มต้องเป็นจำนวนคู่ ไม่งั้นมันบวกกันเป็น $15$ ที่เป็นจำนวนคี่ไม่ได้

โอเค… เมื่อกี้เราเคลมว่ามันต้องมีสักกลุ่มเป็นจำนวนคี่ถึงจะทำให้บวกกันได้ $15$ ได้ งั้นลองมาดูค่าของกลุ่ม $x$ ก่อนละกัน

เราจะสมมติเพิ่มให้จุดที่ 1 มีค่า $x$ มากที่สุด ซึ่งหมายความว่า $x_1 \geq x_2$ และ $x_1 \geq x_3$

หลังจากสมมติแบบนั้นไปแล้วเราจะได้พจน์ใหม่เป็น

ซึ่งสรุปต่อได้ว่า $2x_1$ ยังไงก็เป็นจำนวนคู่อยู่แล้ว เพราะมีจำนวนคู่คูณอยู่
ทีนี้จะเหลือพจน์ $-x_2-x_3+|x_2-x_3|$ ที่ต้องคิดต่อว่าเป็นเลขคู่หรือเลขคี่

เราก็สามารถคิดทั้งสองกรณีเลยก็ได้

ทั้งสองเคสได้เหมือนกันว่ามีตัวคูณข้างหน้าของ $x_2$ หรือ $x_3$ เป็น 0 หรือ -2 แล้วแต่ว่าเราจะตั้งให้ $x_2$ หรือ $x_3$ มากกว่ากัน

ซึ่งไม่ว่ายังไงก็มีตัวคูณนำหน้าเป็นจำนวนคู่อยู่แล้ว ก็เลยทำให้เป็นจำนวนคู่ตามไปด้วย ทำให้สรุปได้ว่ากลุ่มของค่า $x$ ที่เราดูอยู่เนี่ยเป็นจำนวนคู่แน่ๆ

ทีนี้เรารู้ว่าในกลุ่ม x เป็นจำนวนคู่แน่ๆ เราก็สามารถสรุปต่อได้ว่า กลุ่ม y ก็เป็นจำนวนคู่เช่นกัน เพราะมีรูปพจน์ในแบบเดียวกันเป๊ะๆ

ทีนี้กลับมาดูสมการที่เราได้ก่อนหน้านี้

สุดท้ายแล้วเรารู้ว่าทั้งกลุ่ม $x$ และ $y$ มีค่าเป็นจำนวนคู่ แปลว่าผลรวมก็ต้องเป็นจำนวนคู่
ซึ่งขัดแย้งกับสมการ $d_{1,2}+d_{2,3}+d_{1,3} = 15$ ซึ่งเป็นจำนวนคี่ ทำให้สรุปได้ว่าไม่สามารถเลือกจุดทั้ง 3 จุดได้

2. Proof จากการวาดตาราง

อีกวิธีนึงที่ดูเหมือนจะไม่ต้องทำอะไรยุ่งยากเหมือนวิธีที่แล้ว แต่อาจจะนึก(ฝัน) ยากกว่าคือ เราจะวาดตารางและระบายสี 2 สีบนตารางสลับๆกัน นึกถึงตารางหมากรุกก็ได้

เราจะเปลี่ยนให้แต่ละจุดที่อยู่บนพิกัดจำนวนเต็มมาเป็นช่องในตารางแทน

โดยจุดตรงกลางเรียกว่าตำแหน่ง $(0, 0)$ มีสีเขียวและจุดมุมซ้ายบนเรียกว่าตำแหน่ง $(-3, -3)$ เป็นสีเขียวเหมือนกัน
ทีนี้ลองมองรอบๆจุดตรงกลางนิดนึง

สรุป

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

ตัวอย่างโจทย์เพิ่มเติมเรื่อง Parity

https://people.math.carleton.ca/~kcheung/math/books/giam-ON/html/sec-parity.html