2025-11-19T22:58:13.964427

A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence

Komak, Miyadera, Murakami

In this paper, we study a variant of the classical Wythoff's game. The classical form is played with two piles of stones, from which two players take turns to remove stones from one or both piles. When removing stones from both piles, an equal number must be removed from each. The player who removes the last stone or stones is the winner. Equivalently, we consider a single chess queen placed somewhere on a large grid of squares. Each player can move the queen toward the upper-left corner of the grid, either vertically, horizontally, or diagonally, in any number of steps. The winner is the player who moves the queen into the upper-left corner, the position (0,0) in our coordinate system. We call (0,0) the terminal position of Wythoff's game. In our variant of Wythoff's game, we have a set of positions {(0,0),(1,0),(0,1),(1,1),(2,0),(0,2)} as the terminal set. If a player moves the queen into this terminal set, that player is the winner of the game. The P-positions of this variant are described by the P-positions of Wythoff's game and Hofstadter's G-Sequence. This variant has two remarkable properties. For a position (x,y) with x >= 8 or y >= 8, the Grundy number of the position (x,y) is 1 in this variant if and only if (x,y) is a P-position of Wythoff's game. There is another remarkable property.For a position (x,y) with x >= 8 or y >= 8, (x,y) is a P-position of of the misere version of this variant if and only if (x,y) is a P-position of of Wythoff's game.

academic

विथॉफ खेल का एक प्रकार जो हॉफस्टैडर के जी-अनुक्रम द्वारा परिभाषित है

मूल जानकारी

पेपर ID: 2510.11767
शीर्षक: A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence
लेखक: काहोरी कोमाकी, रयोहेई मियाडेरा, आओई मुराकामी
वर्गीकरण: math.CO (संयोजन गणित)
प्रकाशन समय: 13 अक्टूबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.11767

सारांश

यह पेपर शास्त्रीय विथॉफ खेल के एक प्रकार का अध्ययन करता है। शास्त्रीय विथॉफ खेल में दो पत्थरों के ढेर होते हैं, दो खिलाड़ी बारी-बारी से एक या दोनों ढेरों से पत्थर निकालते हैं, और जब दोनों ढेरों से निकाला जाता है तो समान संख्या में निकालना अनिवार्य है। अंतिम पत्थर या पत्थरों को निकालने वाला खिलाड़ी जीतता है। समान रूप से, इसे बड़ी ग्रिड पर शतरंज की रानी को स्थानांतरित करने के रूप में देखा जा सकता है, जहां प्रत्येक खिलाड़ी रानी को ऊपरी-बाएं कोने (0,0) की ओर किसी भी दिशा में (ऊर्ध्वाधर, क्षैतिज या विकर्ण) स्थानांतरित कर सकता है।

इस पेपर के प्रकार में, टर्मिनल स्थिति समुच्चय को {(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)} तक विस्तारित किया गया है। इस प्रकार की P स्थितियों को विथॉफ खेल की P स्थितियों और हॉफस्टैडर के जी अनुक्रम के माध्यम से वर्णित किया जाता है। इस प्रकार के दो उल्लेखनीय गुण हैं: x≥8 या y≥8 वाली स्थितियों (x,y) के लिए, इस प्रकार में स्थिति (x,y) का ग्रंडी संख्या 1 है यदि और केवल यदि (x,y) विथॉफ खेल की P स्थिति है; x≥8 या y≥8 वाली स्थितियों (x,y) के लिए, (x,y) इस प्रकार के मिसेरे संस्करण की P स्थिति है यदि और केवल यदि (x,y) विथॉफ खेल की P स्थिति है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

यह अनुसंधान शास्त्रीय विथॉफ खेल के एक नए प्रकार का विश्लेषण और समाधान करने का लक्ष्य रखता है, जिसमें टर्मिनल शर्तें एकल स्थिति (0,0) से छह स्थितियों वाले समुच्चय तक विस्तारित होती हैं। यह विस्तार सरल प्रतीत होता है, लेकिन खेल की जटिलता और रणनीतिक संरचना को महत्वपूर्ण रूप से बदलता है।

महत्व

सैद्धांतिक महत्व: विथॉफ खेल संयोजन खेल सिद्धांत की एक शास्त्रीय समस्या है, जिसकी P स्थितियां स्वर्णिम अनुपात φ=(1+√5)/2 से घनिष्ठ रूप से संबंधित हैं। इसके प्रकारों का अध्ययन संयोजन खेलों की संरचनात्मक गुणों की गहन समझ में सहायता करता है।
गणितीय संबंध: यह अनुसंधान हॉफस्टैडर के जी अनुक्रम और संयोजन खेल सिद्धांत के बीच नए संबंध स्थापित करता है, जो पूर्व अनुसंधान में कम छुआ गया है।
विधि नवाचार: फलन g(n) और हॉफस्टैडर के जी अनुक्रम को प्रस्तुत करके, जटिल टर्मिनल शर्तों वाले संयोजन खेलों के विश्लेषण के लिए नए गणितीय उपकरण प्रदान करता है।

मौजूदा विधियों की सीमाएं

शास्त्रीय विथॉफ खेल की P स्थितियों का स्पष्ट बंद-रूप अभिव्यक्ति है, लेकिन जब टर्मिनल शर्तें स्थितियों के समुच्चय में बदल जाती हैं, तो पारंपरिक विश्लेषण विधियां सीधे लागू करना कठिन होता है। मौजूदा संयोजन खेल सिद्धांत में इस प्रकार की विस्तारित टर्मिनल शर्तों को संभालने की व्यवस्थित विधि की कमी है।

मुख्य योगदान

नए खेल प्रकार को परिभाषित किया: विथॉफ खेल की टर्मिनल स्थितियों को एकल बिंदु (0,0) से समुच्चय {(x,y): x+y≤2} तक विस्तारित किया
P स्थितियों का पूर्ण लक्षण वर्णन स्थापित किया: फलन g(n) और हॉफस्टैडर के जी अनुक्रम को प्रस्तुत करके, इस प्रकार की P स्थितियों के लिए सटीक सूत्र दिया
दो महत्वपूर्ण गुणों की खोज की:
- x≥8 या y≥8 वाली स्थितियों के लिए, इस प्रकार की ग्रंडी संख्या 1 है यदि और केवल यदि वह स्थिति मूल विथॉफ खेल की P स्थिति है
- x≥8 या y≥8 वाली स्थितियों के लिए, वह स्थिति मिसेरे संस्करण की P स्थिति है यदि और केवल यदि यह मूल विथॉफ खेल की P स्थिति है
हॉफस्टैडर जी अनुक्रम के साथ संबंध स्थापित किया: साबित किया कि फलन g(n) को हॉफस्टैडर के जी अनुक्रम के माध्यम से पुनरावर्ती रूप से परिभाषित किया जा सकता है

विधि विस्तार

कार्य परिभाषा

इनपुट: खेल स्थिति (x,y), जहां x,y∈ℤ≥0 आउटपुट: यह निर्धारित करना कि वह स्थिति P स्थिति (पूर्व खिलाड़ी की जीत) है या N स्थिति (अगले खिलाड़ी की जीत) बाधाएं: स्थानांतरण नियम शास्त्रीय विथॉफ खेल के समान हैं, लेकिन टर्मिनल समुच्चय {(x,y): x+y≤2} है

मुख्य गणितीय ढांचा

1. फलन g(n) की परिभाषा

g(0) = 1, g(1) = 0
g(n) = {
  1 - g(m)  यदि ⌊nφ⌋ = ⌊m(φ+1)⌋ + 1 किसी m∈ℤ≥0 के लिए
  1         अन्य स्थितियों में
}

2. P स्थिति समुच्चय का लक्षण वर्णन

P₁ = P₁,₁ ∪ P₁,₂ ∪ {(0,0)}, जहां:

P₁,₁ = {(⌊nφ⌋ + g(n) - 1, ⌊n(φ+1)⌋ + g(n)) : n ∈ ℤ≥0}
P₁,₂ = {(⌊n(φ+1)⌋ + g(n), ⌊nφ⌋ + g(n) - 1) : n ∈ ℤ≥0}

3. हॉफस्टैडर जी अनुक्रम के साथ संबंध

n≥2 के लिए:

g(n) = {
  1 - g(h(n-1))  यदि h(n-2) < h(n-1)
  1              अन्य स्थितियों में
}

जहां h हॉफस्टैडर का जी अनुक्रम है: h(0)=0, h(n)=n-h(h(n-1))

तकनीकी नवाचार बिंदु

अनुक्रम विघटन तकनीक: प्राकृतिक संख्याओं को निचले विथॉफ अनुक्रम A₁={⌊nφ⌋} और ऊपरी विथॉफ अनुक्रम A₂={⌊n(φ+1)⌋} में विघटित करके, एक व्यवस्थित विश्लेषण ढांचा स्थापित किया।
पुनरावर्ती फलन डिजाइन: फलन g(n) का डिजाइन चतुराई से टर्मिनल समुच्चय के विस्तार के P स्थिति वितरण पर प्रभाव को पकड़ता है।
ग्रंडी संख्या विश्लेषण: ग्रंडी संख्या की गणना के माध्यम से, इस प्रकार और मूल खेल के बीच गहरे संबंध स्थापित किए।

प्रयोगात्मक सेटअप

सैद्धांतिक सत्यापन विधि

यह पेपर शुद्ध सैद्धांतिक प्रमाण विधि अपनाता है, निम्नलिखित चरणों के माध्यम से परिणामों को सत्यापित करता है:

पूर्णता प्रमाण: साबित करना कि किसी भी गैर-P स्थिति से P स्थिति तक स्थानांतरण संभव है
सामंजस्य प्रमाण: साबित करना कि P स्थिति से किसी अन्य P स्थिति तक स्थानांतरण असंभव है
गणनात्मक सत्यापन: छोटे पैमाने की स्थितियों के लिए संपूर्ण गणना सत्यापन

विशिष्ट सत्यापन सीमा

स्थिति निर्देशांक x,y≤7 के सभी मामलों के लिए पूर्ण गणना विश्लेषण
x≥8 या y≥8 की स्थितियों के लिए, सैद्धांतिक प्रमाण के माध्यम से मूल विथॉफ खेल के साथ समतुल्यता संबंध स्थापित किया

प्रयोगात्मक परिणाम

मुख्य सैद्धांतिक परिणाम

प्रमेय 1: P स्थितियों का पूर्ण लक्षण वर्णन

समुच्चय P₁ इस खेल प्रकार की P स्थितियों का समुच्चय है, यह Lemma 8 और Lemma 12 के माध्यम से साबित होता है:

Lemma 8: P₁ में स्थिति से P₁ में किसी अन्य स्थिति तक स्थानांतरण असंभव है
Lemma 12: P₁ में न होने वाली किसी भी स्थिति से P₁ में किसी स्थिति तक स्थानांतरण संभव है

प्रमेय 2: मूल विथॉफ खेल के साथ संबंध

x≥8 या y≥8 वाली स्थितियों (x,y) के लिए:

इस प्रकार में G₂(x,y,1)=0 यदि और केवल यदि मूल खेल में G₀(x,y)=0
यह दोनों खेलों के बीच "बड़ी" स्थितियों पर समतुल्यता स्थापित करता है

प्रमेय 3: मिसेरे संस्करण की गुण

मिसेरे संस्करण (टर्मिनल समुच्चय में प्रवेश करने वाला खिलाड़ी हारता है) की P स्थितियां मूल खेल और एकल पत्थर ढेर के योग खेल की P स्थितियों के समान हैं।

छोटे पैमाने के सत्यापन परिणाम

संपूर्ण गणना सत्यापन के माध्यम से, निम्नलिखित छोटे पैमाने की P स्थितियां निर्धारित की गईं:

समुच्चय A: {(0,0,1), (0,1,1), (0,2,1), (1,0,1), (1,1,1), (2,0,1), (3,6,1), (6,3,1), (4,8,1), (8,4,1)}
समुच्चय B: {(0,3,1), (1,2,1), (2,1,1), (3,0,1), (4,4,1), (5,7,1), (7,5,1)}
समुच्चय C: {(0,0), (1,2), (2,1), (3,5), (5,3), (4,7), (7,4)}

मुख्य खोजें

सीमा प्रभाव: x,y≤7 की सीमा में, P स्थिति वितरण मूल विथॉफ खेल से महत्वपूर्ण रूप से भिन्न है
स्पर्शोन्मुख व्यवहार: जब निर्देशांक पर्याप्त रूप से बड़े हों, तो इस प्रकार का व्यवहार मूल विथॉफ खेल में परिवर्तित होता है
अनुक्रम गुण: फलन g(n) के मान पैटर्न हॉफस्टैडर जी अनुक्रम के वृद्धि गुणों से घनिष्ठ रूप से संबंधित हैं

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

पूर्ण समाधान: विथॉफ खेल के विस्तारित टर्मिनल प्रकार की P स्थितियों का पूर्ण लक्षण वर्णन दिया
गहरे संबंध: इस प्रकार और हॉफस्टैडर जी अनुक्रम के बीच आवश्यक संबंध का खुलासा किया
स्पर्शोन्मुख समतुल्यता: बड़े निर्देशांक की स्थितियों में, इस प्रकार और मूल खेल की समतुल्यता साबित की

सीमाएं

जटिलता: फलन g(n) की परिभाषा अपेक्षाकृत जटिल है, मूल विथॉफ खेल के बंद-रूप समाधान जितनी सुंदर नहीं है
गणनात्मक दक्षता: P स्थिति का निर्धारण हॉफस्टैडर अनुक्रम की गणना की आवश्यकता है, जिसमें गणनात्मक जटिलता समस्या हो सकती है
सामान्यीकरण: विधि अन्य टर्मिनल समुच्चयों तक सामान्यीकृत की जा सकती है या नहीं, यह स्पष्ट नहीं है

भविष्य की दिशाएं

अधिक सामान्य टर्मिनल समुच्चय: किसी भी टर्मिनल समुच्चय के विथॉफ खेल प्रकार का अनुसंधान
एल्गोरिदम अनुकूलन: P स्थिति निर्धारण के लिए अधिक कुशल एल्गोरिदम विकसित करना
अन्य पुनरावर्ती अनुक्रम: संयोजन खेलों में अन्य प्रसिद्ध पुनरावर्ती अनुक्रमों के अनुप्रयोग का अन्वेषण

गहन मूल्यांकन

लाभ

सैद्धांतिक गहराई: संयोजन खेल सिद्धांत और पुनरावर्ती अनुक्रम सिद्धांत के बीच नए संबंध स्थापित करता है, जिसका महत्वपूर्ण सैद्धांतिक मूल्य है
विधि नवाचार: फलन g(n) का डिजाइन चतुर है, पुनरावर्ती परिभाषा के माध्यम से जटिल खेल संरचना को पकड़ता है
प्रमाण पूर्णता: पूर्ण गणितीय प्रमाण प्रदान करता है, जिसमें बड़ी संख्या में तकनीकी लेम्मा की विस्तृत व्याख्या शामिल है
परिणाम गहराई: खोजी गई स्पर्शोन्मुख समतुल्यता गुण जटिल संयोजन खेलों को समझने के लिए नया दृष्टिकोण प्रदान करता है

कमियां

अभिव्यक्ति जटिलता: फलन g(n) की परिभाषा काफी अमूर्त है, जो परिणामों की सहज समझ को प्रभावित कर सकती है
सीमित व्यावहारिकता: हालांकि सैद्धांतिक रूप से पूर्ण है, लेकिन व्यावहारिक अनुप्रयोग में इसका मूल्य अभी स्पष्ट नहीं है
सामान्यीकरण कठिनाई: विधि की विशेषता अन्य समस्याओं पर इसके अनुप्रयोग को सीमित कर सकती है

प्रभाव

शैक्षणिक मूल्य: संयोजन खेल सिद्धांत और पुनरावर्ती अनुक्रम सिद्धांत के अंतःविषय अनुसंधान के लिए नई दिशा खोलता है
पद्धति योगदान: जटिल टर्मिनल शर्तों वाले संयोजन खेलों के विश्लेषण के लिए नए उपकरण प्रदान करता है
सैद्धांतिक पूर्णता: विथॉफ खेल प्रकार के सैद्धांतिक प्रणाली को समृद्ध करता है

लागू परिदृश्य

सैद्धांतिक अनुसंधान: संयोजन गणित और खेल सिद्धांत के सैद्धांतिक अनुसंधान के लिए उपयुक्त
एल्गोरिदम डिजाइन: संबंधित खेलों की इष्टतम रणनीति एल्गोरिदम डिजाइन के लिए सैद्धांतिक आधार प्रदान करता है
शिक्षण अनुप्रयोग: पुनरावर्ती अनुक्रमों और संयोजन समस्याओं के संबंध को प्रदर्शित करने के लिए एक उत्कृष्ट मामला अध्ययन के रूप में काम कर सकता है

संदर्भ

M.H. Albert, R.J. Nowakowski, and D. Wolfe: Lessons In Play, A K Peters/CRC Press, 2007
D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, 1980
W.A. Wythoff: A modification of the game of Nim, Nieuw Arch. Wiskd, 7 (1907), 199-202
V. Granville and J.-P. Rasson, A strange recursive relation, J. Number Theory 30 (1988), 238–241

यह पेपर संयोजन खेल सिद्धांत के क्षेत्र में महत्वपूर्ण सैद्धांतिक योगदान देता है, हॉफस्टैडर जी अनुक्रम को चतुराई से संयोजित करके, जटिल टर्मिनल शर्तों वाले विथॉफ खेल प्रकार के विश्लेषण के लिए एक पूर्ण गणितीय ढांचा प्रदान करता है। हालांकि व्यावहारिकता के पहलू में कुछ सीमाएं हैं, लेकिन इसकी सैद्धांतिक गहराई और विधि नवाचार इसे इस क्षेत्र का एक महत्वपूर्ण अनुसंधान परिणाम बनाते हैं।