जी रक्कम चुकती करता येत नाही त्यातील सर्वात मोठी, आता घट्ट मर्यादेत

अशा एका गल्ल्याची कल्पना करा जो फक्त काही प्रकारची नाणी, अमर्याद पुरवठ्यात, स्वीकारतो आणि कधीच सुटे पैसे परत देत नाही. काही रकमा अचूक चुकत्या करता येतात; इतर कधीच करता येत नाहीत. गणितज्ञ नाण्यांच्या किमतींना जनक (generators) म्हणतात, आणि फसवा वाटावा इतका साधा प्रश्न विचारतात: चुकती करता न येणारी सर्वात मोठी रक्कम कोणती?

कधीच चुकत्या करता न येणाऱ्या रकमा

a₁ < a₂ < … < aₙ अशा पूर्ण संख्या घ्या, ज्या सर्वांमध्ये कोणताही सामायिक अवयव नाही. या संख्या, प्रत्येकी हव्या तितक्या वेळा, बेरीज करून मिळणारी एकूण रक्कम “मांडता येण्याजोगी” (representable) असते. फक्त मर्यादित संख्येच्या पूर्ण संख्या तशा नसतात; त्यांपैकी सर्वात मोठी म्हणजे फ्रोबेनियस संख्या, F. (किमतींपैकी एक 1 असेल, तर सर्व काही चुकते करता येते आणि F = −1 ठरवले जाते.)

एक लहान उदाहरण: 3, 4 आणि 6 च्या नाण्यांनी तुम्ही 3, 4, 6, 7, 8 आणि त्यानंतरची प्रत्येक रक्कम चुकती करू शकता, पण 1, 2 किंवा 5 कधीच नाही. म्हणून F = 5. लक्षात घ्या की 3 आणि 6 मध्ये एक सामायिक अवयव आहे; महत्त्वाचे हे आहे की तिन्हींमध्ये सामायिक असा कोणताही अवयव नाही.

दोन नाण्यांसाठी एक अचूक उत्तर आहे, Sylvester यांचे सूत्र: F(a₁, a₂) = a₁a₂ − a₁ − a₂. तीन किंवा अधिक नाण्यांसाठी, काम म्हणजे F ला मर्यादा घालणे: नाण्यांवरून काढलेल्या एखाद्या किमतीपेक्षा ते जास्त असू शकत नाही हे सिद्ध करणे.

2 चा एक हट्टी गुणक

Paul Erdős आणि Ronald Graham यांनी, तीन किंवा अधिक जनकांसाठी, सिद्ध केले:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

इथे aₙ ही सर्वात मोठी किंमत, aₙ₋₁ दुसरी सर्वात मोठी, n किमतींची संख्या, आणि ⌊ ⌋ म्हणजे खालच्या पूर्णांकाकडे पूर्णांकन. Sylvester यांच्या सूत्राप्रमाणेच, यात दोन सर्वात मोठी नाणी येतात.

त्यांनी सर्वात वाईट स्थितीचाही अंदाज बांधला, म्हणजे सर्व n किमती जास्तीत जास्त t असताना शक्य असलेले सर्वात मोठे F. त्यांच्या अंदाजांमधील अंतर, साधारण 2 च्या गुणकाचे, यातून एक अटकळ (conjecture) जन्मली, जी Erdős Problem #433 म्हणून नोंदवली गेली. Jacques Dixmier यांनी ती सोडवली, आणि प्रत्येक संचासाठी लागू होणारी एक अधिक साधी मर्यादाही सिद्ध केली: F ≤ aₙ²/(n − 1). 2 चा गुणक गेला, पण दुसरे सर्वात मोठे नाणेही गेले.

दोन्ही सर्वात मोठी नाणी राखून

झेजियांग विद्यापीठाच्या कॉलेज ऑफ कॉम्प्युटर सायन्स अँड टेक्नॉलॉजीमधील Lin Chen, Tingwei Hu, Yuchen Mao आणि Guochuan Zhang यांना दोन्ही हवे होते: 2 चा गुणक नको, आणि दुसरे सर्वात मोठे नाणे राखलेले. दोन किंवा अधिक किमतींच्या कोणत्याही संचासाठी लागू होणारे त्यांचे उत्तर:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

इथे ⌈ ⌉ म्हणजे वरच्या पूर्णांकाकडे पूर्णांकन. Erdős आणि Graham यांच्याशी तुलना करता, 2 चा गुणक नाहीसा झाला आहे, मात्र त्याची किंमत म्हणून n ऐवजी n − 1 ने भागावे लागते आणि वरच्या पूर्णांकाकडे पूर्णांकन करावे लागते. Dixmier यांच्याशी तुलना करता, दुसरे सर्वात मोठे नाणे सर्वात मोठ्याच्या तुलनेत लहान असते तेव्हा नवी मर्यादा लक्षणीयरीत्या लहान असू शकते.

3, 4, 6 या उदाहरणावर, Erdős आणि Graham यांची मर्यादा 10 देते, Dixmier यांची 18 देते, आणि नवी मर्यादा 4 × 3 − 6 − 1 = 5 देते, नेमके खरे मूल्य. यात आश्चर्य नाही: हा संच खाली वर्णन केलेल्या टोकाच्या उदाहरणांच्या कुटुंबातील आहे, जे नेमके मर्यादेपर्यंत पोहोचण्यासाठीच रचलेले आहेत; शोधनिबंध नेहमीच्या संचांवर कोणतीही तुलना देत नाही.

रकमांची शेषानुसार वर्गवारी

सिद्धता Erdős आणि Graham यांच्या मार्गाने जाते. प्रत्येक रकमेची वर्गवारी सर्वात मोठ्या नाण्याने, aₙ ने, भागल्यावर उरणाऱ्या शेषानुसार करा. लहान नाण्यांची एखादी बेरीज दिलेल्या शेषापर्यंत पोहोचली की, aₙ च्या प्रती जोडून त्याच शेषाची प्रत्येक मोठी रक्कम गाठता येते. काम असे दाखवण्याचे आहे की प्रत्येक शेष स्वस्तात गाठता येतो.

मुख्य साधन म्हणजे Kneser यांचे प्रमेय, बेरजांचा संच किती मोठा असलाच पाहिजे याबद्दलचे. Erdős आणि Graham यांनी त्याचा वापर करून दाखवले की सुमारे aₙ/n नाण्यांच्या बेरजा अर्ध्याहून अधिक शेष व्यापतात, आणि मग सर्व व्यापण्यासाठी ते दुप्पट केले. या बेरजांमधील प्रत्येक नाण्याची किंमत जास्तीत जास्त aₙ₋₁ असते, त्यामुळे नाण्यांची संख्या दुप्पट केल्याने खर्च दुप्पट होतो: म्हणून 2 चा गुणक.

नवी सिद्धता ⌈aₙ/(n − 1)⌉ नाण्यांच्या बेरजा वापरते. या बेरजांतून काही शेष सुटतात, तेव्हा Kneser यांचे प्रमेय सांगते की सुटलेले शेष यादृच्छिकपणे विखुरलेले नसतात: ते नियमित अंतराने मांडलेल्या शेषांची संपूर्ण कुटुंबे बनवतात. जितकी अधिक कुटुंबे सुटतात, तितकी अधिक लहान नाणी गाठलेल्या प्रत्येक कुटुंबात दाटीवाटीने बसावी लागतात, त्यामुळे अशा प्रत्येक कुटुंबात काही लहान नाणी असतात, आणि सुटलेल्या कुटुंबांपर्यंत पोहोचण्यासाठी लागणारी मोजकी जादा नाणी स्वस्त पडतात. एकूण खर्च कधीच ⌈aₙ/(n − 1)⌉ × aₙ₋₁ पेक्षा जास्त होत नाही.

ती पहिली पायरी शेवटच्या “− 1” शिवायची मर्यादा देते. शेवटचे एकक एका स्वतंत्र युक्तिवादातून येते, जो फक्त एकाच प्रकारे बनवता येणाऱ्या बेरजांबद्दलच्या Scherk आणि Kemperman यांच्या एका प्रमेयावर आधारित आहे: तो दाखवतो की सीमेवरची रक्कम aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ स्वतः नेहमीच चुकती करता येते. ऋणनिर्देशानुसार, लेखकांनी आधी कमजोर मर्यादा सिद्ध केली; मग GPT-6 ने ती एकाने खाली आणणारा युक्तिवाद शोधायला मदत केली, आणि मर्यादा आणखी खाली आणता येत नाही या सिद्धतेत तसेच इंग्रजीच्या संपादनातही साहाय्य केले. अंतिम हस्तलिखिताची जबाबदारी आपण घेतो, असे लेखक नमूद करतात.

नेमके मर्यादेवर आदळणारी उदाहरणे

ही मर्यादा खाली आणता येत नाही: प्रत्येक n ≥ 3 साठी, लेखक असे अनंत संच तयार करतात जिथे F नेमके तिच्याइतके असते. कोणताही q ≥ 2 घ्या आणि q, 2q, …, (n − 1)q या किमती, अधिक (n − 2)q + 1. एक सोडून सर्व q च्या पटी आहेत, त्यामुळे केवळ q जे चुकते करू शकत नाही असे काहीच ते चुकते करत नाहीत. हा संच q आणि (n − 2)q + 1 या दोन नाण्यांसारखा वागतो, आणि Sylvester यांचे सूत्र असे F देते जे नव्या मर्यादेशी नेमके जुळते. n = 3 आणि q = 3 घेतल्यास, ही कृती नेमके वरचे 3, 4, 6 उदाहरण तयार करते.

कमी नाणी, खालचे छत

ही मर्यादा घनतेच्या भाषेतही वाचता येते. ती i सर्वात लहान किमती अधिक सर्वात मोठी किंमत यांनी बनलेल्या कोणत्याही कमी केलेल्या संचाला लागू होते, जोपर्यंत त्यांच्यात अजूनही कोणताही सामायिक अवयव नाही. नाणी काढून टाकल्याने रक्कम चुकती करणे फक्त अधिक कठीणच होऊ शकते, त्यामुळे कमी केलेल्या संचासाठी सिद्ध झालेले छत पूर्ण संचालाही लागू होते. निकाल ठरवणारी गोष्ट साधारण aᵢ/i असते, म्हणजे पहिल्या i किमती 1 ते aᵢ पर्यंतच्या संख्या किती दाटपणे भरतात याचा व्यस्त: सर्वात दाट गट जिंकतो. विशेषतः, लेखक नोंदवतात की उरलेल्या नाण्यांत अजूनही सर्वांमध्ये सामायिक असा कोणताही अवयव नसेल, तेव्हा दुसरे सर्वात मोठे नाणे सरळ बाजूला ठेवता येते.

शोधनिबंध पूर्णपणे सैद्धांतिकच राहतो: नेहमीच्या नाण्यांच्या संचांवर नवी मर्यादा किती लहान आहे याचा कोणताही आकडा तो देत नाही, आणि तिचा नेमकेपणा केवळ तीन किंवा अधिक नाण्यांच्या किमतींसाठीच सिद्ध झाली आहे.