The Ordered Zeckendorf Game

यहाँ बोर्टनोव्स्कीकी (Bortnovskyi) और अन्य के शोध पत्र "द ऑर्डर्ड ज़ेकेन्डॉर्फ गेम" (The Ordered Zeckendorf Game) का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या की परिभाषा और प्रेरणा

संदर्भ:
यह शोध पत्र ज़ेकेन्डॉर्फ प्रमेय (Zeckendorf's Theorem) पर आधारित एक कॉम्बिनेटोरियल द्वि-खिलाड़ी खेल की जांच करता है, जो यह बताता है कि प्रत्येक धनात्मक पूर्णांक $n$ को गैर-समीपवर्ती फाइबोनैची संख्याओं ($F_1=1, F_2=2, F_{i+1}=F_i+F_{i-1}$) के योग के रूप में एक अद्वितीय रूप में दर्शाया जा सकता है।

शास्त्रीय खेल (The Classical Game):
पूर्व में अध्ययन किए गए "ज़ेकेन्डॉर्फ गेम" में, खिलाड़ी $n$ एकों ($F_1$) के एक अव्यवस्थित मल्टीसेट (unordered multiset) से शुरुआत करते हैं। वे तब तक मर्ज (merge) और स्प्लिट (split) ऑपरेशन्स (जैसे, $F_i + F_{i+1} \to F_{i+2}$ या $F_i + F_i \to F_{i+1} + F_{i-2}$) करते हैं जब तक कि अद्वितीय ज़ेकेन्डॉर्फ अपघटन (decomposition) प्राप्त नहीं हो जाता।

• सीमा: शास्त्रीय अव्यवस्थित संस्करण में, $n > 2$ के लिए खिलाड़ी 2 के पास एक प्रभावी जीतने वाली रणनीति होती है, जिससे खेल रणनीतिक रूप से उथला (shallow) हो जाता है।

क्रमित संस्करण (The Ordered Variant):
लेखक "ऑर्डर्ड ज़ेकेन्डॉर्फ गेम" प्रस्तुत करते हैं, जहाँ अवस्था (state) फाइबोनैची संख्याओं का एक क्रमित टुपल (ordered tuple) है।

• प्रतिबंध: चालें केवल समीपवर्ती (adjacent) तत्वों तक ही सीमित हैं।
• नया मूव: एक स्विचिंग (Switching) मूव पेश किया गया है, जो खिलाड़ियों को $(F_i, F_j) \to (F_j, F_i)$ के रूप में समीपवर्ती तत्वों को बदलने (swap करने) की अनुमति देता है यदि $i > j$ हो (अर्थात, आरोही क्रम को बहाल करने के लिए)।
• लक्ष्य: खेल तब समाप्त होता है जब टुपल सख्ती से बढ़ता हुआ (strictly increasing) हो और कोई और मर्ज या स्प्लिट संभव न हो (बढ़ते क्रम में ज़ेकेन्डॉर्फ अपघटन)।

अनुसंधान प्रश्न: क्रम और निकटता (adjacency) के प्रतिबंध लगाने से खेल की समाप्ति, लंबाई और रणनीतिक संतुलन कैसे बदल जाता है?

---

2. कार्यप्रणाली (Methodology)

लेखक सैद्धांतिक प्रमाणों (मोनोवेरिएंट्स और इंडक्शन का उपयोग करके) और कम्प्यूटेशनल सिमुलेशन (छोटे $n$ के लिए व्यापक खोज और संभावabilistic विश्लेषण के लिए मोंटे कार्लो सिमुलेशन) को मिलाकर एक हाइब्रिड दृष्टिकोण अपनाते हैं।

अ. सैद्धांतिक ढांचा (Theoretical Framework)

• मोनोवेरिएंट्स (Monovariants): खेल की समाप्ति और लंबाई को सीमित करने के लिए, लेखक एक अवस्था $S = (F_{i_1}, \dots, F_{i_k})$ के लिए एक सख्ती से घटता हुआ फलन $f(S)$ परिभाषित करते हैं:
  $$f(S) = \sum_{j=1}^k (k + 1 - j)F_{i_j}$$
  यह फलन पदों को उनके स्थान और मान के आधार पर भारित (weight) करता है, यह सुनिश्चित करता है कि प्रत्येक वैध चाल (मर्ज, स्प्लिट, या स्विच) कुल मान को सख्ती से कम करती है।
• स्टेट-ट्रांजिशन ग्राफ (State-Transition Graphs): अधिकतम खेल लंबाई के विश्लेषण के लिए, लेखक "पिवट स्टेट्स" (Pivot States) को उच्च-इंडेक्स वाले पदों की पुनरावृत्ति के आधार पर परिभाषित करते हैं ($i \ge 3$ के लिए $F_i$)। वे "कोई पुनरावृत्ति नहीं" (No Repetitions) वाली अवस्थाओं और विशिष्ट पुनरावृत्तियों (जैसे, $F_3, F_3$) वाली अवस्थाओं के बीच संक्रमण को ट्रैक करने के लिए एक निर्देशित ग्राफ (directed graph) का निर्माण करते हैं।
• रणनीति विश्लेषण: वे एक विशिष्ट "लॉन्ग गेम स्ट्रैटेजी" (LGS) प्रस्तावित करते हैं जो स्विचिंग, फिर एकों को संयोजित करने, फिर दाईं ओर से विभाजित करने, और बाईं ओर से मर्ज करने को प्राथमिकता देती है।

ब. कम्प्यूटेशनल विश्लेषण

• व्यापक खोज (Exhaustive Search): $n \le 25$ के लिए जीतने वाली रणनीतियों को निर्धारित करने के लिए उपयोग किया गया।
• रैंडम सिमुलेशन: बड़े $n$ (जैसे, $n=150$) के लिए चालों के वितरण और जीत की संभावनाओं का विश्लेषण करने के लिए 10,000+ रैंडम गेम सिम्युलेट किए गए।
• कोडबेस: पायथन (Python) और C++ में कार्यान्वित (सार्वजनिक रूप से उपलब्ध)।

---

3. मुख्य योगदान और परिणाम

अ. समाप्ति और अंतिम अवस्था

• प्रमेय 1.3 (Theorem 1.3): खेल हमेशा सीमित चालों में समाप्त होता है।
• अंतिम अवस्था: खेल अनिवार्य रूप से $n$ के अद्वितीय ज़ेकेन्डॉर्फ अपघटन में समाप्त होता है, जिसे सख्ती से बढ़ते क्रम में व्यक्त किया जाता है।
• प्रमाण: यह सख्ती से घटते हुए मोनोवेरिएंट $f(S)$ पर निर्भर करता है, जो चक्रों (cycles) को रोकता है और उस अद्वितीय अवस्था की ओर अभिसरण (convergence) को मजबूर करता है जहाँ कोई चाल संभव नहीं है।

ब. खेल की लंबाई के बंधन (Game Length Bounds)

शोध पत्र चालों की संख्या $M(n)$ पर सटीक सीमाएं स्थापित करता है:

1. सबसे छोटा खेल (निम्नतम सीमा/Lower Bound):

   • परिणाम: न्यूनतम लंबाई ठीक $n - Z(n)$ है, जहाँ $Z(n)$, $n$ के ज़ेकेन्डॉर्फ अपघटन में पदों की संख्या है।
   • तंत्र: इसे एक ग्रीडी (greedy) रणनीति के माध्यम से प्राप्त किया जाता है जो अनावश्यक स्प्लिट या स्विच के बिना तुरंत समीपवर्ती जोड़ों को मर्ज करती है।

2. सबसे लंबा खेल (ऊपरी और निम्नतम सीमा):

   • ऊपरी सीमा (Upper Bound): $M(n) \le \frac{n(n-1)}{2}$।
   • परिमित ऊपरी सीमा (Refined Upper Bound): $M(n) \le \frac{n^2}{2} - \frac{1}{32}n \log_\phi n + o(n \log_\phi n)$।
   • निम्नतम सीमा (Lower Bound): लेखक सिद्ध करते हैं कि "लॉन्ग गेम स्ट्रैटेजी" (LGS) कम से कम $\frac{n^2}{2} - n \log_\phi n + o(n \log_\phi n)$ की लंबाई प्रदान करती है।
   • एसिम्प्टोटिक लक्षण (Asymptotic Characterization): $M(n) = \frac{n^2}{2} - \Theta(n \log_\phi n)$।
   • महत्व: खेल की लंबाई द्विघातीय (quadratically) रूप से बढ़ती है, लेकिन लॉगरिदमिक सुधार पद (logarithmic correction term) महत्वपूर्ण है।

स. जीतने वाली रणनीतियाँ और रणनीतिक संतुलन

• गतिशीलता में बदलाव: शास्त्रीय खेल के विपरीत (जहाँ $n > 2$ के लिए खिलाड़ी 2 जीतता है), क्रमित संस्करण अत्यधिक संतुलित है।
• अनुभवजन्य निष्कर्ष (Empirical Findings):
  • $n \le 25$ के लिए, खिलाड़ी 1 सभी मामलों में जीतता है सिवाय $n=18$ के (जहाँ खिलाड़ी 2 जीतता है)।
  • यह सुझाव देता है कि क्रम और स्विचिंग को पेश करने से रणनीतिक गहराई बहाल होती है और छोटे $n$ के लिए खिलाड़ी 1 को महत्वपूर्ण लाभ मिलता है।
• खुली समस्या (Open Problem): किसी भी $n$ के लिए सामान्य जीतने वाली रणनीति अभी भी अप्रामाणित है क्योंकि गेम ट्री का संयोजन विस्फोट (combinatorial explosion) बहुत अधिक है।

द. संभाव्यता व्यवहार (Probabilistic Behavior)

• कन्जक्चर 3.2 (Conjecture 3.2): समान रैंडम प्ले के तहत, चालों की लंबाई का वितरण $n \to \infty$ होने पर लॉग-नॉर्मल वितरण (log-normal distribution) की ओर अभिसरित होता है।
• साक्ष्य: $n=150$ के लिए सिमुलेशन भारी-पूंछ (heavy-tailed) और दाईं ओर झुके हुए वितरण दिखाते हैं जो लॉग-नॉर्मल व्यवहार के अनुरूप है।
• जीत की संभावना: रैंडम प्ले के तहत, दोनों खिलाड़ियों के लिए जीत की संभावना 0.5 के करीब पहुंचती हुई प्रतीत होती है, जो रैंडम डायनेमिक्स में समरूपता (symmetry) को दर्शाता है।

---

4. महत्व और भविष्य की दिशाएँ

महत्व:

• सैद्धांतिक गहराई: यह शोध पत्र प्रदर्शित करता है कि एक ज्ञात संख्या-सिद्धांत खेल में सरल प्रतिबंध (क्रम और निकटता) जोड़ने से इसकी जटिलता मौलिक रूप से बदल जाती है, जिससे यह एक हल किए गए, सरल खेल से एक समृद्ध रणनीतिक और संभाव्य गुणों वाले खेल में बदल जाता है।
• एल्गोरिदम संबंधी चुनौती: यह खेल एल्गोरिथमिक गेम थ्योरी के लिए एक परीक्षण स्थल (testbed) के रूप में कार्य करता है, जिसके लिए गहरे लुकअहेड (lookahead) और ह्यूरिस्टिक प्रूनिंग (जैसे, अल्फा-बीटा) की आवश्यकता होती है।
• नए इनवेरिएंट्स: विशिष्ट मोनोवेरिएंट $f(S)$ का निर्माण फाइबोनैची पुनरावृत्तियों (recurrences) वाले खेलों के विश्लेषण के लिए एक नवीन उपकरण प्रदान करता है।

खुले प्रश्न और भविष्य का कार्य:

1. इष्टतम रणनीति प्रमाण: सभी $n$ के लिए खिलाड़ी 1 के लिए एक जीतने वाली रणनीति का कठोरता से प्रमाण देना (या $n=18$ जैसे अपवादों के पैटर्न की पहचान करना)।
2. LGS इष्टतमता: यह सिद्ध करना कि प्रस्तावित "लॉन्ग गेम स्ट्रैटेजी" वास्तव में खेल की लंबाई को अधिकतम करने के लिए इष्टतम है।
3. सामान्यीकरण: क्रमित खेल को $k$-bonacci अनुक्रमों या गैर-स्थिर पुनरावृत्ति संबंधों तक विस्तारित करना।
4. संभाव्यता कठोरता: चाल गणना के लॉग-नॉर्मल वितरण को अनुभवजन्य (empirically) के बजाय गणितीय रूप से व्युत्पन्न करना।
5. बहु-खिलाड़ी संस्करण: दो से अधिक खिलाड़ियों या सहकारी गठबंधनों (cooperative alliances) के साथ क्रम प्रतिबंधों के प्रभाव का पता लगाना।

संक्षेप में, ऑर्डर्ड ज़ेकेन्डॉर्फ गेम एक स्थिर संख्या-सिद्धांत अपघटन को एक गतिशील, रणनीतिक और संभाव्य रूप से समृद्ध कॉम्बिनेटोरियल खेल में बदल देता है, जो एडिटिव नंबर थ्योरी और एल्गोरिथमिक गेम थ्योरी में अनुसंधान के नए मार्ग खोलता है।