एक "मार्कोव खेल"

Question

मैं नीचे मार्कोव खेलों के समान खेल का वर्णन करता हूं। मैं सिर्फ एक या एक नहीं बल्कि गेम्स की 1-पैरामीटर श्रृंखला का चयन कर रहा हूं। खुली चुनौती यह पता लगाने की है कि कौन से खिलाड़ी हैं$\ 0\ $ या $\ 1\ $ दिए गए पैरामीटर में से प्रत्येक के लिए एक जीतने की रणनीति है $\ W.$

सूचना $\ n\%2=0\ $ के लिये $\ n\ $ भी, और $\ n\%2=1\ $ के लिये $\ n\ $ विषम ;;

चलो $ d(0)=J(0)=0.\ $ मनमाना सकारात्मक पूर्णांक के लिए $\ n,\ $ खिलाड़ी $\ n\%2\ $ एक सकारात्मक पूर्णांक का चयन करता है $\ d(n)\le d(n-1)+1;\ $ तब फिर $\ J(n)=J(n-1)+d(n).$

जब खिलाड़ी खेल में प्रतिस्पर्धा करते हैं $\ M(W),\ $ कहां है $\ W\ $ एक मनमाने ढंग से नियत धनात्मक पूर्णांक है, तो वह खिलाड़ी जो वास्तव में मिलता है $J(n)=W\ $ जीतता है।

चलो $\ \omega(W)=0\ $ अगर खिलाड़ी $0$ जीतने की रणनीति है $M(W);\ $ अन्यथा होने दो $\ \omega(W)=1\ $ अगर खिलाड़ी $1$ जीतने की रणनीति है $M(W)$।

समस्या:   कम्प्यूट फ़ंक्शन$\ \omega:\mathbb N\to\{0\ 1\}.$

उदाहरण के लिए: $\ \omega(1)=1;\ \omega(2)=\omega(3)=0;\ \omega(4)=1, $ हालांकि, $\ \omega(120)\ $ या $\ \omega(5553)\ $ थोड़ा कठिन है (और मेरे लिए अज्ञात है)।

Answer 1

उत्तर अधिक से अधिक संख्या के साथ नहीं बदलता है।

पूरा जवाब है $$ \omega(W)=\left\{ \begin{array}{ll} 1, & W\%5=1,4\\ 0, & W\%5=0,2,3 \end{array}\right. $$

हमें वह पद कहते हैं $(W-J,d)$ अगर खिलाड़ी जीत रहा है $n\%2$ खेल के लिए एक जीतने की रणनीति है $M(W)$ अपनी बारी पर $n$ साथ से $d(n)=d,J(n)=J$। यह अन्यथा खो रहा है। स्पष्ट रूप से, यह वास्तव में केवल अंतर पर निर्भर करता है$W-J$।

$(i,d)$ जीत रहा है अगर वहाँ हार मौजूद है $(j,f)$ सेंट $j+f=i,f\le d+1$। हमें इसमें दिलचस्पी है या नहीं$(W-1,1)$ जीत रहा है।

इसके लिए यह केवल विचार करने के लिए पर्याप्त है $(i,d)$ साथ से $d\le 3$।

पैटर्न इस तरह दिखता है:

$ \begin{array}{ccc} - & - & -\\ + & + & +\\ + & + & +\\ - & + & +\\ + & + & +\\ - & - & -\\ \vdots & \vdots & \vdots \end{array} $

इसे देखने के लिए, नोटिस करें:

• $(0,d)$ सभी के लिए खो रहा है $d$, यानी पहली पंक्ति से भरा है $-$का है
• अगर $(i,d)$ जीत रहा है, तो $(i,d+1)$ जीत रहा है, यानी के दाईं ओर $+$ हमेशा एक और है $+$

Answer 2

हमारे पास @JosephGordon की ओर से पहले से ही एक पूर्ण उत्तर है जो समय-समय पर साबित हुआ $\ \omega,\ $ अवधि की अवधि 5. जोसेफ - बहुत धन्यवाद!

मुझे एक समाधान लिखना है जो कम से कम मेरे लिए अनुसरण करना आसान है।

उस खिलाड़ी को याद करो $\ \omega(n)\ $ मार्कोव खेल के लिए जीतने की रणनीति है $\ M(n).$

हर सकारात्मक पूर्णांक के लिए प्रमेय$\ n\ $ निम्नलिखित दो गुण धारण करें:

• खिलाड़ी $\ \omega(n)\ $ के हर खेल को जीत सकते हैं $\ M(n)\ $ अपनी खुद की सभी चालों का चयन करके $\ d(k)\le 3;$

• $\ \omega(n+5) = \omega(5).\ $

प्रमाण   खिलाड़ी$\ \omega(n)\ $, जब खेल खेल रहे हैं $\ M(n+5)\ $, स्थिति में आने में सक्षम है $\ n\ $ ऐसे कदमों का उपयोग करते समय $\ d(k)\le 3\ $हर बार। विशेष रूप से,$\ d(t)\le 3\ $ कब अ $\ J(t)=n.\ $ इस प्रकार, अब हमारे पास खेल के केवल चार एक्सटेंशन हैं:

• $\ d(t+1)=4.\ $ फिर खिलाड़ी $\ \omega(n)\ $ खेलता है $\ d(t+2)=1\ $ और जीत (तब से $\ J(t+2)=n+5\ \text{and}\ t+2\equiv t\mod 2)$;

• $\ d(t+1)=3.\ $ फिर खिलाड़ी $\ \omega(n)\ $ खेलता है $\ d(t+2)=2\ $ और जीतता है;

• $\ d(t+1)=2.\ $ फिर खिलाड़ी $\ \omega(n)\ $ खेलता है $\ d(t+2)=3\ $ और जीतता है;

• $\ d(t+1)=1.\ $ फिर खिलाड़ी $\ \omega(n)\ $ खेलता है $\ d(t+2)=1;\ $ फिर दूसरा खिलाड़ी खेलता है $\ d(t+3)= 1$ या $2\ $, और खिलाड़ी $\ \omega(n)\ $ खेलता है $\ 2$ या $1\ $ क्रमशः, और जीतता है।

तर्क का औपचारिक बाकी पूरी तरह से नियमित और स्पष्ट है। PROOF का अंत।

का पूरा संख्यात्मक विवरण $\ \omega\ $ उपरोक्त प्रमेय और प्रारंभिक द्वारा दिया गया है $5$ मान:

$$ \omega(1)=1;\,\ \omega(2)=\omega(3)=0;\,\ \omega(4)=1, \,\ \omega(5)=0 $$

उदाहरण के लिए, $\ \omega(5)=0\ $ क्योंकि जे (1) = 1, फिर खिलाड़ी $0$ d (2) = 1, J (2) = 2 खेल सकते हैं, फिर - खिलाड़ी द्वारा एक चाल के बाद $0$ - खिलाड़ी $\ 0\ $ खेलेंगे $\ J(4)=5.$