गुप्त सांता पहेली

आपको याद होगा कि 26 अक्टूबर, 2023 के न्यूज़लेटर में मैंने जहाज पर खेले जाने वाले एक गेम शो के बारे में लिखा था, जिसका नाम था "डील ऑर नो डील"। उस गेम में, हर खिलाड़ी मंच पर खेलने के लिए कार्ड खरीद सकता था। हालाँकि, हर कार्ड के पास सांत्वना पुरस्कार जीतने का मौका भी था। सांत्वना पुरस्कारों के लिए हर कार्ड में 20 सूटकेस होते थे, जिनमें 20 बक्सों के पीछे 20 अलग-अलग नकद पुरस्कार बेतरतीब ढंग से रखे होते थे। सूटकेस के फ्लैप ऊपर उठाकर खोले जाते थे। खिलाड़ी अपने कार्ड पर दिए गए पुरस्कारों में से कितने पुरस्कारों का मिलान स्क्रीन पर दिखाए गए समान पुरस्कारों के बेतरतीब ढंग से फेरबदल करने पर करता था, उसके आधार पर जीतता था। उस न्यूज़लेटर की एक अनसुलझी समस्या थी किसी भी निश्चित संख्या में मिलान की प्रायिकता।

इस समस्या को आमतौर पर सीक्रेट सांता पहेली कहा जाता है। इसका नाम क्रिसमस पार्टी की एक गतिविधि से लिया गया है जिसमें लोगों का एक समूह, आमतौर पर एक ही कार्यालय में, सभी कर्मचारियों की टोपी में से एक नाम चुनकर यह तय करता है कि किसे उपहार देना है। इस खेल की एक समस्या यह है कि इसमें अपना नाम निकालने का मौका होता है, जो मज़ेदार नहीं है। औसतन, कर्मचारियों की संख्या चाहे कितनी भी हो, हर कार्यालय में एक खिलाड़ी के साथ ऐसा होगा। इस न्यूज़लेटर में मैं एक सवाल का जवाब देने की कोशिश कर रहा हूँ, वह यह कि क्या किसी के भी अपना नाम न निकालने की सटीक संभावना है।

जब मैंने 26 अक्टूबर का न्यूज़लेटर लिखा था, तब मुझे ठीक से गणित का तरीका नहीं पता था, इसलिए मैंने अनुमान लगाने के लिए पॉइसन फ़ंक्शन का इस्तेमाल किया। हालाँकि, तब से यह समस्या मुझे परेशान कर रही है। मुझे अनुमान लगाना हमेशा से बौद्धिक रूप से बहुत असंतोषजनक लगता रहा है।

सबसे पहले, मैंने पुरस्कारों के सभी संभावित क्रमों को चक्रित करने और प्रत्येक क्रमपरिवर्तन के साथ मिलानों की संख्या गिनने के लिए एक कंप्यूटर प्रोग्राम लिखा। हालाँकि, 13 सूटकेसों के साथ, उस प्रोग्राम को सभी 6,227,020,800 क्रमपरिवर्तनों को चक्रित करने में लगभग एक दिन लगा। 20 सूटकेसों में 2,432,902,008,176,640,000 क्रमपरिवर्तन होते, जिन्हें चक्रित करने में लगभग दस लाख वर्ष लगते।

दूसरा, मैं एक्सेल में गया और इसे पुनरावर्ती रूप से हल करने की कोशिश की। यह उम्मीद से कहीं ज़्यादा आसान था। मुझे इसे शुरू में इसी तरह करना चाहिए था।इस समाचार-पत्र के शेष भाग में उस दृष्टिकोण के पीछे के तर्क को समझाया जाएगा।

मुझे लगता है कि पाठक एक्सेल के combin(x,y) फ़ंक्शन से परिचित होंगे, जो x में से y आइटम चुनने के तरीकों की संख्या है। सटीक समीकरण x!/(y!*(xy)!) है।

आइये कुछ स्पष्ट मामलों से शुरुआत करें।

1. 1. एक सांता के साथ, यह स्पष्ट है कि उसे अपना नाम मिलता है।
2. 2. दो सांता होने पर, 50/50 संभावना होती है कि दोनों लोगों को अपना नाम या एक दूसरे का नाम मिलेगा।
3. 3. तीन सांता क्लॉज़ के साथ, हर किसी के पास अपना नाम रखने का एक ही तरीका है। दो लोगों के पास अपना नाम रखने के 0 तरीके हैं, क्योंकि अगर वे ऐसा करते हैं, तो आखिरी व्यक्ति भी अपना नाम निकालेगा क्योंकि वही एकमात्र बचा है। एक व्यक्ति के पास अपना नाम रखने के 3 तरीके हैं, तीनों लोगों में से प्रत्येक के लिए एक और फिर बाकी दो लोगों के पास एक-दूसरे का नाम रखने का एक तरीका। 3*1 = 1. 3 नामों को क्रम में रखने के कुल 3!=6 संभावित तरीके हैं। 0 लोगों के पास अपना नाम रखने के जितने तरीके बचे हैं, उनकी संख्या उतनी ही है: 6-1-3 = 2।

अब तक हम यहां पर हैं:

माचिस	3 सांता	2 सांता	1 सांता
3	1
2	0	1
1	3	0	1
0	2	1	0
कुल	6	2	1

अब, आइए 4 सांताओं पर चलते हैं।

4 मिलान: हर किसी को अपना नाम पाने का हमेशा एक ही तरीका होता है।

3 मिलान: एक व्यक्ति को छोड़कर बाकी सभी का नाम निकालना हमेशा असंभव होता है। एक व्यक्ति को छोड़कर बाकी सभी का नाम मिल जाने के बाद, केवल एक व्यक्ति और एक नाम ही बचेगा, और उनका नाम एक जैसा होना ज़रूरी है।

2 मिलान: 4 में से 2 लोगों को मिलान के लिए चुनने के लिए combin(4,2)=6 तरीके हैं। बाकी 2 के साथ, एक तरीका है जिससे वे मेल नहीं खाते, वह है एक-दूसरे का नाम निकालना।

1 मिलान: अपने से मेल खाने वाले सांता को चुनने के 4 तरीके हैं। 3 सांता वाले मामले से हम देख सकते हैं कि बाकी 3 सांता के मेल न खाने के 2 तरीके हैं, जो होना ही चाहिए। इसलिए, 1 मिलान के लिए संयोजनों की संख्या 4*2=8 है।

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 मिलान: 4 सांता मामले में बताए गए कारणों से असंभव।

3 मिलान: 5 में से 3 लोगों को खुद से मिलाने के लिए चुनने के कॉम्बिन(5,3)=10 तरीके हैं। एक तरीका है जिससे बाकी दो लोग एक-दूसरे के नाम जान सकते हैं। इस तरह, 3 मिलान के 10 तरीके हैं।

2 मिलान: 5 में से 2 लोगों को मिलान के लिए चुनने के लिए combin(5,2)=10 तरीके हैं। बाकी 3 के साथ, 2 तरीके ऐसे हैं जिनसे वे मेल नहीं खाते, जैसा कि हम 3 सांता वाले मामले में देखते हैं। तो, 2 मिलान के लिए 10*2=20 तरीके हैं।

1 मिलान: अपने से मेल खाने वाले सांता को चुनने के 5 तरीके हैं। 4 सांता वाले मामले से हम देख सकते हैं कि बाकी 4 सांता के मेल न खाने के 9 तरीके हैं, जो होना ही चाहिए। इसलिए, 1 मिलान के लिए संयोजनों की संख्या 5*9=45 है।

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

ध्यान दें कि 0 और 1 मिलान के क्रमचयों की संख्या हमेशा एक-दूसरे के भीतर होती है। 0 मिलानों का योग सम संख्या वाले सांता के लिए 1 मिलान से एक अधिक और विषम संख्या वाले सांता के लिए एक कम होता है। अगर हम मान लें कि ऐसा हमेशा होता है, जो कि होता भी है, तो हम 11 या उससे अधिक सांता के लिए 0 मिलानों की संख्या निम्न प्रकार से शीघ्रता से निर्धारित कर सकते हैं।

11 सांता: एक मिलान के लिए, 11 सांता होते हैं जिन्हें मिलान करना होता है और बाकी 10 के 133,496 तरीकों से मेल न खाने के 10 सांता मामले में यही स्थिति है। इस प्रकार, 1 मिलान के लिए क्रमचयों की संख्या 11*133,496 = 14,684,571 है। चूँकि 11 विषम है, इसलिए 0 मिलान के लिए क्रमचयों की संख्या एक कम है, अर्थात 14,684,571 - 1 = 14,684,570।

12 सांता: एक मिलान के लिए, 12 सांता हैं जिन्हें मिलान करना है और 11 सांता के मामले में, अन्य 11 के मिलान न करने के 14,684,570 तरीके हैं। इस प्रकार, 1 मिलान के लिए क्रमचयों की संख्या 12*14,684,570 = 176,214,840 है। चूँकि 12 सम है, इसलिए 0 मिलान के लिए क्रमचयों की संख्या एक अधिक है, अर्थात 176,214,840 + 1 = 176,214,841

इसी तर्क को जारी रखते हुए, यहां 1 से 20 सांता के लिए 0 मिलानों के क्रमपरिवर्तनों की संख्या दी गई है, जिसमें कुल क्रमपरिवर्तन और संभावना भी शामिल है।

सांता	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 मिलान की प्रायिकता 0.367879 के करीब कैसे पहुँचती है। क्या यह संख्या जानी-पहचानी लगती है? होनी भी चाहिए! यह 1/e है। मैं इस समय पॉइसन अनुमान पर एक छोटी किताब लिख सकता हूँ, लेकिन यह न्यूज़लेटर पहले ही बहुत लंबा हो चुका है। इस बारे में अधिक जानकारी के लिए, मैं स्टैनफोर्ड वोंग द्वारा लिखित शार्प स्पोर्ट्स बेटिंग की सलाह देता हूँ, जिसमें बताया गया है कि सुपर बाउल प्रस्ताव दांवों का विश्लेषण करने के लिए पॉइसन फ़ंक्शन का उपयोग कैसे किया जाता है।

चलिए डील या नो डील गेम पर वापस आते हैं, जो 20 सांता केस के बराबर है। हम 0 से 20 मैचों के लिए संयोजनों की संख्या जानना चाहते हैं।

20 सांताओं में से m मिलानों के लिए संयोजनों की संख्या combin(20,m)*z(m) है, जहाँ z(m) = m सांताओं के लिए शून्य मिलानों के संयोजनों की संख्या। निम्न तालिका 20 सांताओं के साथ 0 से 20 मिलानों के लिए क्रमचयों की संख्या ज्ञात करने के लिए इसी विधि का उपयोग करती है।

माचिस	क्रमपरिवर्तन	संभावना
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