बूलियन पायथागॉरियन ट्रिपल समस्या: Difference between revisions
From Vigyanwiki
(Created page with "{{short description|Can one split the integers into two sets such that every Pythagorean triple spans both?}} बूलियन पायथागॉरियन ट्र...") |
No edit summary |
||
| (8 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Can one split the integers into two sets such that every Pythagorean triple spans both?}} | {{short description|Can one split the integers into two sets such that every Pythagorean triple spans both?}} | ||
बूलियन [[पायथागॉरियन ट्रिपल]] समस्या [[रैमसे सिद्धांत]] से एक समस्या है कि क्या [[प्राकृतिक संख्या]] को लाल और नीले रंग में रंगा जा सकता है | बूलियन [[पायथागॉरियन ट्रिपल]] समस्या [[रैमसे सिद्धांत]] से एक समस्या है कि क्या [[प्राकृतिक संख्या]] को लाल और नीले रंग में रंगा जा सकता है जिससे कोई पायथागॉरियन ट्रिपल में सभी लाल या सभी नीले सदस्य न हों। मई 2016 में एक कंप्यूटर-सहायता प्रमाण के माध्यम से बूलियन पायथागॉरियन ट्रिपल्स समस्या को [[मैरी ह्यूले]], ओलिवर कुल्मन और विक्टर डब्ल्यू मारेक द्वारा समाधान किया गया था।<ref name="nature">{{Cite journal|last=Lamb|first=Evelyn|date=26 May 2016|title=दो सौ टेराबाइट मैथ्स प्रूफ अब तक का सबसे बड़ा है|journal=Nature|doi=10.1038/nature.2016.19990|volume=534|issue=7605 |pages=17–18|pmid=27251254|bibcode=2016Natur.534...17L|doi-access=free}}</ref> | ||
== कथन == | == कथन == | ||
समस्या पूछती है कि क्या प्रत्येक | समस्या पूछती है कि क्या प्रत्येक धनात्मक पूर्णांक को लाल या नीले रंग में रंगना संभव है, जिससे पूर्णांक a, b, c का कोई पायथागॉरियन ट्रिपल संतोषजनक न हो <math>a^2+b^2=c^2</math> सब एक ही रंग के हैं। | ||
उदाहरण के लिए, पायथागॉरियन ट्रिपल 3, 4 और 5 में (<math>3^2+4^2=5^2</math>), यदि 3 और 4 को लाल रंग से रंगा गया है, तो 5 को नीले रंग से अवश्य रंगा जाना चाहिए। | उदाहरण के लिए, पायथागॉरियन ट्रिपल 3, 4 और 5 में (<math>3^2+4^2=5^2</math>), यदि 3 और 4 को लाल रंग से रंगा गया है, तो 5 को नीले रंग से अवश्य रंगा जाना चाहिए। | ||
| Line 10: | Line 10: | ||
== समाधान == | == समाधान == | ||
मेरिजन ह्यूले, ओलिवर कुलमैन और विक्टर डब्ल्यू मारेक ने दिखाया कि ऐसा रंग केवल 7824 संख्या तक ही संभव है। प्रमेय का वास्तविक कथन सिद्ध हुआ है | मेरिजन ह्यूले, ओलिवर कुलमैन और विक्टर डब्ल्यू मारेक ने दिखाया कि ऐसा रंग केवल 7824 संख्या तक ही संभव है। प्रमेय का वास्तविक कथन सिद्ध हुआ है | ||
{{math theorem| | {{math theorem|समुच्चय {1, . . . , 7824} को दो भागों में विभाजित किया जा सकता है, जैसे कि किसी भी भाग में पायथागॉरियन ट्रिपल नहीं है, जबकि यह {1, . . . , 7825} के लिए असंभव है।<ref name="arXiv"/> | ||
}} | }} | ||
[[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]] | |||
== पुरस्कार == | == पुरस्कार == | ||
1980 के दशक में [[रोनाल्ड ग्राहम]] ने समस्या के समाधान के लिए $100 के पुरस्कार की | 1980 के दशक में [[रोनाल्ड ग्राहम]] ने समस्या के समाधान के लिए $100 के पुरस्कार की प्रस्तुति की थी, जिसे अब मरिजन ह्यूले को प्रदान किया गया है।<ref name="nature"/> | ||
== सामान्यीकरण == | == सामान्यीकरण == | ||
2018 तक, समस्या अभी भी 2 से अधिक रंगों के लिए खुली है, अर्थात, यदि धनात्मक पूर्णांकों का k-रंग (k ≥ 3) | 2018 तक, समस्या अभी भी 2 से अधिक रंगों के लिए खुली है, अर्थात, यदि धनात्मक पूर्णांकों का k-रंग (k ≥ 3) उपस्थित है, जैसे कि कोई पाइथागोरस ट्रिपल समान रंग नहीं है।<ref>{{Cite journal|last1=Eliahou|first1=Shalom|last2=Fromentin|first2=Jean|last3=Marion-Poty|first3=Virginie|last4=Robilliard|first4=Denis|date=2018-10-02|title=Are Monochromatic Pythagorean Triples Unavoidable under Morphic Colorings?|url=https://www.tandfonline.com/doi/full/10.1080/10586458.2017.1306465|journal=Experimental Mathematics|language=en|volume=27|issue=4|pages=419–425|doi=10.1080/10586458.2017.1306465|issn=1058-6458|arxiv=1605.00859|s2cid=19035265 }}</ref> | ||
| Line 31: | Line 42: | ||
== संदर्भ == | == संदर्भ == | ||
<references /> | <references /> | ||
[[Category: | [[Category:CS1 English-language sources (en)]] | ||
[[Category:Created On 17/03/2023]] | [[Category:Created On 17/03/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors|Short description/doc]] | |||
[[Category:Short description with empty Wikidata description]] | |||
[[Category:Template documentation pages|Short description/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:कंप्यूटर-सहायता प्राप्त प्रमाण]] | |||
[[Category:गणितीय समस्याएं]] | |||
[[Category:पाइथागोरस प्रमेय]] | |||
[[Category:रैमसे सिद्धांत]] | |||
Latest revision as of 11:27, 18 April 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.
