ก่อนหน้านี้ไม่นาน นักคณิตศาสตร์ได้ค้นพบว่า จำนวนครั้งที่ต้องใช้ในการหมุนเพื่อแก้รูบิค 3x3x3 ใดๆ จะมีค่าไม่เกิน 20 ครั้ง ไม่ว่ารูบิคลูกนั้นจะมีสภาพเริ่มต้นอย่างไรก็ตาม (สำหรับรูบิคมาตรฐาน 3x3x3 ที่ประกอบเป็นลูกบาศก์หกหน้า มีรูปแบบสภาพเริ่มต้นที่เป็นไปได้ 48 ล้านล้านล้านรูปแบบ) แต่ทีมวิจัยที่นำโดย Erik Demaine แห่ง MIT ได้คิดค้นสมการที่อธิบายความสัมพันธ์ของจำนวนครั้งมากที่สุดที่ต้องใช้กับขนาดของรูบิคได้ และที่สำคัญไม่ใช่แค่เฉพาะรูบิค 3x3x3 เท่านั้น แต่สมการนี้ใช้ได้กับรูบิค 4x4x4, 5x5x5, 6x6x6 หรือขนาดใดๆ ก็ได้

สมการนั้นคือ

สำหรับรูบิคขนาด n x n x n
จำนวนครั้งมากที่สุดที่ต้องใช้ในการหมุนจะแปรผันตาม n²/log n

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

บทความวิจัยของพวกเขาสามารถดาวน์โหลดได้จาก arxiv.org/abs/1106.5736 และงานวิจัยนี้จะถูกนำเสนอในงาน 19th Annual European Symposium on Algorithms เดือนกันยายน 2011 นี้

ที่มา - New Scientist, PhysOrg, LiveScience

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

เมื่อปี 1995 ตัวเลขขั้นสูงอยู่ที่ 29 ครั้ง และลดลงมาเรื่อยๆ เมื่อมีคนคิดเทคนิคใหม่ๆ ที่ลดจำนวนครั้งที่จำเป็นลงไปได้ แต่ทีม Morley Davidson, John Dethridge, Herbert Kociemba, และ Tomas Rokicki ก็ขอบริจาคเวลาทำงานของซีพียูจากกูเกิลเพื่อพิสูจน์ว่าจำนวนครั้งที่ต้องหมุนเพื่อแก้ปัญหา Rubik ทุกรูปแบบนั้นคือ 20 ครั้ง

Rubik นั้นมีความเป็นไปได้ของตำแหน่งต่างๆ อยู่ 43,252,003,274,489,856,000 ตำแหน่ง ทีมงานอาศัยการลดรูปแบบต่างๆ จนได้ปัญหาที่ต้องการแก้จริงๆ 55,882,296 กรณี แล้วคำนวณทีละกรณีจนกว่าจะเจอคำตอบที่ต้องหมุนน้อยกว่าหรือเท่ากับ 20 ครั้ง

กูเกิลบริจาคเวลาการทำงานของซีพียูเป็นเวลา 1 สัปดาห์ให้ทีมงานจนกระทั่งสามารถคำนวณทุกรูปแบบสำเร้จ กินเวลาซีพียูรวม 35 ปี โดยกูเกิลไม่เปิดเผยว่าเครื่องที่ให้รันนั้นจริงๆ แล้วมีกี่เครื่องกันแน่

น่าจะพิมพ์หนังสือขายได้ถ้ามันไม่หนาเกินไป

ที่มา - Cube20