แต่ก่อนอื่นต้องเข้าใจกฎการแลกของขวัญ ซึ่งมีขั้นตอนประมาณนี้
- ทุกคนซื้อของขวัญมาร่วมสนุกในงานคนละอย่าง โดยเอาของขวัญใส่กล่องไว้ไม่ให้ใครรู้ว่าด้านในเป็นอะไร
- พอแต่ละคนไปถึงงาน คนจัดงานจะแปะป้ายชื่อเจ้าของของขวัญไว้กับกล่อง พร้อมหย่อนฉลากรายชื่อของคนนั้นลงไห
- เมื่อถึงเวลาแลกของขวัญ ให้ประธานในพิธีหรือใครซักคนที่ใหญ่ที่สุดในงาน เป็นคนเริ่มจับฉลากรายชื่อจากไหเป็นคนแรก
- ประธานจับได้ชื่อใครก็เอากล่องของขวัญของคนนั้นไป แล้วก็ให้คนที่โดนจับชื่อเมื่อกี้ เป็นคนเริ่มจับฉลากในไหวนต่อไปเรื่อยๆ
- ถ้าเกิดมีคนจับได้ชื่อประธาน จะถือว่าเป็นการแลกของขวัญที่ครบรอบวง ก็ให้คนนั้นเอาของขวัญของประธานไป แล้วผู้จัดงานเลือกใครซักคนจากคนที่ยังไม่ได้จับของขวัญ มาเป็นหัวจับของขวัญรอบต่อไป
- การแลกของขวัญจะสิ้นสุดลงเมื่อไม่มีฉลากรายชื่อเหลือในไห
ยกตัวอย่างให้ชัดขึ้นไปอีก สมมตินายประธานเป็นคนจับฉลากคนแรก แล้วก็มีคนจับตามๆ กันมาอีกหลายคน จนตอนสุดท้ายเหลือคนที่ยังไม่ได้จับฉลาก 2 คนคือสมศักดิ์กับมานี ถ้าคนก่อนหน้าจับฉลากได้ชื่อสมศักดิ์ แปลว่าสมศักดิ์จะเป็นคนจับฉลากคนต่อไป แต่รายชื่อในไหตอนนี้จะเหลือแค่มานีกับประธานเท่านั้น ที่โอกาสครึ่งๆ ถ้าสมศักดิ์จับได้ชื่อประธาน ก็จะเหลือคนไม่ได้จับฉลากคือมานี และฉลากที่เหลือในไหก็เป็นชื่อมานี นั่นก็คือมานีจะต้องจับฉลากได้ของขวัญของตัวเองแน่นอน
โอกาสที่ในงานแลกของขวัญงานหนึ่ง จะมีคนได้ของขวัญเป็นของตัวเองสูงถึง 50% ซึ่งจริงๆ แล้วโอกาสน่าจะมากกว่านี้อีกนิดหน่อยด้วยซ้ำ เพราะยังไม่ได้คิดโอกาสที่คนกลางๆ จะจับได้ของตัวเองทันทีหลังจากเกิดการจับฉลากครบรอบวงเลย
คิดได้แค่นี้ก็พอใจแล้ว แต่ก็โดน @NungNing ถามต่อว่า ถ้าไม่จับฉลากกันต่อไปเรื่อยๆ แบบนี้หละ แต่เปลี่ยนเป็นให้ทุกคนหยิบฉลากจากไหพร้อมกันเลย แล้วค่อยเปิดดูทีเดียวว่าใครได้ของขวัญจากใคร ยังจะมีโอกาสสูงอยู่มั้ยที่จะมีคนจับฉลากได้ของขวัญของตัวเอง?
ตอนนั้นหมดพลังแล้ว ให้คิดต่ออย่างเดียวคงไม่ออกแน่ๆ เลยเขียนโปรแกรมง่ายๆ มาดูค่าเอาเลยนั่นแหละ
#!/usr/bin/env python3 from random import shuffle from collections import Counter shuffled = lambda ls: shuffle(ls) or ls own_gift = lambda n: [i for i, j in enumerate(shuffled(list(range(n)))) if i == j]สมมติให้มีคนแลกของขวัญกัน 10 คน ทดลองไปล้านครั้ง พบว่ามีประมาณสามแสนหกหมื่นครั้งเท่านั้น (36%) ที่การแลกของขวัญนั้นจะไม่มีคนได้ของตัวเอง
ตอนนั้นก็ตกใจว่าเลข 36% มาจากไหน นึกว่าโอกาสไม่ได้ของตัวเองมันจะมีค่าสูงกว่า 50% ที่คิดได้จากการแลกของขวัญวนไปเรื่อยๆ ซะอีก นี่กลายเป็นว่าโอกาสไม่ได้ของตัวเองมันยิ่งเหลือน้อย เลยทดลองเพิ่มโดยนับแยกว่า ในแต่ละการทดลองแลกของขวัญนั้น มีคนกี่คนที่ได้ของขวัญของตัวเอง
ทดลองแลกของขวัญกัน 10 คนล้านครั้งเหมือนเดิม แล้วก็ตกใจเพิ่มกับหน้าตาผลลัพธ์ที่ไม่โกหกดังนี้
| จำนวนคนที่จับได้ของขวัญของตัวเอง | จำนวนครั้งของเหตุการณ์ที่เกิด | ข้อคาดการณ์โอกาสการเกิด |
|---|---|---|
| 0 | 368,243 | 1/0! x 1/e |
| 1 | 367,640 | 1/1! x 1/e |
| 2 | 183,800 | 1/2! x 1/e |
| 3 | 61,406 | 1/3! x 1/e |
| 4 | 15,269 | 1/4! x 1/e |
| 5 | 3,014 | 1/5! x 1/e |
| 6 | 545 | 1/6! x 1/e |
| 7 | 67 | 1/7! x 1/e |
| 8 | 16 | 1/8! x 1/e |
ถึงตอนนี้ก็พอจะเข้าใจแล้วว่ามันเกิดอะไรขึ้น
แม้แค่เห็นข้อมูลข้างบนแล้วจะสรุปได้ว่าเกิดอะไรขึ้น แต่เรื่องที่ยากกว่าก็คือการพิสูจน์หาคำอธิบายเป๊ะๆ ว่าทำไมถึงเป็นอย่างนั้น
เริ่มจากกรณีที่ไม่มีใครจับของขวัญได้ของตัวเองก่อน จะได้ว่า
- คนแรกมีโอกาสจะจับไม่ได้ของตัวเองที่
(n-1)/n - คนที่สองมีโอกาสที่จะจับไม่ได้ของตัวเอง แบ่งได้ 2 แบบ คือ
- คนแรกจับได้ของคนที่สองไปแล้ว (โอกาส
1/n) ดังนั้นคนที่สองจับไม่ได้ของตัวเองแน่ๆ (โอกาส1) รวมโอกาสได้เป็น1/n - คนแรกจับไม่ได้ของคนที่สอง (โอกาส
(n-1)/n) คนที่สองต้องจับหลบให้ไม่ได้ของตัวเอง (โอกาส(n-2)/(n-1)) รวมโอกาสได้เป็น((n-1)/n)((n-2)/(n-1)) - สรุปว่าโอกาสทั้งหมดที่คนที่สองจะจับไม่ได้ของตัวเองคือ
1/n + ((n-1)/n)((n-2)/(n-1))
- คนแรกจับได้ของคนที่สองไปแล้ว (โอกาส
- โอกาสคนที่สามจะคล้ายๆ กับของคนที่สอง คือ
2/n + ((n-2)/n)((n-3)/(n-2)) - คนที่
iมีโอกาส(i-1)/n + ((n-i-1)/n)((n-i)/(n-i-1))ที่จะจับไม่ได้ของตัวเอง
เนื่องจากเหตุการณ์ทั้งหมด ต้องเกิดขึ้นพร้อมกัน ดังนั้นสรุปได้ว่า
P(n คนไม่มีใครได้ของตัวเอง) = (n-1)/n x (1/n + ((n-1)/n)((n-2)/(n-1))
x ... x ((i-1)/n + ((n-i-1)/n)((n-i)/(n-i-1))
x ... x ((n-n)/n + 0)
= (n-1)/n x (1/n + (n-2)/n) x .... x ((i-1)/n + (n-i)/n) x ... x 1
= Product (n-1)/n for integer i from 1 to n-1
= Product 1 - 1/n for integer i from 1 to n-1
= (1-1/n)^(n-1)
จากสมการข้างต้น ถ้าลองแทนตัวเลขน้อยๆ เช่น n=1,2,3,4 เข้าไป จะได้คำตอบเป็น 1, 0.5, 0.445, 0.422 ตามลำดับ แต่เมื่อลองแทนเลขมากๆ แล้ว ผลลัพธ์จะลู่เข้าหาค่าเดียวกันคือ 0.367879... นั่นก็เพราะ limit (1-1/n)^(n-1) when n -> infinity = limit (1-1/n)^n when n -> infinity
= limit ((n-1)/n)^n when n -> infinity
= limit (n/(n+1))^n when n -> infinity
= limit 1/((n+1)/n)^n when n -> infinity
= 1/(limit ((n+1)/n)^n when n -> infinity)
= 1/(limit (1+1/n)^n when n -> infinity)
= 1/e
สวยมั้ย อยู่ดีๆ ก็ได้ค่า e ออกมาเฉยเลยส่วนการพิสูจน์กรณีมีคนได้ของขวัญของตัวเองแค่คนเดียว จะมีฟอร์มที่ต่างไปเล็กน้อยเนื่องจากเหตุการณ์จะไม่เกิดขึ้นต่อเนื่องกันแล้ว เขียนสมการออกมาได้เป็น
P(n คนมี 1 คนได้ของตัวเอง) = (1/n)P(n-1 คนไม่มีใครได้ของตัวเอง)
+ ((n-1)/n)(1/(n-1))P(n-2 คนไม่มีใครได้ของตัวเอง)
+ ...
+ ((n-(n-1))/n)(1/(n-(n-1)))P(n-n คนไม่มีใครได้ของตัวเอง)
= (1/n)P(n-1 คนไม่มีใครได้ของตัวเอง)
+ (1/n)P(n-2 คนไม่มีใครได้ของตัวเอง)
+ ...
+ (1/n)P(n-n คนไม่มีใครได้ของตัวเอง)
= (1/n)(Sum P(n-i คนไม่มีใครได้ของตัวเอง) for integer i from 1 to n)
สมมติว่ามีคนมาร่วมงานแลกของขวัญเยอะ อาจจะมองว่า P(n-i คนที่ไม่มีใครได้ของตัวเอง) มีค่าไม่แตกต่างกันสำหรับแต่ละค่า i เลยก็ได้ ทำให้เราสามารถยุบผลรวมยุ่งๆ ด้านหลัง ให้เหลือแค่เอาความน่าจะเป็นไปคูณด้วย n ก็พอ ซึ่งมันก็จะโดนหักล้างทิ้งไปกับ (1/n) ด้านหน้าทันทีดังนั้นจะได้ว่า ค่าความน่าจะเป็นของงานเลี้ยงแลกของขวัญที่จะมีคนหนึ่งคนได้จับได้ของตัวเอง เป็น
1/e เท่ากันกับกรณีไม่มีใครจับได้ของตัวเองเลยสำหรับกรณีที่มีคนสองคนจับได้ของตัวเอง จะเริ่มพิสูจน์ยุ่งยากมากขึ้นไปอีก แต่ใจความจะคล้ายๆ กับการพิสูจน์คนเดียวได้ของตัวเอง ซึ่งได้แก่การมองแยกกรณี โดยแบบที่หนึ่งจะให้คนแรกจับได้ของตัวเองไปแล้ว หลังจากนั้นจึงหาโอกาสของคนที่เหลือที่จะมีหนึ่งคนจับได้ของตัวเองเป็นเท่าไหร่ กับแบบที่สองที่ให้คนแรกจับไม่ได้ของตัวเอง แล้วหาโอกาสของคนที่เหลือที่จะมีสองคนจับได้ของตัวเองเป็นเท่าไหร่ (ถ้าคิดด้วยวิธีนี้ไม่ผิด จะได้หน้าตาสมการเป็นการหาผลรวมของเทอม
((n-k)/n)((n-k+1)/(n-1))((n-k+2)/(n-2))...(1/(n-k+1))P(n-k คนมี 1 คนได้ของตัวเอง))กรณีอื่นๆ ที่เหลือเนื่องด้วยพื้นที่กระดาษไม่พอเขี.... เฮ้ย ไม่ใช่แฟร์มาต์! จริงๆ แล้วต้องบอกว่าการพิสูจน์ด้วยท่านี้มันเริ่มยุ่งยากซับซ้อนจนไปต่อไม่ไหวแล้ว แต่ถ้ายังจำกันได้ นี่มันการแจกแจงปัวซองที่มีค่า
λ=1 ชัดๆ ก็เอาเป็นว่าใครอยากพิสูจน์ต่อก็ลองใช้ท่านี้ดูนะ อาจจะได้บทพิสูจน์ที่สั้นและสวยงามกว่าด้วยเห็นแล้วว่าการสุ่มจับฉลากทั้งหมดทีเดียวพร้อมกันมันไม่เวิร์ค กลับไปดูวิธีดั้งเดิมที่ค่อยๆ ให้จับฉลากทีละคน จับได้ชื่อใครก็ให้คนนั้นไปจับฉลากต่อ วิธีนี้เขียนเป็นโค้ดออกมาได้ว่า
from random import randint
def exchange(ls):
owned = [None for _ in ls]
current = 0
while ls:
if owned[current] is not None:
current = owned.index(None)
gone = randint(0, len(ls)-1)
owned[current] = ls[gone]
current = ls[gone]
del ls[gone]
return owned
เอาฟังก์ชัน exchange ไปแทนที่ฟังก์ชัน shuffled ข้างบนแล้วทดลองใหม่ ก็ได้ผลลัพธ์ที่ไม่ต่างไปจากตารางแรกซักเท่าไหร่เลยดังนั้นไม่ว่าจะให้จับฉลากพร้อมกันหมดในทีเดียว หรือจะค่อยๆ จับทีละคน พอจับได้ชื่อใครก็ให้คนนั้นจับต่อ ทั้งสองวิธีนี้ยังไงก็จะมีคน
1-1/e หรือประมาณ 63.21% ครับ โดยที่(แทบ)ไม่ต้องสนใจด้วยว่ามีคนมาแลกของขวัญกันกี่คนแต่วิธีแก้ก็ไม่ได้ยากเกินไป ใช้วิธีค่อยๆ ไล่จับฉลากไปทีละคนนั่นแหละ (จะได้เล่นมุกคั่นเวลา ดูรีแอคชันของคนได้ของขวัญด้วย) แล้วเพิ่มกฎเข้าไปสองข้อดังนี้
- ถ้าจับได้ชื่อตัวเอง ให้จับฉลากเพิ่มอีกใบเพื่อจะได้เอาของขวัญจากคนนั้น แต่อย่าลืมหย่อนฉลากชื่อตัวเองที่จับขึ้นมาเมื่อกี้ใส่กลับลงไหก่อนเอาไปให้จับฉลากต่อ
- ตอนเหลือคนยังไม่ได้จับฉลาก 2 คน ไม่ต้องให้จับฉลากแล้ว ให้คนที่กำลังจะจับฉลากไปเอาของขวัญจากคนสุดท้ายได้เลย ส่วนคนสุดท้ายก็ไปเอาของขวัญจากคนแรก
สวัสดีปีใหม่ 2016 ล่วงหน้าครับ
No comments:
Post a Comment