🔢 mathematics

Structural Conjectures for 4 x n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry

यह शोध पत्र 4 x n चोमप (Chomp) का एक व्यापक कम्प्यूटेशनल अध्ययन प्रस्तुत करता है, जिसमें अद्वितीय विस्तार (unique extensions), अनंत अनुपात (asymptotic ratios), आवर्त-112 मॉड्यूलर पैटर्न (period-112 modular patterns), और रैखिक शंकु ज्यामिति (linear cone geometry) के संबंध में चार संरचनात्मक अनुमान प्रस्तावित करने हेतु 4.3 मिलियन से अधिक P-स्थितियों को सूचीबद्ध किया गया है, जो खेल में पहले की तुलना में अधिक समृद्ध नियतात्मक संरचना (deterministic structure) को प्रकट करते हैं।

मूल लेखक: Arnav Garg

प्रकाशित 2026-04-30

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Arnav Garg

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि एक खेल है जिसका नाम चोमप (Chomp) है, जो चॉकलेट बार के एक आयताकार ग्रिड पर खेला जाता है। बार चॉकलेट के वर्गों (squares) से बना है। दो खिलाड़ी बारी-बारी से अपनी चाल चलते हैं। अपनी बारी पर, आप एक वर्ग चुनते हैं और उसे "खा" लेते हैं, साथ ही उसके ऊपर और दाईं ओर के सभी वर्गों को भी। पेच यह है कि सबसे ऊपर-बाएँ (top-left) वाला वर्ग ज़हरीला है। यदि आपको वह आखिरी वर्ग खाने के लिए मजबूर किया जाता है, तो आप हार जाते हैं।

गणितज्ञों ने बहुत छोटे या बहुत विशिष्ट चॉकलेट बार के लिए जीतने की रणनीति खोज ली है, लेकिन 4 वर्ग चौड़े और n वर्ग लंबे बार के लिए, यह पैटर्न अब तक एक रहस्य था।

यह शोध पत्र एक विशाल, हाई-स्पीड जासूसी कहानी की तरह है जहाँ लेखक ने एक अत्यंत तेज़ कंप्यूटर का उपयोग करके 500 वर्ग लंबे चॉकलेट बार के लिए हर एक "हारने वाली स्थिति" (losing position - वह स्थान जहाँ यदि खिलाड़ी की बारी है, तो वह तब हार जाएगा यदि प्रतिद्वंद्वी सही ढंग से खेले) का मानचित्र तैयार किया है।

यहाँ लेखक द्वारा की गई खोज का सरल विवरण दिया गया है:

1. "एक-और-एक-ही" नियम (अद्वितीय विस्तार - Unique Extension)

चॉकलेट बार को चार पंक्तियों (rows) के रूप में सोचें। ऊपर की तीन पंक्तियों की निश्चित लंबाई है (मान लीजिए A, B, और C)।

खोज: लेखक ने पाया कि ऊपर की तीन पंक्तियों की लंबाई के किसी भी विशिष्ट संयोजन के लिए, चौथी पंक्ति की अधिकतम एक विशिष्ट लंबाई ही ऐसी होती है जो "हारने वाली स्थिति" बनाती है।
उपमा: कल्पना कीजिए कि आप विशिष्ट आकार के तीन ब्लॉकों से एक टावर बना रहे हैं। यदि आप चाहते हैं कि टावर "अस्थिर" (हारने वाली स्थिति) हो, तो केवल चौथी ब्लॉक का एक विशिष्ट आकार ही ऐसा होगा जो उसे अस्थिर बनाएगा। आप चौथी ब्लॉक का कोई भी आकार नहीं चुन सकते; गणित आपको एक एकल, अद्वितीय उत्तर की ओर ले जाता है। यह सुझाव देता है कि यह खेल पहले की तुलना में बहुत अधिक अनुमानित (predictable) और "निश्चित" (deterministic) है।

2. चॉकलेट का "स्वर्ण अनुपात" (अनंत अनुपात - Asymptotic Ratios)

जैसे-जैसे चॉकलेट बार लंबा होता जाता है (कल्पना कीजिए कि इसे अनंत तक खींचा जा रहा है), इसकी पंक्तियाँ एक विशिष्ट आकार में स्थिर होने लगती हैं।

खोज: पंक्तियों की लंबाई बेतरतीब ढंग से बदलना बंद कर देती है और एक निश्चित पैटर्न का पालन करने लगती है। यदि पहली पंक्ति की लंबाई 100 है, तो दूसरी पंक्ति हमेशा लगभग 76 इकाई लंबी होगी, तीसरी लगभग 50, और चौथी लगभग 22।
उपमा: यह एक बढ़ते हुए पेड़ की तरह है। पेड़ चाहे कितना भी ऊँचा हो जाए, उसकी शाखाएँ हमेशा समान सापेक्ष अनुपातों में बढ़ती हैं। लेखक ने इन "विकास दरों" (growth rates) की गणना की, लेकिन वे अभी तक इसे सटीक रूप से वर्णित करने के लिए कोई सरल गणितीय सूत्र (जैसे कि भिन्न/fraction) नहीं खोज पाए हैं। वे कुछ प्रसिद्ध संख्याओं के करीब हैं, लेकिन सटीक रहस्य अभी भी छिपा हुआ है।

3. "छिपी हुई लय" (पीरियड-112 - Period-112)

लेखक ने डेटा में एक दोहराव वाले पैटर्न की तलाश की, जैसे किसी गाने की बीट।

खोज: डेटा 112 चरणों के बाद एक विशिष्ट पैटर्न को दोहराता है।
उपमा: कल्पना कीजिए कि एक घड़ी है जो हर सेकंड टिक-टिक नहीं करती, बल्कि इसमें एक जटिल लय है जो 112 टिक के बाद फिर से सेट हो जाती है। लेखक ने पाया कि यह लय संभवतः दो छोटी लयों का मिश्रण है: एक जो 7 चरणों के अंतराल पर दोहराती है (3-रो वाले गेम से विरासत में मिली है) और दूसरी एक रहस्यमय लय जो 8 चरणों के अंतराल पर दोहराती है। संख्या 112 केवल वह बिंदु है जहाँ ये दोनों लयएँ पूरी तरह से एक साथ (sync up) आती हैं।

4. "कीप" का आकार (रैखिक शंकु ज्यामिति - Linear Cone Geometry)

यदि आप सभी संभावित "हारने वाली स्थितियों" को एक ग्राफ पर दर्शाते हैं, तो वे यादृच्छिक बिंदुओं के बादल की तरह नहीं दिखते।

खोज: वे एक साफ, कीप (funnel) जैसे आकार (शंकु/cone) में बनते हैं। जैसे-जैसे पंक्तियाँ लंबी होती हैं, वैध हारने वाली स्थितियों की "चौड़ाई" एक सीधी, अनुमानित रेखा में बढ़ती है।
उपमा: कल्पना कीजिए कि आप एक कीप में रेत डाल रहे हैं। रेत बेतरतीब ढंग से नहीं जमा होती है; यह एक चिकने, चौड़े होते शंकु का रूप लेती है। लेखक ने पाया कि इस खेल में "वैध" हारने वाली स्थितियाँ इसी तरह के चिकने, चौड़े होते आकार में फिट बैठती हैं, जिसमें ऊपर बताए गए 112-चरण के रिदम के कारण एक मामूली उतार-चढ़ाव (wobble) होता है।

यह क्यों मायने रखता है?

इस शोध पत्र से पहले, 4-पंक्तियों वाला चोमप एक "ब्लैक बॉक्स" की तरह था। हम जानते थे कि पहला खिलाड़ी आमतौर पर जीतता है, लेकिन हमें यह नहीं पता था कि क्यों या हारने वाली स्थितियाँ कैसे व्यवस्थित थीं।

लेखक ने 4.3 मिलियन विशिष्ट हारने वाली स्थितियाँ खोजीं।
उन्होंने सिद्ध किया कि यह खेल अराजकता के बजाय सख्त नियमों ("अद्वितीय विस्तार") द्वारा संचालित होता है।
उन्होंने एक छिपी हुई लय (112) खोजी जो खेल की संरचना को नियंत्रित करती है।

यह शोध पत्र क्या नहीं कहता:

यह दावा नहीं करता कि इससे शतरंज या गो (Go) जैसे अन्य खेल हल करने में मदद मिलेगी।
यह दावा नहीं करता कि इसके चिकित्सा या वास्तविक दुनिया के अनुप्रयोग हैं।
यह सिद्ध नहीं करता कि ये नियम अनंत बोर्डों के लिए 100% सत्य हैं; यह केवल उस 500-चरण की सीमा के लिए सत्य है जिसका उन्होंने परीक्षण किया है। लेखक इन्हें प्रमाणित कानूनों के बजाय "अनुमान" (conjectures - साक्ष्यों पर आधारित मजबूत अनुमान) कहते हैं।

संक्षेप में, लेखक ने एक अव्यवस्थित, जटिल खेल लिया, एक विशाल कंप्यूटर सिमुलेशन चलाया, और पाया कि इस अराजकता के नीचे, एक बहुत ही व्यवस्थित, लयबद्ध और अनुमानित संरचना मौजूद है जिसे पूरी तरह से समझा जाना बाकी है।

यहाँ अर्नव गर्ग के शोध पत्र "Structural Conjectures for 4 × n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र $4 \times n$ आयताकार ग्रिड पर खेले जाने वाले कॉम्बिनेटोरियल गेम Chomp की जांच करता है।

खेल के नियम: खिलाड़ी बारी-बारी से एक वर्ग (square) और उसके ऊपर तथा दाईं ओर के सभी वर्गों को हटाते हैं। शीर्ष-बाएँ वर्ग $(1,1)$ को "जहरीला" (poisoned) माना जाता है; जो खिलाड़ी इसे लेने के लिए मजबूर होता है, वह हार जाता है।
उद्देश्य: P-positions (पिछले खिलाड़ी के जीतने वाली स्थितियाँ, या वर्तमान खिलाड़ी के लिए हारने वाली स्थितियाँ) की पहचान करना।
संदर्भ: जबकि $1 \times n$ और $2 \times n$ के मामले पूरी तरह से हल किए जा चुके हैं, और $3 \times n$ के लिए आंशिक एल्गोरिदम समाधान उपलब्ध हैं, $4 \times n$ के मामले में व्यवस्थित कम्प्यूटेशनल विश्लेषण का अभाव था। यह शोध पत्र उन P-positions को सूचीबद्ध करने और अंतर्निहित संरचनात्मक पैटर्न की पहचान करने के माध्यम से इस अंतर को भरने का लक्ष्य रखता है।

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

लेखक ने $n = 500$ तक की बोर्ड चौड़ाई के लिए P-positions की गणना करने हेतु एक अनुकूलित रिट्रोग्रेड सॉल्वर (retrograde solver) C++ में विकसित किया।

अवस्था प्रतिनिधित्व (State Representation):
- स्थितियों को गैर-बढ़ते (non-increasing) टुपल्स $(a, b, c, d)$ के रूप में दर्शाया जाता है जहाँ $a \ge b \ge c \ge d \ge 0$ , जो प्रत्येक पंक्ति में वर्गों की संख्या को दर्शाता है।
- बिटपैकिंग (Bitpacking): मेमोरी उपयोग को कम करने और हैशिंग गति को अधिकतम करने के लिए प्रत्येक टुपल को चार 16-बिट फ़ील्ड्स का उपयोग करके एक एकल uint64 पूर्णांक में एनकोड किया गया है।
एल्गोरिदम डिज़ाइन:
- स्पार्स स्टोरेज (Sparse Storage): केवल P-positions को ही एक हैश सेट में संग्रहीत किया जाता है। सॉल्वर किसी ज्ञात P-position की ओर ले जाने वाली चाल (move) मिलते ही N-positions (वर्तमान खिलाड़ी के लिए जीत) को शॉर्ट-सर्किट कर देता है।
- बॉटम-अप मूल्यांकन (Bottom-Up Evaluation): अवस्थाओं को कुल सेल काउंट के बढ़ते क्रम में संसाधित किया जाता है, जिससे यह सुनिश्चित होता है कि किसी भी अवस्था का मूल्यांकन करने से पहले उसके सभी उत्तराधिकारियों (successors) का समाधान हो चुका है।
प्रदर्शन:
- $n \le 500$ के लिए 4,316,097 P-positions की गणना की गई।
- निष्पादन समय: Apple M4 प्रोसेसर पर लगभग 70 मिनट।
- मेमोरी उपयोग: शिखर उपयोग (Peak usage) 45 MB।
सत्यापन:
- ज्ञात $2 \times n$ फॉर्मूले (जहाँ $c=d=0$ होने पर $b=a-1$ होता है) के विरुद्ध मान्य किया गया।
- $3 \times n$ सब-केस ( $d=0$ ) के लिए एक स्वतंत्र पायथन सॉल्वर के साथ $n=50$ तक क्रॉस-चेक किया गया।
- डेटा आउटपुट में प्रारंभिक कॉलम-अलाइनमेंट बग को सुधारा गया।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

परिकलित डेटासेट के विश्लेषण से चार प्राथमिक संरचनात्मक अनुमान (conjectures) निकले:

क. अनुमान 1: अद्वितीय विस्तार गुण (Unique Extension Property)

कथन: किसी भी वैध ट्रिपल रो लेंथ $(a, b, c)$ के लिए, अधिकतम एक पूर्णांक $d$ मौजूद है जिससे $(a, b, c, d)$ एक P-position बन जाता है।
निहितार्थ: प्रोजेक्शन मैप $\pi: (a, b, c, d) \to (a, b, c)$ P-positions के सेट पर इनजेक्टिव (injective) है।
महत्व: यह सुझाव देता है कि $4 \times n$ गेम $3 \times n$ गेम का एक "डिटरमिनिस्टिक लिफ्ट" (deterministic lift) है। हालाँकि हर $(a, b, c)$ P-position में विस्तारित नहीं होता (केवल ~20% ही करते हैं), लेकिन यदि कोई विस्तार मौजूद है, तो चौथी पंक्ति की लंबाई $d$ अद्वितीय रूप से निर्धारित होती है। यह $3 \times n$ के मामले के विपरीत है, जहाँ ऐसा कोई सरल इनजेक्टिव मैपिंग पहले स्थापित नहीं किया गया था।

ख. अनुमान 2: स्पर्शोन्मुखी अनुपात (Asymptotic Ratios)

कथन: जैसे-जैसे बोर्ड की चौड़ाई $a \to \infty$ $a \to \infty$ होती है, P-positions में पंक्तियों की लंबाई के अनुपात निश्चित स्थिरांकों (constants) की ओर अभिसरित होते हैं:
- $b/a \to L_1 \approx 0.762$
- $c/a \to L_2 \approx 0.499$
- $d/a \to L_3 \approx 0.224$
कार्यप्रणाली: इनका अनुमान विंडोed मीडियंस, रोलिंग विंडोज और पावर-लॉ कर्व फिटिंग के माध्यम से लगाया गया।
अवलोकन: इन स्थिरांकों के लिए कोई सटीक बीजगणितीय पहचान (algebraic identity) नहीं मिली। हालाँकि, $L_3 \approx 0.224$ उल्लेखनीय रूप से $\cos(3\pi/7) \approx 0.2225$ के करीब है, जो एक संभावित छिपे हुए बीजगणितीय संबंध का संकेत देता है।

ग. अनुमान 3: अवधि-112 मॉड्यूलर संरचना (Period-112 Modular Structure)

कथन: वे ट्रिपल $(a, b, c)$ जो P-positions में विस्तारित होते हैं, एक मौलिक अवधि (fundamental period) 112 के साथ एक मॉड्यूलर संरचना प्रदर्शित करते हैं।
साक्ष्य:
- $d$ -मानों के अनुक्रम के ऑटोकोरिलेशन विश्लेषण से अंतराल (lag) 112 पर एक तीव्र शिखर (peak) दिखाई देता है।
- केवल $c$ और $(a-b) \pmod{112}$ का उपयोग करने वाला एक लॉजिस्टिक क्लासिफायर विस्तार क्षमता (extendability) की 79% सटीकता के साथ भविष्यवाणी करता है।
- ची-स्क्वायर टेस्ट पुष्टि करते हैं कि अन्य मॉड्यूली की तुलना में मोडुलस 112 सबसे मजबूत सांख्यिकीय पृथक्करण ( $\chi^2 = 12,433$ ) प्रदान करता है।
व्याख्या: $112 = \text{lcm}(7, 8) \times 2$ । कारक 7 संभवतः $3 \times n$ सब-गेम की आवधिकता (periodicity) से आता है, जबकि कारक 8 अस्पष्ट है (जो बिट-पैकिंग आर्टिफैक्ट्स को खारिज करता है)।

घ. अनुमान 4: रैखिक शंकु ज्यामिति (Linear Cone Geometry)

कथन: विस्तारित होने वाले ट्रिपल $(a, b, c)$ का सेट $\mathbb{R}^3$ में एक रैखिक शंकु (linear cone) बनाता है।
ज्यामिति: एक निश्चित $c$ के लिए, वैध रेंज $(a, b)$ एक निरंतर बैंड बनाती है। इस बैंड की चौड़ाई $c$ के साथ रैखिक रूप से बढ़ती है:
$\text{width}(c) \approx \frac{11}{8} \cdot c + f(c \pmod{112})$
जहाँ $f(c \pmod{112})$ एक बाउंडेड पीरियोडिक फंक्शन है। ढलान (slope) $11/8 = 1.375$ स्लाइस-आधारित मापों से प्राप्त की गई थी।

4. महत्व और भविष्य की दिशाएं (Significance and Future Directions)

संरचनात्मक अंतर्दृष्टि: निष्कर्ष बताते हैं कि $4 \times n$ चोंप (Chomp) में पहले के संदेह की तुलना में अधिक समृद्ध और अधिक डिटरमिनिस्टिक संरचना है, जो "यूनिक एक्सटेंशन" गुण के कारण $3 \times n$ मामले से सरल हो सकती है।
सामान्यीकरण: लेखक यह परिकल्पना करते हैं कि 'यूनिक एक्सटेंशन' गुण सभी $k$ के लिए $k \times n$ चोंप में सामान्य हो सकता है, जिसका अर्थ है कि सभी चोंप गेम्स को हल किए गए $2 \times n$ केस द्वारा पुनरावर्ती रूप से (recursively) निर्धारित किया जा सकता है।
खुले प्रश्न:
1. प्रमाण: क्या 'यूनिक एक्सटेंशन' गुण को कॉम्बिनेटोरियल रूप से सिद्ध किया जा सकता है?
2. बीजगणितीय सीमाएँ: क्या स्पर्शोन्मुखी अनुपात (asymptotic ratios) एक सामान्य बहुपद (polynomial) के मूल (roots) हैं?
3. उच्च आयाम: क्या यह $5 \times n$ के लिए भी सत्य है? (इसके लिए $O(n^5)$ स्टेट स्पेस की आवश्यकता होगी)।
4. अवधि का स्रोत: 112-साइकिल में अवधि-8 घटक का स्रोत क्या है?
5. क्लोज्ड फॉर्म: क्या ~20% विस्तार योग्य ट्रिपल्स को क्लोज्ड-फॉर्म मास्क द्वारा वर्णित किया जा सकता है?

शोध पत्र यह भी नोट करता है कि $d$ -मानों के अनुक्रम को A395126 के रूप में 'ऑन-लाइन एनसाइक्लोपीडिया ऑफ इंटीजर सीक्वेंस' (OEIS) में जमा किया गया है। कोड और डेटा लेखक के GitHub रिपॉजिटरी के माध्यम से सार्वजनिक रूप से उपलब्ध हैं।