การแบ่งเหรียญเป็นสองกลุ่มกับความไม่แน่นอน
เริ่มจากปัญหาง่ายๆ ถ้าเรามีเหรียนอยู่$n$เหรียน เราจะแบ่งเหรียนเป็นสองกลุ่มได้ $n-1$ วิธี
ถ้าเหรียนนั่นสุ่มหัวกับก้อยเราจะแบ่งเหรียนได้ $2^n*n-1$ วิธี ซึ่งใหญ่กว่าเหรียนกลุ่มเดียวซึ่งมีเพียง $2^n$ วิธี
ซึ่งถ้าเราเอามาเทียบกันแบบหนึ่งต่อหนึ่งเราจะพบว่าความแตกต่างของจำนวนเหรียนที่ต้องการใช้ในการจับคู่จะเพิ่มขึ้นเมื่อ $n$ ใหญ่ขึ้นซึ่งเราสามารถสร้างความแตกต่างของเหรียนเท่าไหร่ก็ได้ถ้า $n$ ใหญ่พอ
ผมคิดว่าความแตกต่างของจำนวนเหรียนคือขนาดโปรแกรมที่สั้นที่สุดที่จะแบ่งไบนารี่เป็นสองกลุ่มโดยสามารถย้อนกลับได้
แต่ผมก็ยังเชื่อลึกๆอยู่ว่าบางทีอาจจะมีโปรแกรมที่สั้นกว่านั่นถ้าขนาดเหรียนเยอะมากๆหรือเราใช้โครงสร้างข้อมูลที่ซับซ้อนมากๆ ซึ่งนั่นจะสามารถใช้เป็นโปรแกรมบีบอัดข้อมูลได้ และเป็นข้อพิสูจน์ว่าคณิตศาสตร์ไม่แน่นอน
เพื่อนๆมีความเห็นว่าอย่างไรครับ
|
18 ธันวาคม 2014, 19:35
