รูบิกมี 43 ล้านล้านล้านสถานะ นักคณิตศาสตร์พิสูจน์ขีดจำกัดได้อย่างไร

* รูปภาพใช้เพื่อประกอบเนื้อหาเท่านั้น อาจไม่ใช่ภาพเหตุการณ์จริงหรือภาพจริงจากเรื่องในบทความ ขอบคุณภาพประกอบจาก https://graphic.in.th

ลูกบาศก์รูบิก 3×3 มีสีอยู่เพียง 6 สี แต่เมื่อหมุนสลับชั้นไปเรื่อย ๆ ชิ้นส่วนเล็ก ๆ ทั้งหมดจะเปลี่ยนตำแหน่งจนแทบมองไม่ออกว่าต้องเริ่มแก้จากตรงไหน ความยุ่งเหยิงที่เห็นบนมือมีโครงสร้างทางคณิตศาสตร์ซ่อนอยู่ครบถ้วน

การหมุนแต่ละครั้งสร้างสถานะใหม่ขึ้นมา และจำนวนสถานะที่เกิดจากการหมุนอย่างถูกกติกามีมากเกินกว่าจะไล่ลองด้วยคนเพียงคนเดียว ต่อให้หมุนหนึ่งครั้งทุกวินาที การตรวจให้ครบก็ใช้เวลายาวนานเกินอายุมนุษย์

ตัวเลขของลูกบาศก์ 3×3

ตำแหน่งที่เป็นไปได้ของรูบิกคำนวณจากการสลับมุม 8 ชิ้น การบิดทิศของมุม การสลับขอบ 12 ชิ้น และการกลับด้านของขอบ เมื่อรวมเงื่อนไขทางกลไกของลูกบาศก์แล้ว จะได้จำนวนทั้งหมด 43,252,003,274,489,856,000 สถานะ หรือประมาณ 43 ล้านล้านล้านรูปแบบ

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

ในเดือนกรกฎาคม 2010 ทีมของ Tomas Rokicki, Herbert Kociemba, Morley Davidson และ John Dethridge พิสูจน์ได้ว่า ทุกสถานะของรูบิกสามารถแก้กลับเป็นลูกบาศก์สีเรียงกันได้ภายในไม่เกิน 20 ครั้ง ภายใต้เกณฑ์ที่การหมุนหน้าใด ๆ 90 องศาหรือ 180 องศานับเป็นหนึ่งครั้ง

ตัวเลข 20 นี้ถูกเรียกว่า God’s Number หรือเลขของพระเจ้า เป็นชื่อเปรียบเทียบถึงวิธีแก้ที่สั้นที่สุดในกรณีที่ยากที่สุด ไม่ได้หมายความว่าคนที่เพิ่งหยิบรูบิกขึ้นมาจะจำลำดับการหมุน 20 ครั้งแล้วแก้ได้ทันที

คอมพิวเตอร์ไม่ได้ลองทีละลูก

การนำรูบิกทั้ง 43 ล้านล้านล้านสถานะมาวางเรียงแล้วตรวจทีละแบบทำไม่ได้ ทีมวิจัยจึงแบ่งพื้นที่ของปัญหาออกเป็นชุดย่อยจำนวน 2,217,093,120 ชุด แต่ละชุดมี 19,508,428,800 สถานะ จากนั้นใช้สมมาตรของลูกบาศก์ เช่น การหมุนลูกทั้งลูกหรือการมองภาพสะท้อน เพื่อลดจำนวนชุดที่ต้องตรวจจริงเหลือ 55,882,296 ชุด

โปรแกรมที่ใช้สามารถค้นหาสถานะได้ประมาณหนึ่งพันล้านสถานะต่อวินาที การประมวลผลกระจายไปยังคอมพิวเตอร์ของ Google และเสร็จภายในเวลาไม่กี่สัปดาห์ หากใช้คอมพิวเตอร์ตั้งโต๊ะเครื่องเดียว งานชุดเดียวกันจะเทียบเท่ากับเวลาประมวลผลประมาณ 35 ปี

ทีมวิจัยไม่จำเป็นต้องหาลำดับที่สั้นที่สุดของทุกสถานะ เพราะมีสถานะที่พิสูจน์แล้วว่าต้องใช้ถึง 20 ครั้งอยู่ก่อนแล้ว สิ่งที่ต้องตรวจเพิ่มคือ ไม่มีสถานะใดใช้เกิน 20 ครั้ง เมื่อพบว่าทุกสถานะแก้ได้ภายในขอบเขตนี้ ค่าต่ำสุดและค่าสูงสุดจึงมาบรรจบกันที่เลข 20

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

20 ครั้งมีเงื่อนไขที่ต้องจำไว้

ค่า 20 ใช้เกณฑ์ที่เรียกว่า half-turn metric หมายถึงการหมุนหน้า 180 องศานับเป็นหนึ่งครั้ง หากบังคับให้นับการหมุน 90 องศาทีละหนึ่งครั้ง ตัวเลขขีดจำกัดจะเป็น 26 ครั้งแทน

วิธีแก้ที่มนุษย์เรียนจากคู่มือมักใช้จำนวนครั้งมากกว่านี้ เพราะต้องจำขั้นตอนเป็นช่วง ๆ และไม่ได้เลือกเส้นทางที่สั้นที่สุดสำหรับทุกสถานะ ส่วน God's Number เป็นคำตอบของคำถามเชิงคณิตศาสตร์ว่า สถานะที่ยุ่งที่สุดของรูบิกต้องใช้การหมุนอย่างน้อยกี่ครั้งในกรณีที่เลือกทางได้ดีที่สุด

ลูกบาศก์รูบิกจึงมีความพิเศษอยู่ที่ความแตกต่างระหว่างขนาดของปัญหากับขอบเขตของคำตอบ แม้จะมีสถานะมากกว่า 43 ล้านล้านล้านแบบ แต่เมื่อวัดระยะทางจากสถานะใด ๆ กลับถึงลูกบาศก์ที่แก้เสร็จแล้ว ระยะทางที่ไกลที่สุดในเกณฑ์นี้มีเพียง 20 ครั้ง