3x+1 problem

[picmy]

ห่างหายไปนานสำหรับการเข้ามาเยี่ยมชมเว็บบอร์ดนี้ เนื่องจากช่วงก่อนหน้านี้ต้องยุ่งกับการเขียนวิทยานิพนธ์ แต่ตอนนี้ได้ทำสำเร็จเสร็จสิ้น

ผมอยากจะนำหัวข้อที่ผมทำมาแนะนำให้กับเพื่อนๆ พี่ๆ น้องๆ ได้รู้จักกัน
ปัญหาที่ผมทำเป็นปัญหาที่นักคณิตศาสตร์รู้จักกันในนาม “ปัญหา 3x+1” (ปัญหานี้ยังมีชื่อเรียกอีกมากมาย อย่างเช่น Collatz conjecture, Ulam conjecture , Kakutani's problem , Thwaites conjecture , Hasse's algorithm ,Syracuse problem)

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

ยกตัวอย่างเช่น เริ่มจาก 7 ใช้กระบวนการข้างบนจะได้ว่า $7\rightarrow 22\rightarrow 11\rightarrow 34 \rightarrow 17\rightarrow 52\rightarrow 26\rightarrow 13\rightarrow 40\rightarrow 20\rightarrow 10\rightarrow 5\rightarrow 16\rightarrow 8\rightarrow 4\rightarrow 2\rightarrow 1$

จนถึงปัจจุบัน นักคณิตศาสตร์ได้ทดลองแล้วว่าถ้าเริ่มจากจำนวนเต็มบวกที่น้อยกว่าเท่ากับ $20 \times 2^{58}$ สุดท้ายก็จะไปจบลงที่ 1 ทุกครั้ง

จุดเริ่มต้นของปัญหานี้ ไม่มีใครทราบแน่นอน แต่ตามที่นักคณิตศาสตร์พูดกัน ก็ว่ากันว่าเริ่มมาจากนักคณิตศาสตร์ที่มีชื่อว่า Collatz (ในศตวรรษที่ ๓๐) หลังจากนั้นก็มีนักคณิตสาสตร์อีกหลายท่านสนใจในปัญหานี้ อย่างเช่น Ulam, Kakutani,Thwates,Hasse นอกจากนี้ยังมีคนเสนอเงินรางวัลสำหรับคนที่แก้ปัญหานี้ได้อีกด้วย อย่างเช่นในปี 1970 Coxeter เสนอ ๕๐ ดอลลาร์ ต่อมา Paul Erdos เสนอ ๕๐๐ ดอลลาร์ และสุดท้าย Thwaites เสนอ ๑๐๐๐ ปอนด์ (เงินจำนวนนี้ในสมัยนั้น ผมว่าสำหรับโจทย์เลขข้อนึง ก็เยอะพอสมควรเลยทีเดียว )

นักคณิตศาสตร์ชื่อดัง Paul Erdos (หรือที่คนไทยรู้จักกันในนาม พอล แอร์ดิช ผู้ชายที่หลงรักตัวเลข) เคยกล่าวถึงปัญหานี้ไว้ว่า "Mathematics is not yet ready for such problems." อย่างไรก็ตาม เคยมีคนเชื่อว่าหลังจากทฤษฎีบทสุดท้ายของแฟร์มาต์ได้รับการพิสูจน์ ทฤษฏีบทที่ยิ่งใหญ่อันต่อไปที่จะได้รับการพิสูจน์ก็คือ ปัญหา 3x+1 แต่ทว่า ตอนนี้ก็ผ่านมา ๑๐ กว่าปีแล้วที่ทฤษฎีบทสุดท้ายของแฟร์มาต์ได้รับการพิสูจน์ แต่ก็ยังไม่มีใครสามารถแก้ปัญหา 3x+1 ได้

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

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

[Switchgear]

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

[picmy]

วิทยานิพนธ์ที่ผมทำ แบ่งเป็นสองส่วนใหญ่ๆครับ

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

ส่วนที่สอง ผมก็เสนอแนวความคิดใหม่ๆ ซึ่งอาจจะเป็นลู่ทางในการแก้ปัญหาในอนาคตต่อไป

สำหรับคนที่สนใจปัญหานี้ ผมมีข้อเท็จจริงง่ายๆเกี่ยวกับปัญหา 3x+1 มาฝากครับ
สมมตินะครับว่า มีจำนวนเต็มบวกอยู่ตัวหนึ่ง ที่พอผ่านกระบวนการข้างบนแล้ว ปรากฎว่าไม่ไปจบลงที่ 1
ไม่ยากที่จะพบว่า ในกรณีนี้ มีความเป็นไปได้อยู่แค่สองรูปแบบคือ ไม่พุ่งสู่อนันต์ ก็เข้าสู่ loop (เช่น $a\rightarrow b \rightarrow c \rightarrow a\rightarrow b \rightarrow c... $)โดยที่ใน loop นั้นไม่มี 1