खेल सिद्धांत

विषय पर विस्तार करने के लिए, हम प्रसिद्ध नीम्स गेम की भिन्नता का विश्लेषण करेंगे।

और इसलिए, मेज पर पत्थरों के कई ढेर हैं। एक चाल में, किसी भी ढेर से पत्थरों की एक मनमानी संख्या लेने की अनुमति है, किसी भी ढेर को दो गैर-खाली लोगों में विभाजित करने के लिए।

सामान्य नियमों में, एक खिलाड़ी जो एक चाल नहीं खो सकता है। Giveaways में, वह जो हारने के बाद टेबल पर कोई पत्थर नहीं रहता।







निर्णय



समस्या को हल करने के लिए, ओलंपियन को खेलों के सिद्धांत से परिचित होना चाहिए



खेल के इस भिन्नता का विश्लेषण एक नियमित खेल की तुलना में अधिक जटिल नहीं है।

एक नियमित खेल के लिए स्प्राग-ग्रैंडि फंक्शन (या स्प्राग-ग्रुंडी, जैसा कोई व्यक्ति करता था) का निम्न रूप है।



जी (एन) =

{ n-1 for n (mod 4) == 0},

{ n के लिए n (mod 4) == 1 या 2},

{ n + 1 for n (mod 4) == 3}



प्रमाण एन पर प्रेरण द्वारा दिया जा सकता है। मामला n = 1 तुच्छ है (आप हमेशा उठा सकते हैं और पूरे गुच्छा को जीत सकते हैं)। हमारे ग्रैंड फंक्शन को सभी k <n के लिए होल्ड करें। एन के लिए जाँच करें।

1. इस तरह के ढेर से आप आवश्यक संख्या में पत्थरों को हटाकर किसी भी छोटे आकार का ढेर प्राप्त कर सकते हैं, अर्थात एक छोटे पैरामीटर के साथ हमारा कार्य।
2. आप यह सुनिश्चित कर सकते हैं कि ढेर को दो में विभाजित करने से आपको G = (k), k <n के अलावा किसी ग्रैंड नंबर के साथ स्थिति प्राप्त करने की अनुमति नहीं मिलती है, सिवाय n = 4 * k + 3 के। फिर, P (1, n-1) = G (1) xor G (n-1) = 1 xor (4 * k + 2) = 4 * k + 3 = n। वह है, जी (4 * के + 3) = एन + 1।

आइए बदले हुए नियमों के अनुसार खेल में वापस जाएं।

आइए हम यह साबित करते हैं कि खेल एक समान है, सिवाय इसके कि जब सभी ढेर में 1 पत्थर हो। इस मामले में, कुछ भी खिलाड़ियों पर निर्भर नहीं करता है और खेल का परिणाम समता n द्वारा निर्धारित किया जाता है।



सबूत।

हम पी द्वारा पदों के वर्णित सेट को निरूपित करते हैं। स्प्रैग ग्रैडी नंबरों की परिभाषा के अनुसार, हम दिखाते हैं कि पी से सभी पद खो रहे हैं, और सभी से पी! (अंकन "नहीं पी") जीत रहे हैं, और पी से अन्य पदों के लिए अन्य पदों से कोई चाल नहीं है।

यह साबित करना आसान है कि किसी भी स्थिति से! R में एक चाल है। ऐसा करने के लिए, आपको खेल की रणनीति को थोड़ा बदलना होगा। कहते हैं, अगर हम चयनित चाल में ढेर में 1 पत्थर छोड़ते हैं, तो इसके बजाय हम पूरे ढेर को लेते हैं और इसके विपरीत, अगर हम पूरे ढेर को लेते हैं, तो हम इसके बजाय 1 पत्थर छोड़ देंगे। और अंत में, यदि हम ढेर को 2 में 1 पत्थर से विभाजित करते हैं, तो हम हमेशा केवल 1 पत्थर छोड़ सकते हैं।



यह विधि आपको केवल कुछ चरम मामलों पर विचार करते हुए, "सस्ता" के नियमों के साथ समस्याओं को हल करने की अनुमति देती है।