मोनोक्रोमेटिक आयतों के बिना चार रंगों में मैट्रिक्स 17x17 रंग

इस तस्वीर में क्या आश्चर्य है?



वास्तव में, यह अद्वितीय है। 17 x 17 मैट्रिक्स चार रंगों के साथ चित्रित किया गया है, और आप इस पर एक (!) आयत नहीं बना सकते हैं ताकि इसके सभी कोने समान रंग हों। यह एक्स और वाई कुल्हाड़ियों के समानांतर विभिन्न बिंदुओं और किनारों पर किसी भी आकार के आयतों को संदर्भित करता है।

तुलना के लिए, यदि आप किसी भी सेल में रंग बदलते हैं, तो बहुत सारे मोनोक्रोमेटिक आयताकार तुरंत दिखाई देते हैं। उदाहरण के लिए, अगर ऊपरी बाएं सेल का रंग नीले से लाल रंग में बदल जाता है।



इसी तरह, यदि आप बीच से एक यादृच्छिक सेल बदलते हैं।



कॉम्बिनेटरियल एनालिसिस के क्षेत्र की यह समस्या 20 नवंबर 2009 को क्ले मैथेमेटिक्स इंस्टीट्यूट के विलियम गेसार्क द्वारा पेश की गई थी, जिन्होंने पहले कलरिंग मैट्रिसेस पर एक मौलिक काम प्रकाशित किया था, और जिसमें उन्होंने मल्टीचैरामिक आयतों के बिना चार रंगों वाले लगभग सभी आकारों के मैट्रिस के रंग या गैर-रंगाई को साबित किया। उनकी तालिका में केवल कुछ आकार अज्ञात रहे: 17x17, 18x18 और 12X21।

मेथेमेटिशियन ब्रांड स्टाइनबैक इंस्टीट्यूट ऑफ़ कंप्यूटर साइंस से तकनीकी विश्वविद्यालय फ़्रेबरग माइनिंग एकेडमी (जर्मनी) में, और वेस्ट इंडीज़ (त्रिनिदाद और टोबैगो) विश्वविद्यालय में कंप्यूटर और सूचना प्रौद्योगिकी विभाग के एक पूर्व कर्मचारी क्रिश्चियन पोस्टहॉफ ने चार के साथ 17x17 की गिनती की। एक एकल एक रंग की आयत के बिना रंग! इसके अलावा, वे 18x18 मैट्रिक्स को रंग देने में भी कामयाब रहे। इस प्रकार, आज का एकमात्र अनसुलझे प्रारूप 21x12 है।

विक्टोरिया में 14 मई, 2012 को मल्टीपल-वेल्यूड लॉजिक में "मोस्ट कॉम्प्लेक्स फोर-कलर्ड रेक्टेंगल-फ्री ग्रिड्स - एक ओपन मल्टीपल-वैल्यूड प्रॉब्लम का सॉल्यूशन" और स्टाइनबैक-पोस्टहॉफ एल्गोरिदम के परिणाम प्रकाशित किए जाएंगे। (कनाडा)।

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