1000^1000 กับ 1001^999 อะไรมากกว่ากัน?

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

จริงๆ ตอนก่อนก็แอบเกรียนไปหน่อย คือรู้แหละว่าตั้งใจจะให้พิสูจน์ทางคณิตศาสตร์ งั้นมาไถ่บาปกับคำถามที่ว่า 1000^1000 กับ 1001^999 (เวอร์ชั่นแก้คำผิดแล้ว) อะไรมากกว่ากันอีกรอบดีกว่า ;)

---

ก่อนอื่น สังเกตว่า

1000^1000 = 1000 * 1000^999

ที่เราต้องการคือ จัดรูปของ 1001^999 ให้กลายเป็น 1000^999 ให้ได้ ซึ่งก็ง่ายๆ โดนทำการกระจายทวินาม

1001^999 = (1000 + 1)^999
         = summation   C(999, i) * 1000^(999-i) * 1^i   for i from 0 to 999
         = summation   C(999, i) * 1000^(999-i)         for i from 0 to 999
         = 1000^999 + C(999, 1) * 1000^998 + C(999, 2) * 1000^997 + ... + 1

จะเห็นว่า พอกระจาย 1000^999 ออกมาแล้ว จะมี 1000 พจน์พอดี (index ไล่จาก 0 จนถึง 999) ซึ่งมันสามารถเอาไปจับคู่กับ 1000*1000^999 ได้ ดังนี้

pair(1000^1000, 1001^999) = [ (1000^999, 1000^999),
                              (1000^1 * 1000^998, C(999, 1) * 1000^998),
                              (1000^2 * 1000^997, C(999, 2) * 1000^997),
                              ...
                              (1000^i * 1000^(999-i), C(999, i) * 1000^(999-i)),
                              ...
                              (1000^999 * 1000^0, C(999, 999) * 1000^0) ]

จะเห็นว่า สิ่งที่ต้องการตรวจสอบคือ 1000^i กับ C(999, i) อะไรมากกว่ากัน

จาก

P(n, r) = n!/r!
C(n, r) = n!/(r!(n-r)!) = P(n, r)/(n-r)!

จะเห็นว่า P(n, r) มีค่ามากกว่าหรือเท่ากับ C(n, r) เสมอ

ถึงตรงนี้ก็เห็นชัดแล้วว่า

1000^0 = P(999, 0) = 999!/999! = 1
1000^1 > P(999, 1) = 999!/998! = 999
1000^2 > P(999, 2) = 999!/997! = 999 * 998
1000^3 > P(999, 3) = 999!/997! = 999 * 998 * 997
...
1000^n >= P(999, n) = 999!/(999-n)! = 999 * 998 * ... * (999-n)

ดังนั้น

1000^i >= P(999, i) >= C(999, i)   for all i in [0..999]

เพราะฉะนั้น

for i in [1..999]:
    summation 1000^i * 1000^(999-i) >= summation C(999, i) * 1000^(999-i)
    summation 1000^(i+999-i) >= summation C(999, i) * 1000^(999-i) * 1^i
    1000 * 1000^999 >= (1000 + 1)^999
    1000^1000 >= 1001^999

แต่เนื่องจาก มีบางพจน์ 1000^i ที่มีค่ามากกว่า C(999, i) ดังนั้น

1000^1000 > 1001^999

จบการพิสูจน์ครับ