बूलियन पायथागॉरियन ट्रिपल समस्या: Difference between revisions
No edit summary |
No edit summary |
||
| Line 15: | Line 15: | ||
[[7825 (संख्या)]] तक की संख्याओं के लिए {{nowrap|2<sup>7825</sup> ≈ 3.63×10<sup>2355</sup>}} संभावित रंग संयोजन हैं। इन संभावित रंगों को तार्किक और एल्गोरिदमिक रूप से लगभग एक ट्रिलियन (अभी भी अत्यधिक जटिल) स्थितियों तक सीमित कर दिया गया था, और [[बूलियन संतुष्टि]] समाधान का उपयोग करके उनकी जांच की गई थी। प्रमाण बनाने में [[टेक्सास एडवांस्ड कंप्यूटिंग सेंटर]] में स्टैम्पेड सुपरकंप्यूटर पर दो दिनों की अवधि में लगभग 4 सीपीयू-वर्ष की गणना हुई और एक 200 टेराबाइट प्रस्तावात्मक प्रमाण उत्पन्न हुआ, जिसे 68 गीगाबाइट तक संकुचित किया गया था। | [[7825 (संख्या)]] तक की संख्याओं के लिए {{nowrap|2<sup>7825</sup> ≈ 3.63×10<sup>2355</sup>}} संभावित रंग संयोजन हैं। इन संभावित रंगों को तार्किक और एल्गोरिदमिक रूप से लगभग एक ट्रिलियन (अभी भी अत्यधिक जटिल) स्थितियों तक सीमित कर दिया गया था, और [[बूलियन संतुष्टि]] समाधान का उपयोग करके उनकी जांच की गई थी। प्रमाण बनाने में [[टेक्सास एडवांस्ड कंप्यूटिंग सेंटर]] में स्टैम्पेड सुपरकंप्यूटर पर दो दिनों की अवधि में लगभग 4 सीपीयू-वर्ष की गणना हुई और एक 200 टेराबाइट प्रस्तावात्मक प्रमाण उत्पन्न हुआ, जिसे 68 गीगाबाइट तक संकुचित किया गया था। | ||
प्रमाण का वर्णन करने वाला पेपर एसएटी 2016 सम्मेलन में प्रकाशित हुआ था,<ref name="arXiv">{{Cite conference|last1=Heule|first1=Marijn J. H.|last2=Kullmann|first2=Oliver|last3=Marek|first3=Victor W.|author3-link=Victor W. Marek|year=2016|contribution=Solving and Verifying the Boolean Pythagorean Triples problem via Cube-and-Conquer |arxiv=1605.00723|doi=10.1007/978-3-319-40970-2_15|series=Lecture Notes in Computer Science|volume=9710|pages=228–245|title=Theory and Applications of Satisfiability Testing – SAT 2016: 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings|editor1-first=Nadia|editor1-last=Creignou|editor2-first=Daniel|editor2-last=Le Berre}}</ref> जहां इसने सर्वश्रेष्ठ पेपर का पुरस्कार जीता था।<ref>[http://sat2016.labri.fr/ SAT 2016]</ref> नीचे दिया गया आंकड़ा समूह {1,...,7824} के लिए रंगों के एक संभावित परिवार को दिखाता है जिसमें कोई मोनोक्रोमैटिक पायथागॉरियन ट्रिपल नहीं है, और सफेद वर्गों को इस स्थिति को संतुष्ट करते हुए या तो लाल या नीला रंग दिया जा सकता है। | |||
प्रमाण का वर्णन करने वाला पेपर | |||
[[File:Ptn-7824-zoom-2.png|alt=|center|400x400px]] | [[File:Ptn-7824-zoom-2.png|alt=|center|400x400px]] | ||
Revision as of 06:23, 24 March 2023
बूलियन पायथागॉरियन ट्रिपल समस्या रैमसे सिद्धांत से एक समस्या है कि क्या प्राकृतिक संख्या को लाल और नीले रंग में रंगा जा सकता है जिससे कोई पायथागॉरियन ट्रिपल में सभी लाल या सभी नीले सदस्य न हों। मई 2016 में एक कंप्यूटर-सहायता प्रमाण के माध्यम से बूलियन पायथागॉरियन ट्रिपल्स समस्या को मैरी ह्यूले, ओलिवर कुल्मन और विक्टर डब्ल्यू मारेक द्वारा समाधान किया गया था।[1]
कथन
समस्या पूछती है कि क्या प्रत्येक धनात्मक पूर्णांक को लाल या नीले रंग में रंगना संभव है, जिससे पूर्णांक a, b, c का कोई पायथागॉरियन ट्रिपल संतोषजनक न हो सब एक ही रंग के हैं।
उदाहरण के लिए, पायथागॉरियन ट्रिपल 3, 4 और 5 में (), यदि 3 और 4 को लाल रंग से रंगा गया है, तो 5 को नीले रंग से अवश्य रंगा जाना चाहिए।
समाधान
मेरिजन ह्यूले, ओलिवर कुलमैन और विक्टर डब्ल्यू मारेक ने दिखाया कि ऐसा रंग केवल 7824 संख्या तक ही संभव है। प्रमेय का वास्तविक कथन सिद्ध हुआ है
Theorem — समुच्चय {1, . . . , 7824} को दो भागों में विभाजित किया जा सकता है, जैसे कि किसी भी भाग में पायथागॉरियन ट्रिपल नहीं है, जबकि यह {1, . . . , 7825} के लिए असंभव है।[2]
7825 (संख्या) तक की संख्याओं के लिए 27825 ≈ 3.63×102355 संभावित रंग संयोजन हैं। इन संभावित रंगों को तार्किक और एल्गोरिदमिक रूप से लगभग एक ट्रिलियन (अभी भी अत्यधिक जटिल) स्थितियों तक सीमित कर दिया गया था, और बूलियन संतुष्टि समाधान का उपयोग करके उनकी जांच की गई थी। प्रमाण बनाने में टेक्सास एडवांस्ड कंप्यूटिंग सेंटर में स्टैम्पेड सुपरकंप्यूटर पर दो दिनों की अवधि में लगभग 4 सीपीयू-वर्ष की गणना हुई और एक 200 टेराबाइट प्रस्तावात्मक प्रमाण उत्पन्न हुआ, जिसे 68 गीगाबाइट तक संकुचित किया गया था।
प्रमाण का वर्णन करने वाला पेपर एसएटी 2016 सम्मेलन में प्रकाशित हुआ था,[2] जहां इसने सर्वश्रेष्ठ पेपर का पुरस्कार जीता था।[3] नीचे दिया गया आंकड़ा समूह {1,...,7824} के लिए रंगों के एक संभावित परिवार को दिखाता है जिसमें कोई मोनोक्रोमैटिक पायथागॉरियन ट्रिपल नहीं है, और सफेद वर्गों को इस स्थिति को संतुष्ट करते हुए या तो लाल या नीला रंग दिया जा सकता है।
पुरस्कार
1980 के दशक में रोनाल्ड ग्राहम ने समस्या के समाधान के लिए $100 के पुरस्कार की प्रस्तुति की थी, जिसे अब मरिजन ह्यूले को प्रदान किया गया है।[1]
सामान्यीकरण
2018 तक, समस्या अभी भी 2 से अधिक रंगों के लिए खुली है, अर्थात, यदि धनात्मक पूर्णांकों का k-रंग (k ≥ 3) उपस्थित है, जैसे कि कोई पाइथागोरस ट्रिपल समान रंग नहीं है।[4]
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 Lamb, Evelyn (26 May 2016). "दो सौ टेराबाइट मैथ्स प्रूफ अब तक का सबसे बड़ा है". Nature. 534 (7605): 17–18. Bibcode:2016Natur.534...17L. doi:10.1038/nature.2016.19990. PMID 27251254.
- ↑ 2.0 2.1 Heule, Marijn J. H.; Kullmann, Oliver; Marek, Victor W. (2016). "Solving and Verifying the Boolean Pythagorean Triples problem via Cube-and-Conquer". In Creignou, Nadia; Le Berre, Daniel (eds.). Theory and Applications of Satisfiability Testing – SAT 2016: 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings. Lecture Notes in Computer Science. Vol. 9710. pp. 228–245. arXiv:1605.00723. doi:10.1007/978-3-319-40970-2_15.
- ↑ SAT 2016
- ↑ Eliahou, Shalom; Fromentin, Jean; Marion-Poty, Virginie; Robilliard, Denis (2018-10-02). "Are Monochromatic Pythagorean Triples Unavoidable under Morphic Colorings?". Experimental Mathematics (in English). 27 (4): 419–425. arXiv:1605.00859. doi:10.1080/10586458.2017.1306465. ISSN 1058-6458. S2CID 19035265.
