एलगोरिदम आधारित कॉम्बिनेटरिक्स समस्या IMO शैली [डुप्लिकेट]
समस्या को चित्र में वर्णित किया गया है, समाधान को रचनात्मक प्रमाण माना जाता है, इसलिए आपको एक एल्गोरिथ्म खोजने की आवश्यकता है जो रनिंग टाइम जैसे सामान की परवाह किए बिना काम करता है। कोई मदद आभारी होगी मैं इसे हल नहीं कर सकता और मैं थोड़ी देर के लिए कोशिश कर रहा हूं
संपादित करें: मेरी मुख्य दिशा हर कच्चे पर नकारात्मक राशि के साथ संकेत बदल रही थी, अब हर कच्चा पूरा हो गया है और सभी प्रविष्टियों का योग गैर-देनदार है (चूंकि सभी कच्चे का योग अब अप्रसार है)
जवाब
यदि किसी पंक्ति या स्तंभ में ऋणात्मक योग है, तो किसी एक को चुनें और संकेतों को उलट दें।
प्रक्रिया में सुधार करें।
प्रत्येक संक्रमण के बाद, मैट्रिक्स में सभी प्रविष्टियों का योग बढ़ जाता है।
लेकिन प्रविष्टियों का पूर्ण मूल्य अपरिवर्तित रहता है, इसलिए कुल योग के लिए केवल बहुत अधिक संभावनाएं हैं।
यह इस प्रकार है कि प्रक्रिया अंततः समाप्त हो जाएगी।
बस निम्नलिखित सरल एल्गोरिथ्म का उपयोग करें: प्रत्येक मोड़ में, एक ऋणात्मक पंक्ति या स्तंभ के चिन्ह को ऋणात्मक राशि के साथ उल्टा करें और हम यह साबित करेंगे कि यह प्रक्रिया परिमित चाल में समाप्त होती है: ध्यान दें कि इस एल्गोरिथम का उपयोग करके सभी में संख्याओं का योग। बोर्ड हमेशा बढ़ेगा और क्योंकि यह राशि ऊपर से बंधी हुई है और इस राशि के लिए भी सीमित संभावनाएं हैं, हमारा एल्गोरिदम कहीं बंद हो जाएगा और वहाँ बिंदु है कि सभी पंक्तियों और स्तंभों का योग गैर-नकारात्मक है।