ปาร์ตี้แลกของขวัญที่มีคนได้ของตัวเองเกิดบ๊อยบ่อย
วันก่อนเห็นเพื่อนแลกของขวัญปีใหม่แล้วดันจับได้ของตัวเองก็ฮาดี มองเผินๆ เหมือนว่าเรื่องแบบนี้จะเกิดขึ้นได้ยาก แต่เท่าที่เคยเล่นแลกของขวัญวันคริสต์มาสที่โรงเรียนมากว่าหนึ่งทศวรรษ ก็จำได้ลางๆ ว่าเรื่องประมาณนี้เกิดขึ้นบ่อยจนเป็นที่จดจำเลยหละ เลยลองมานั่งไล่สมการความน่าจะเป็นดูว่าโอกาสที่ปาร์ตี้หนึ่งๆ จะมีคนจับของขวัญได้ของตัวเองเป็นเท่าไหร่กันแน่
แต่ก่อนอื่นต้องเข้าใจกฎการแลกของขวัญก่อน ซึ่งมีขั้นตอนประมาณนี้
- ทุกคนซื้อของขวัญมาร่วมสนุกในงานคนละอย่าง โดยเอาของขวัญใส่กล่องไว้ไม่ให้ใครรู้ว่าด้านในเป็นอะไร
- พอแต่ละคนไปถึงงาน คนจัดงานจะแปะป้ายชื่อเจ้าของของขวัญไว้กับกล่อง พร้อมหย่อนฉลากรายชื่อของคนนั้นลงไห
- เมื่อถึงเวลาแลกของขวัญ ให้ประธานในพิธีหรือใครซักคนที่ใหญ่ที่สุดในงาน เป็นคนเริ่มจับฉลากรายชื่อจากไหเป็นคนแรก
- ประธานจับได้ชื่อใครก็เอากล่องของขวัญของคนนั้นไป แล้วก็ให้คนที่โดนจับชื่อเมื่อกี้ เป็นคนเริ่มจับฉลากในไหวนต่อไปเรื่อยๆ
- ถ้าเกิดมีคนจับได้ชื่อประธาน จะถือว่าเป็นการแลกของขวัญที่ครบรอบวง ก็ให้คนนั้นเอาของขวัญของประธานไป แล้วผู้จัดงานเลือกใครซักคนจากคนที่ยังไม่ได้จับของขวัญ มาเป็นหัวจับของขวัญรอบต่อไป
- การแลกของขวัญจะสิ้นสุดลงเมื่อไม่มีฉลากรายชื่อเหลือในไห
จากกฎนี้เห็นได้ชัดว่า เมื่อถึงตอนใกล้จบการแลกของขวัญที่มีฉลากรายชื่อในไหเหลือเพียงสองใบ ใบนึงจะต้องเป็นของคนแรกที่เริ่มจับฉลาก ส่วนอีกใบก็ต้องเป็นของคนที่ยังไม่ได้จับฉลากเท่านั้น ดังนั้นโอกาสที่คนจับฉลากจะจับฉลากได้ชื่อของคนแรก (และบังคับให้คนสุดท้ายจับฉลากชื่อตัวเอง) จะมีโอกาสสูงถึง $50\%$ เลย
ยกตัวอย่างให้ชัดขึ้นไปอีก สมมตินายประธานเป็นคนจับฉลากคนแรก แล้วก็มีคนจับตามๆ กันมาอีกหลายคน จนตอนสุดท้ายเหลือคนที่ยังไม่ได้จับฉลากสองคนคือสมศักดิ์กับมานี ถ้าคนก่อนหน้าจับฉลากได้ชื่อสมศักดิ์ แปลว่าสมศักดิ์จะเป็นคนจับฉลากคนต่อไป แต่รายชื่อในไหตอนนี้จะเหลือแค่มานีกับประธานเท่านั้น ที่โอกาสครึ่งๆ ถ้าสมศักดิ์จับได้ชื่อประธาน ก็จะเหลือคนไม่ได้จับฉลากคือมานี และฉลากที่เหลือในไหก็เป็นชื่อมานี นั่นก็คือมานีจะถูกบังคับให้จับฉลากได้ของขวัญของตัวเองแน่นอน
โอกาสที่ในงานแลกของขวัญงานหนึ่งมีคนได้ของขวัญเป็นของตัวเองจึงสูงได้ถึง $50\%$ ซึ่งจริงๆ แล้วโอกาสอาจจะมากกว่านี้ได้อีกด้วยซ้ำ เพราะยังไม่ได้คิดโอกาสที่คนกลางๆ จะจับได้ของตัวเองทันทีหลังจากเกิดการจับฉลากครบรอบวงเลย (แต่เมื่อเกิดกรณีแบบนั้น ก็จะให้คนนั้นจับฉลากใหม่นั่นเอง)
คิดได้แค่นี้ก็พอใจแล้ว แต่ก็โดน @NungNing ถามต่อว่า ถ้าไม่จับฉลากกันต่อไปเรื่อยๆ แบบนี้หละ แต่เปลี่ยนเป็นให้ทุกคนหยิบฉลากจากไหพร้อมกันเลย แล้วค่อยเปิดดูทีเดียวว่าใครได้ของขวัญจากใคร ยังจะมีโอกาสสูงอยู่มั้ยที่จะมีคนจับฉลากได้ของขวัญของตัวเอง?
ตอนนั้นหมดพลังแล้ว ให้คิดต่ออย่างเดียวคงไม่ออกแน่ๆ เลยเขียนโปรแกรมง่ายๆ มาดูค่าเอาเลยนั่นแหละ
import random
from collections import Counter
xrange = lambda n: list(range(n))
shuffled = lambda ls: random.shuffle(ls) or ls
own_gift = lambda n: {i for i, j in enumerate(shuffled(xrange(n))) if i == j}
ให้ $n$ คือจำนวนคนทั้งหมดในปาร์ตี้แลกของขวัญหนึ่งๆ และ $k$ คือจำนวนคนที่ได้ของขวัญของตัวเอง จากการทดลองจำนวนอย่างน้อยหนึ่งล้านครั้งต่อแต่ละค่า $n$ ได้ผลลัพธ์การทดลองความน่าจะเป็นออกมาดังนี้
\[\begin{array}{c|cc} n \backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 1 & - & 1 \\ 2 & \frac12 & - & \frac12 \\ 3 & \frac13 & \frac12 & - & \frac16 \\ 4 & \frac38 & \frac13 & \frac14 & - & \frac1{24} \\ 5 & \frac{11}{30} & \frac38 & \frac16 & \frac1{12} & - & \frac1{120} \\ 6 & .36793 & .36664 & .18738 & .05571 & .02097 & - & .00137 \\ 7 & .36776 & .36834 & .18310 & .06260 & .01388 & .00412 & - & .00020 \end{array}\]และถึงแม้ว่าตอนที่ $n$ มีค่าน้อยๆ ค่าของ $k$ ในแต่ละแถวจะดูแตกต่างกันไปบ้าง แต่เมื่อพิจารณา $n$ ที่ใหญ่ขึ้น ค่า $k$ ในแต่ละแถวก็จะแตกต่างกันน้อยลงเรื่อยๆ จนเข้าสู่จุดสมดุลอะไรบางอย่าง ซึ่งจากการทดลองเพิ่มเติมเมื่อ $n$ มีขนาดใหญ่ (ไม่จำเป็นต้องใหญ่มากก็ได้เพราะลู่เข้าเร็วมาก) จะทำให้ได้ข้อคาดการณ์ว่า
\[\begin{array}{c|cc} n \backslash k & 0 & 1 & 2 & 3 & \cdots \\ \hline \text{large $n$} & \dfrac{e^{-1}}{0!} & \dfrac{e^{-1}}{1!} & \dfrac{e^{-1}}{2!} & \dfrac{e^{-1}}{3!} & \cdots \end{array}\]หรือก็คือมีเพียงประมาณ $1/e\approx36\%$ เท่านั้นที่ปาร์ตี้แลกของขวัญหนึ่งๆ จะไม่มีใครได้ของขวัญของตัวเองเลย! และเมื่อดูค่า $k$ อื่นๆ ประกอบไปด้วย จะได้ว่านี่ก็คือการแจกแจงปัวซองที่ $\lambda=1$ นั่นเอง
แต่ว่าความน่าจะเป็นของแต่ละค่า $n,k$ นั้นมาจากไหนหละ ทบทวนกันก่อนว่าสำหรับแต่ละแถวในตารางที่มีผู้เล่นเกมแลกของขวัญ $n$ คน วิธีการแลกของขวัญทังหมดที่แตกต่างกันโดยไม่สนใจว่ามีกี่คนที่จะได้ของตัวเอง (ซึ่งก็คือแซมเปิลสเปซ) มีค่าเท่ากับ $n!$ ดังนั้นสิ่งที่เราต้องการทำคือนับวิธีที่แตกต่างกันที่จะมีคนจับได้ของตัวเอง $k$ คนพอดี แล้วเอามาหารแซมเปิลสเปซนี้ซะ หากใช้สัญลักษณ์ $d(n,k)$ แทนจำนวนวิธีการที่การแลกของขวัญ $n$ ชิ้นจะมีคน $k$ คนได้ของขวัญเป็นของตัวเอง ดังนั้นความน่าจะเป็นตามตารางข้างต้นคือ $P(\text{cell }n,k) = d(n,k)/n!$ นั่นเอง
แล้วเราจะคำนวณค่า $d(n,k)$ ได้อย่างไร? เริ่มจากกรณี $d(n,0)$ ก่อน สังเกตว่าเราสามารถสร้างคำตอบนี้ขึ้นมาจากคำตอบก่อนหน้าได้ ซึ่งก็คือถ้าพิจารณา $d(n-1,0)$ ที่มีคนเพียง $n-1$ คนและไม่มีใครจับได้ของขวัญของตัวเองเลย การเพิ่มคนเข้าไปหนึ่งคนในปาร์ตี้ คือการเลือกคนจาก $n-1$ คนที่แลกของขวัญเรียบร้อย แล้วเอาของขวัญที่คนนั้นได้ (ที่ไม่ใช่ของตัวเองแน่ๆ) มาสลับกับของคนใหม่ที่เพิ่มเข้ามานั่นเอง จะเห็นว่าด้วยแนวทางนี้จะไม่มีใครได้ของขวัญของตัวเองเช่นเดิม และเนื่องจากคนที่เพิ่มเข้ามาใหม่สามารถเลือกหยิบคนได้ $n-1$ แบบ จึงมีจำนวนวิธีรวมเป็น $(n-1) \cdot d(n-1,0)$ แบบนั่นเอง
\[\begin{array}{c|cc} \text{person} & 1 & 2 & 3 & 4 & 5 & {\color{red}6} \\ \hline \text{gifts (before)} & 3 & 1 & 2 & 5 & 4 & {\color{red}6} \\ \Downarrow \\ \text{gifts (after)} & 3 & 1 & {\color{red}6} & 5 & 4 & 2 \\ \end{array}\]ตัวอย่างกรณี $d(5,0)$ แล้วเพิ่มคนที่ $6$ ที่จะสลับของขวัญกับใครก็ได้
แต่คำตอบนี้ยังเป็นแค่ครึ่งทางเท่านั้น เพราะเรายังไม่ได้นับอีกหนึ่งความเป็นไปได้ ซึ่งก็คือ $d(n-1,1)$ ที่มีคนแลกของขวัญกันเรียบร้อยแล้ว $n-1$ คน แต่มีหนึ่งคนพอดีที่จับได้ของขวัญของตัวเอง ในกรณีนี้ให้คนที่จับได้ของตัวเองนั้นสลับของขวัญกับคนที่เพิ่มเข้ามาใหม่ไปเลย หรือก็คือจะมีอีก $d(n-1,1)$ วิธีนั่นเอง
\[\begin{array}{c|cc} \text{person} & 1 & 2 & 3 & 4 & 5 & {\color{red}6} \\ \hline \text{gifts (before)} & 5 & 3 & 2 & {\color{red}4} & 1 & {\color{red}6} \\ \Downarrow \\ \text{gifts (after)} & 5 & 3 & 2 & {\color{red}6} & 1 & {\color{red}4} \\ \end{array}\]ตัวอย่างกรณี $d(5,1)$ แล้วเพิ่มคนที่ $6$ ที่ต้องสลับของขวัญกับคนที่ได้ของตัวเองมาก่อนเท่านั้น
ดังนั้น
\[d(n,0) = (n-1) d(n-1,0) + d(n-1,1)\]ซึ่งก็จะนำมาสู่คำถามถัดไปว่าแล้วเราจะคำนวณ $d(n,k)$ ที่ $k \ne 0$ อย่างไร? คำตอบอาจจะตรงไปตรงมากว่าที่คิด เพราะเราก็เพียงเริ่มจากเลือกก่อนว่าจะมีใครที่ได้ของขวัญของตัวเองบ้างผ่าน $\binom{n}{k}$ แล้วคนที่เหลือก็ห้ามได้ของขวัญของตัวเองผ่าน $d(n-k,0)$ เท่านั้นเอง ทำให้มีวิธีรวมทั้งหมดเป็น $\binom{n}{k} \cdot d(n-k,0)$
จะเห็นว่าสมการข้างต้นนั้นอยู่ในรูปฟังก์ชันเวียนเกิด และเมื่อหาค่าพื้นฐานเพื่อเป็นจุดเริ่มต้นบางค่าแล้ว จึงสรุปได้อีกรอบหนึ่งว่า
\[\begin{align} d(0,0) &= 1 \\ d(1,0) &= 0 \\ d(n,0) &= (n-1) \Big( d(n-1,0) + d(n-2,0) \Big) \\ d(n,k) &= \binom{n}{k} \cdot d(n-k,0) \end{align}\](ถึงตรงนี้ก็รู้สึกคุ้นหน้าคุ้นตาสมการมากๆ เพราะอันที่จริงก็เคยวิเคราะห์มันมาแล้วเมื่อ 8 ปีก่อนนั่นเอง)
แต่สมการที่ได้ก็ไม่ช่วยอะไรมากนักในการทำความเข้าใจภาพรวม อย่างไรก็ตามเรายังสามารถวิเคราะห์ $d(n,0)$ อีกทางได้ด้วยหลักการเพิ่มเข้าและตัดออก โดยให้ $s(n,a)$ แทนเซตที่คนทั้งหมด $n$ คนเล่นแลกของขวัญโดยที่คนตำแหน่งที่ $a$ ได้ของขวัญของตัวเอง (ส่วนคนอื่นๆ อาจจะได้หรือไม่ได้ของตัวเองก็ได้) ดังนั้น
\[d(n,0) = n! - \abs{ \bigcup_{1 \le a \le n} s(n,a) \;}\]ซึ่งจะเห็นว่า $s(n,a)$ สำหรับแต่ละ $a$ มีขนาดเป็น $(n-1)!$ แต่เพราะว่ามีวิธีเลือก $a$ ไม่ซ้ำกันทั้งหมด $\binom{n}{1}$ แบบ จึงทำให้เราได้ว่า
\[\sum_{a} \abs{s(n,a)} = \binom{n}{1} (n-1)!\]แต่อย่าลืมว่า $s$ เป็นเซต หากหาผลรวมของขนาดของแต่ละเซตตรงๆ เราจะได้ค่ามากกว่าการหาขนาดของเซตหลังจากการยูเนียนเซตเหล่านั้นแล้ว เพราะมีส่วนที่นับซ้ำเกินมานั่นเอง ในกรณีนี้คือเมื่อมีคนที่ $a$ และคนที่ $b$ สองคนที่ได้ของขวัญตัวเองพร้อมกัน ซึ่งก็คือ
\[\sum_{a,b} \abs{ s(n,a) \cap s(n,b) } = \binom{n}{2} (n-2)!\]อย่างไรก็ตามเมื่อหักล้างการนับเกินจากกรณีสองคนแล้ว จะกลายเป็นว่าเรานับน้อยกว่าที่ควรเพราะได้ลบกรณีได้ของตัวเองสามคนเกินไปเสียอีก และหากแก้กรณีสามคนก็จะกลายเป็นบวกกรณีสี่คนเกินไป เป็นแบบนี้สลับกันไปเรื่อยๆ ดังนั้น
\[\begin{align} \abs{ \bigcup_{1 \le a \le n} s(n,a) \; } &= \sum_a \abs{s(n,a)} - \sum_{a,b} \abs{ \bigcap_{x \in \lbrace a,b \rbrace} s(n,x) } + \cdots + (-1)^{n+1} \abs{ \bigcap_\text{all $x$} s(n,x) } \\ &= \binom{n}{1}(n-1)! - \binom{n}{2} (n-2)! + \cdots + (-1)^{n+1} \binom{n}{n} (n-n)! \\ &= \sum_{i=1}^n (-1)^{i+1} \binom{n}{i} (n-i)! \\ &= n! \sum_{i=1}^n \frac{(-1)^{i+1}}{i!} \\ d(n,0) &= n! - n! \sum_{i=1}^n \frac{(-1)^{i+1}}{i!} = n! \sum_{i=0}^n \frac{(-1)^i}{i!} \end{align}\]จะเห็นว่าการวิเคราะห์ทางนี้ทำให้เราได้พจน์หน้าตาสุดคุ้นขึ้นมา ซึ่งก็คือ $\sum_{i=0}^\infty\pm1/i!=1/e$ นั่นเอง และนี่เป็นเหตุผลว่าทำไมความน่าจะเป็นของการแลกของขวัญที่ไม่มีใครได้ของตัวเองเลยถึงลู่เข้าหา $1/e$
ส่วนกรณีอื่นๆ ที่มีคนเป็นจำนวน $k$ คนได้ของขวัญของตัวเอง สังเกตว่า
\[\begin{align} P(\text{cell $n,k$}) &= \frac{d(n,k)}{n!} \\ &= \frac1{n!} \cdot \binom{n}{k} \cdot d(n-k,0) \\ &= \frac1{n!} \cdot \frac{n!}{(n-k)!k!} \cdot (n-k)! \sum_{i=0}^{n-k} \frac{(-1)^i}{i!} \\ &= \frac{1}{k!} \cdot \sum_{i=0}^{n-k} \frac{(-1)^i}{i!} \\ &\approx \frac{e^{-1}}{k!} \end{align}\]ตรงตามที่คาดการณ์ไว้นั่นเอง
เห็นแล้วว่าการสุ่มจับฉลากทั้งหมดทีเดียวพร้อมกันมันไม่เวิร์ค กลับไปดูวิธีดั้งเดิมที่ค่อยๆ ให้จับฉลากทีละคน จับได้ชื่อใครก็ให้คนนั้นไปจับฉลากต่อ วิธีนี้เขียนเป็นโค้ดออกมาได้ว่า
import random
def exchanged(ls):
owned = [None for _ in ls]
current = 0
while ls:
if owned[current] is not None:
current = owned.index(None)
gone = random.randrange(len(ls))
owned[current] = ls[gone]
current = ls[gone]
del ls[gone]
return owned
เอาฟังก์ชัน exchanged ไปแทนที่ฟังก์ชัน shuffled ข้างบนแล้วทดลองใหม่ ก็ได้ผลลัพธ์ที่ไม่ต่างไปจากตารางแรกซักเท่าไหร่เลย นั่นก็เป็นเพราะว่าทั้งสองวิธีนี้สมมูลกันนั่นเอง! เพราะทั้งคู่ก็มีใจความเป็นขั้นตอนการสลับของแบบ Fisher-Yates เช่นเดียวกัน ที่เริ่มจากเอาฉลากทั้งหมดที่มีใส่ไหลงไป หลังจากนั้นแต่ละรอบจึงหยิบฉลากออกมาจากไหเรื่อยๆ โดยไม่มีการใส่กลับลงไป
เพียงแต่ว่าวิธีการที่ให้แต่ละคนออกมาจับฉลากคนต่อไปเรื่อยๆ มันดูตื่นเต้นเร้าใจมีความเป็นส่วนร่วมของคนทั้งปาร์ตี้มากกว่าที่จะให้คนแค่คนเดียวจับฉลากแล้วบอกว่าใครต้องได้ของขวัญจากใครนั่นเอง
ดังนั้นไม่ว่าจะให้จับฉลากพร้อมกันหมดในทีเดียว หรือจะค่อยๆ จับทีละคน พอจับได้ชื่อใครก็ให้คนนั้นจับต่อ ทั้งสองวิธีนี้ยังไงก็จะมีคนซวยโชคดีอย่างน้อยหนึ่งคน ที่จับได้ของขวัญของตัวเองด้วยโอกาสสูงเท่ากันที่ $1-\frac{1}{e}$ หรือประมาณ $63.21\%$ ครับ โดยที่(แทบ)ไม่ต้องสนใจด้วยว่ามีคนมาแลกของขวัญกันกี่คน
แต่วิธีแก้ก็ไม่ได้ยากเกินไป ใช้วิธีค่อยๆ ไล่จับฉลากไปทีละคนนั่นแหละ (จะได้เล่นมุกคั่นเวลา ดูรีแอคชันของคนได้ของขวัญด้วย) แล้วเพิ่มกฎเข้าไปสองข้อดังนี้
- ถ้าจับได้ชื่อตัวเอง ให้จับฉลากเพิ่มอีกใบเพื่อจะได้เอาของขวัญจากคนนั้น แต่อย่าลืมหย่อนฉลากชื่อตัวเองที่จับขึ้นมาเมื่อกี้ใส่กลับลงไหก่อนเอาไปให้จับฉลากต่อ
- ตอนเหลือคนยังไม่ได้จับฉลาก 2 คน ไม่ต้องให้จับฉลากแล้ว ให้คนที่กำลังจะจับฉลากไปเอาของขวัญจากคนสุดท้ายได้เลย ส่วนคนสุดท้ายก็ไปเอาของขวัญจากคนแรก
อย่างไรก็ตาม หากรู้สึกว่ากฎพวกนี้มันวุ่นวายจนทำให้งานกร่อยก็ไม่ต้องไปทำตามหรอก เพราะการมีคนจับได้ของขวัญของตัวเองก็ไม่ใช่เรื่องเลวร้ายแต่อย่างใด หนำซ้ำในระดับบุคคลแล้วมันยังเป็นประสบการณ์สุดประหลาดที่หาได้ยาก และเป็นเรื่องขำขันชั้นดีที่สามารถเก็บเอาไว้เล่นได้เรื่อยๆ ยันลูกหลานบวชเลยหละ
สวัสดีปีใหม่ 2016 ล่วงหน้าครับ
Revision notes:
- June 20, 2021:
แก้ไขส่วนสมการคณิตศาสตร์ที่วิเคราะห์ผิดตามคำแนะนำของ @jittat
author