لغز سانتا السري

لعلّكم تذكرون في نشرة ٢٦ أكتوبر ٢٠٢٣ أنني كتبتُ عن برنامج ألعاب عُرض على متن السفينة بعنوان "صفقة أو لا صفقة". في تلك اللعبة، كان بإمكان كل لاعب شراء بطاقات لفرصة اللعب على المسرح. ومع ذلك، كانت لكل بطاقة فرصة للفوز بجوائز ترضية. كانت طريقة عمل جوائز الترضية هي أن كل بطاقة تحتوي على ٢٠ حقيبة سفر، وُضعت ٢٠ جائزة نقدية مختلفة عشوائيًا خلف الصناديق العشرين. كانت الحقائب تُفتح برفع اللوحات. يفوز اللاعب بعدد الجوائز على بطاقته التي تطابقت عشوائيًا مع نفس الجوائز المعروضة على الشاشة. إحدى المسائل التي لم تُحلّ في تلك النشرة هي احتمالية أي عدد مُحدّد من التطابقات.

يُشار إلى هذه المسألة عادةً باسم لغز بابا نويل السري. وقد استُوحي اسمها من نشاط حفلة عيد الميلاد، حيث تختار مجموعة من الأشخاص، عادةً في المكتب نفسه، اسمًا من بين أسماء جميع موظفي المكتب لتحديد من سيُهديه. تكمن مشكلة هذه اللعبة في وجود احتمالية سحب اسمك، وهو أمرٌ غير ممتع. في المتوسط، يحدث هذا للاعب واحد في كل مكتب، بغض النظر عن عدد الموظفين. أحد الأسئلة التي أحاول الإجابة عليها في هذه النشرة الإخبارية هو: ما هو الاحتمال الدقيق لعدم سحب أي شخص اسمه؟

عندما كتبتُ نشرة ٢٦ أكتوبر، لم أكن أعرف بالضبط كيفية حل المسألة الرياضية، فاستخدمتُ دالة بواسون للتقدير. مع ذلك، ظلت هذه المشكلة تُؤرقني منذ ذلك الحين. لطالما وجدتُ التقديرات مُرهقةً عقليًا.

أولاً، كتبتُ برنامجًا حاسوبيًا لفرز جميع ترتيبات الجوائز الممكنة وحساب عدد مرات التطابق مع كل تبديل. مع ذلك، باستخدام ١٣ حقيبة، استغرق البرنامج يومًا تقريبًا لفرز جميع التبديلات البالغ عددها ٦٬٢٢٧٬٠٢٠٬٨٠٠ تبديل. أما بالنسبة لعشرين حقيبة، فسيكون هناك ٢٬٤٣٢٬٩٠٢٬٠٠٨٬١٧٦٬٦٤٠٬٠٠٠ تبديل، وهو ما سيستغرق حوالي مليون سنة لفرزها.

ثانيًا، ذهبتُ إلى إكسل وحاولتُ حلَّها بشكل متكرر. كان هذا أسهل بكثير مما توقعتُ. كان عليَّ فعل ذلك بهذه الطريقة من البداية.وسوف يوضح بقية هذه النشرة الإخبارية المنطق وراء هذا النهج.

أفترض أن القارئ مُلِمٌّ بدالة combin(x,y) في برنامج إكسل، وهي عدد طرق اختيار y عنصر من x. المعادلة الدقيقة هي x!/(y!*(xy)!).

دعونا نبدأ ببعض الحالات الواضحة.

1. 1. مع سانتا واحد، من الواضح أنه يحصل على اسمه الخاص.
2. 2. مع وجود اثنين من سانتا، هناك فرصة 50/50 أن يحصل كل شخص على اسمه الخاص أو اسم الآخر.
3. ٣. مع وجود ثلاثة سانتا كلوز، هناك طريقة واحدة فقط ليحصل كل شخص على اسمه. لا توجد طريقة واحدة ليحصل شخصان على اسمهما، لأنه لو فعلوا ذلك، فسيسحب الشخص الأخير اسمه أيضًا لأنه الاسم الوحيد المتبقي. هناك ثلاث طرق ليحصل شخص واحد على اسمه، طريقة واحدة لكل من الثلاثة، ثم طريقة واحدة ليحصل الآخران على اسميهما. ٣ × ١ = ١. هناك ٣ طرق ممكنة لترتيب ٣ أسماء. عدد الطرق التي لا يحصل فيها أي شخص على اسمه هو ما تبقى: ٦ × ١ = ٣ = ٢.

وهذا هو المكان الذي وصلنا إليه حتى الآن:

المباريات	3 سانتا	2 سانتا	1 سانتا
3	1
2	0	1
1	3	0	1
0	2	1	0
المجموع	6	2	1

الآن دعنا ننتقل إلى 4 سانتا.

4 مباريات: هناك دائمًا طريقة واحدة يحصل بها كل شخص على اسمه الخاص.

ثلاث مطابقات: من المستحيل دائمًا أن يتطابق اسم كل شخص باستثناء شخص واحد. بعد مطابقة جميع الأسماء، باستثناء شخص واحد، يتبقى شخص واحد واسم واحد فقط، ويجب أن يكونا متطابقين.

مطابقتان: هناك 6 طرق لاختيار شخصين من أصل 4 مطابقين. مع الشخصين الآخرين، هناك طريقة واحدة لعدم التطابق، وهي سحب اسميهما.

مباراة واحدة: هناك أربع طرق لاختيار سانتا الذي يطابق نفسه. يتضح من حالة وجود ثلاثة سانتا، أن هناك طريقتين لعدم تطابق سانتا الثلاثة الآخرين، وهو أمرٌ لا مفر منه. لذا، فإن عدد التركيبات لمباراة واحدة هو ٤ × ٢ = ٨.

0 تطابقات: مرة أخرى، نطرح جميع الاحتمالات الأخرى من إجمالي التباديل. 4! – 1 – 6 – 8 = 24-15=9.

الآن نحن في:

المباريات	4 سانتا	3 سانتا	2 سانتا	1 سانتا
4	1
3	0	1
2	6	0	1
1	8	3	0	1
0	9	2	1	0
المجموع	24	6	2	1

الآن دعنا ننتقل إلى 5 سانتا.

5 مباريات: هناك دائمًا طريقة واحدة يحصل بها كل شخص على اسمه الخاص.

4 مباريات: مستحيل، للأسباب المذكورة في قضية سانتا الأربعة.

ثلاث مطابقات: هناك 10 طرق لاختيار ثلاثة أشخاص من أصل خمسة ليطابقوا أنفسهم. هناك طريقة واحدة ليحصل الشخصان الآخران على اسميهما. إذن، هناك 10 طرق لثلاث مطابقات.

مطابقتان: هناك 10 طرق لاختيار شخصين من أصل 5 للمطابقة. أما بالنسبة للثلاثة الآخرين، فهناك طريقتان لعدم التطابق، وهو ما نلاحظه في حالة سانتا الثلاثة. إذن، هناك 10 × 2 = 20 طريقة للمطابقة.

مباراة واحدة: هناك خمس طرق لاختيار سانتا الذي يطابق نفسه. يتضح من حالة وجود أربعة سانتا، أن هناك تسع طرق لعدم تطابق الأربعة الآخرين، وهو أمرٌ لا مفر منه. لذا، عدد التركيبات لمباراة واحدة هو ٥ × ٩ = ٤٥.

0 تطابقات: مرة أخرى، نطرح جميع الاحتمالات الأخرى من إجمالي التباديل. 5! – 1 – 0 – 10 – 20 – 45 = 44.

الآن نحن في:

المباريات	5 سانتا	4 سانتا	3 سانتا	2 سانتا	1 سانتا
5	1
4	0	1
3	10	0	1
2	20	6	0	1
1	45	8	3	0	1
0	44	9	2	1	0
المجموع	120	24	6	2	1

وبإتباع نفس المنطق، نحصل على الجدول التالي لما يصل إلى 10 سانتا.

حصيرة.	10 سانتا	9 سانتا	8 سانتا	7 سانتا	6 سانتا	5 سانتا	4 سانتا	3 سانتا	2 سانتا	1 سانتا
10	1
9	0	1
8	45	0	1
7	240	36	0	1
6	1890	168	28	0	1
5	11088	1134	112	21	0	1
4	55650	5544	630	70	15	0	1
3	222480	22260	2464	315	40	10	0	1
2	667485	66744	7420	924	135	20	6	0	1
1	1334960	133497	14832	1855	264	45	8	3	0	1
0	1334961	133496	14833	1854	265	44	9	2	1	0
المجموع	3628800	362880	40320	5040	720	120	24	6	2	1

لاحظ أن عدد التبديلات لمطابقة صفرية ومطابقة واحدة يكون دائمًا ضمن نطاق واحد. إجمالي عدد التبديلات لمطابقة صفرية يزيد بواحد عن عدد تبديلات عدد زوجي من سانتا، وينقص بواحد عن عدد فردي. إذا افترضنا أن هذا هو الحال دائمًا، وهو كذلك، فيمكننا تحديد عدد التبديلات لمطابقة صفرية لـ 11 سانتا أو أكثر بسرعة، كما يلي.

١١ بابا نويل: في حالة مطابقة واحدة، يوجد ١١ بابا نويل ليكونوا المطابقين، و١٣٣٤٩٦ طريقة لعدم تطابق العشرة الآخرين، من حالة ١٠ بابا نويل. وبالتالي، فإن عدد التبديلات لمطابقة واحدة هو ١١ × ١٣٣٤٩٦ = ١٤٦٨٤٥٧١. بما أن العدد ١١ فردي، فإن عدد التبديلات لـ ٠ مباريات أقل بواحد، أو ١٤٦٨٤٥٧١ - ١ = ١٤٦٨٤٥٧٠.

١٢ بابا نويل: في مباراة واحدة، يوجد ١٢ بابا نويل ليكونوا المطابقين، و١٤,٦٨٤,٥٧٠ طريقة لعدم تطابق الأحد عشر الآخرين، من حالة ١١ بابا نويل. وبالتالي، فإن عدد التبديلات لمباراة واحدة هو ١٢ × ١٤,٦٨٤,٥٧٠ = ١٧٦,٢١٤,٨٤٠. بما أن العدد ١٢ زوجي، فإن عدد التبديلات لـ ٠ مباريات يزيد بمقدار واحد، أو ١٧٦,٢١٤,٨٤٠ + ١ = ١٧٦,٢١٤,٨٤١.

بمواصلة نفس المنطق، إليك عدد التباديل لـ 0 تطابقات لـ 1 إلى 20 سانتا، بما في ذلك إجمالي التباديل والاحتمال.

سانتا	0 مباراة	مجموع التباديل	احتمال
20	895,014,631,192,902,000	2,432,902,008,176,640,000	0.367879
19	44,750,731,559,645,100	121,645,100,408,832,000	0.367879
18	2,355,301,661,033,950	6,402,373,705,728,000	0.367879
17	130,850,092,279,664	355,687,428,096,000	0.367879
16	7,697,064,251,745	20,922,789,888,000	0.367879
15	481,066,515,734	1,307,674,368,000	0.367879
14	32,071,101,049	87,178,291,200	0.367879
13	2,290,792,932	6,227,020,800	0.367879
12	176,214,841	479,001,600	0.367879
11	14,684,570	39,916,800	0.367879
10	1,334,961	3,628,800	0.367879
9	133,496	362,880	0.367879
8	14,833	40,320	0.367882
7	1,854	5,040	0.367857
6	265	720	0.368056
5	44	120	0.366667
4	9	24	0.375000
3	2	6	0.333333
2	1	2	0.500000
1	0	1	0.000000

لاحظ كيف يقترب احتمال عدم وجود أي تطابقات من 0.367879. هل يبدو هذا الرقم مألوفًا؟ من المفترض أن يكون كذلك! إنه 1/e. يمكنني كتابة كتاب قصير عن تقدير بواسون في هذه المرحلة، لكن هذه النشرة الإخبارية طويلة جدًا. لمزيد من المعلومات حول هذا الموضوع، أنصح بقراءة كتاب Sharp Sports Betting لستانفورد وونغ، الذي يشرح كيفية استخدام دالة بواسون لتحليل رهانات Super Bowl.

لنعد إلى لعبة "صفقة أم لا"، وهي تعادل لعبة "سانتا ٢٠". نريد معرفة عدد التركيبات لمطابقة من ٠ إلى ٢٠.

عدد التباديل لـ m من أصل ٢٠ بابا نويل هو combin(20,m)*z(m)، حيث z(m) = عدد التباديل لـ m من بابا نويل. يستخدم الجدول التالي هذه الطريقة لإيجاد عدد التباديل لـ ٠ إلى ٢٠ مباراة تتضمن ٢٠ بابا نويل.

المباريات	التباديل	احتمال
20	1	0.000000
19	-	0.000000
18	190	0.000000
17	2,280	0.000000
16	43,605	0.000000
15	682,176	0.000000
14	10,271,400	0.000000
13	143,722,080	0.000000
12	1,868,513,010	0.000000
11	22,421,988,160	0.000000
10	246,642,054,516	0.000000
9	2,466,420,377,200	0.000001
8	22,197,783,520,770	0.000009
7	177,582,268,088,640	0.000073
6	1,243,075,876,659,240	0.000511
5	7,458,455,259,939,930	0.003066
4	37,292,276,299,704,500	0.015328
3	149,169,105,198,817,000	0.061313
2	447,507,315,596,451,000	0.183940
1	895,014,631,192,902,000	0.367879
0	895,014,631,192,902,000	0.367879
المجموع	2,432,902,008,176,640,000	1.000000

إذا قارنت هذه الاحتمالات بتقديراتي لدالة بواسون في النشرة الإخبارية الصادرة في 26 أكتوبر/تشرين الأول 2023، فستجد أن الجميع يتفقون على النقاط العشرية الستة المقدمة، وهو ما يوضح فائدة دالة بواسون والرقم e.

في الأسبوع المقبل، أخطط لشرح هذا الموضوع وإظهار صيغة عامة لعدد التباديل لأي عدد من سانتا.

كتبه: Michael Shackleford