การแบ่งเหรียญเป็นสองกลุ่มกับความไม่แน่นอน
 

เริ่มจากปัญหาง่ายๆ ถ้าเรามีเหรียนอยู่$n$เหรียน เราจะแบ่งเหรียนเป็นสองกลุ่มได้ $n-1$ วิธี

ถ้าเหรียนนั่นสุ่มหัวกับก้อยเราจะแบ่งเหรียนได้ $2^n*n-1$ วิธี ซึ่งใหญ่กว่าเหรียนกลุ่มเดียวซึ่งมีเพียง $2^n$ วิธี

ซึ่งถ้าเราเอามาเทียบกันแบบหนึ่งต่อหนึ่งเราจะพบว่าความแตกต่างของจำนวนเหรียนที่ต้องการใช้ในการจับคู่จะเพิ่มขึ้นเมื่อ $n$ ใหญ่ขึ้นซึ่งเราสามารถสร้างความแตกต่างของเหรียนเท่าไหร่ก็ได้ถ้า $n$ ใหญ่พอ

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

เพื่อนๆมีความเห็นว่าอย่างไรครับ

โทษที อธิบายข้ามไป คือถ้าเกิดสร้างโปรแกรมแบ่ง ที่เล็กกว่าได้ ก็แสดงว่าสามารถ จับคู่หนึ่งต่อหนึ่งจำนวนที่ขนาดไม่เท่ากันได้ นั่นทำให้เกิดความไม่แน่นอนเกิดขึ้น

เหรียญ :mellow:

ถึงว่ารู้สึกแปลกๆ สะกดผิดนี่เอง :unsure: