Dec 29, 2015

เจองานจับฉลากแลกของขวัญที่มีคนได้ของตัวเอง ไม่ต้องตกใจไปโอกาสมีสูงเกินครึ่ง

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

แต่ก่อนอื่นต้องเข้าใจกฎการแลกของขวัญ ซึ่งมีขั้นตอนประมาณนี้
  1. ทุกคนซื้อของขวัญมาร่วมสนุกในงานคนละอย่าง โดยเอาของขวัญใส่กล่องไว้ไม่ให้ใครรู้ว่าด้านในเป็นอะไร
  2. พอแต่ละคนไปถึงงาน คนจัดงานจะแปะป้ายชื่อเจ้าของของขวัญไว้กับกล่อง พร้อมหย่อนฉลากรายชื่อของคนนั้นลงไห
  3. เมื่อถึงเวลาแลกของขวัญ ให้ประธานในพิธีหรือใครซักคนที่ใหญ่ที่สุดในงาน เป็นคนเริ่มจับฉลากรายชื่อจากไหเป็นคนแรก
  4. ประธานจับได้ชื่อใครก็เอากล่องของขวัญของคนนั้นไป แล้วก็ให้คนที่โดนจับชื่อเมื่อกี้ เป็นคนเริ่มจับฉลากในไหวนต่อไปเรื่อยๆ
  5. ถ้าเกิดมีคนจับได้ชื่อประธาน จะถือว่าเป็นการแลกของขวัญที่ครบรอบวง ก็ให้คนนั้นเอาของขวัญของประธานไป แล้วผู้จัดงานเลือกใครซักคนจากคนที่ยังไม่ได้จับของขวัญ มาเป็นหัวจับของขวัญรอบต่อไป
  6. การแลกของขวัญจะสิ้นสุดลงเมื่อไม่มีฉลากรายชื่อเหลือในไห
จากกฎนี้เห็นได้ชัดว่า เมื่อถึงตอนใกล้จบการแลกของขวัญที่มีฉลากรายชื่อในไหเหลือแค่ 2 ใบ ใบนึงจะเป็นของคนแรกและอีกใบเป็นของคนที่ยังไม่ได้จับฉลาก ดังนั้นโอกาสที่คนจับก่อนจะจับฉลากได้ชื่อคนแรกและบังคับให้คนสุดท้ายจับชื่อตัวเอง โอกาสนี้จะสูงถึง 50% เลย

ยกตัวอย่างให้ชัดขึ้นไปอีก สมมตินายประธานเป็นคนจับฉลากคนแรก แล้วก็มีคนจับตามๆ กันมาอีกหลายคน จนตอนสุดท้ายเหลือคนที่ยังไม่ได้จับฉลาก 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% ครับ โดยที่(แทบ)ไม่ต้องสนใจด้วยว่ามีคนมาแลกของขวัญกันกี่คน

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

สวัสดีปีใหม่ 2016 ล่วงหน้าครับ

No comments:

Post a Comment