చెల్లించలేని అతిపెద్ద మొత్తానికి, ఇప్పుడు కచ్చితమైన హద్దు

కొన్ని రకాల నాణేలను మాత్రమే స్వీకరించే, ఎప్పుడూ చిల్లర తిరిగి ఇవ్వని ఒక క్యాష్ కౌంటర్‌ను ఊహించుకోండి; ఆ నాణేలు అపరిమితంగా అందుబాటులో ఉంటాయి. కొన్ని మొత్తాలను కచ్చితంగా చెల్లించవచ్చు; మరికొన్నింటిని ఎప్పటికీ చెల్లించలేం. గణిత శాస్త్రవేత్తలు నాణేల విలువలను జనకాలు (generators) అంటారు, పైకి సరళంగా కనిపించే ఒక ప్రశ్న అడుగుతారు: చెల్లించలేని అతిపెద్ద మొత్తం ఏది?

ఎప్పటికీ చెల్లించలేని మొత్తాలు

a₁ < a₂ < … < aₙ అనే పూర్ణసంఖ్యలను తీసుకోండి; వాటన్నింటికీ ఉమ్మడిగా ఏ కారణాంకమూ ఉండకూడదు. ఈ సంఖ్యలను — ఒక్కోదాన్ని కావలసినన్నిసార్లు — కలపడం ద్వారా వచ్చే మొత్తం “సూచించదగినది” (representable). అలా సూచించలేని పూర్ణసంఖ్యలు పరిమిత సంఖ్యలోనే ఉంటాయి; వాటిలో అతిపెద్దది ఫ్రొబీనియస్ సంఖ్య F. (విలువల్లో ఒకటి 1 అయితే, ప్రతిదాన్నీ చెల్లించవచ్చు, అప్పుడు F = −1 గా నిర్ణయిస్తారు.)

ఒక చిన్న ఉదాహరణ: 3, 4, 6 నాణేలతో మీరు 3, 4, 6, 7, 8, ఆ తర్వాతి ప్రతి మొత్తాన్నీ చెల్లించవచ్చు, కానీ 1, 2, 5 లను ఎప్పటికీ చెల్లించలేరు. కాబట్టి F = 5. గమనించండి: 3, 6 లకు ఒక ఉమ్మడి కారణాంకం ఉంది; ముఖ్యమైనది ఏమిటంటే, మూడింటికీ ఉమ్మడిగా ఉండే కారణాంకం ఏదీ లేదు.

రెండు నాణేలకు కచ్చితమైన సమాధానం ఉంది, అది సిల్వెస్టర్ సూత్రం: F(a₁, a₂) = a₁a₂ − a₁ − a₂. మూడు లేదా అంతకంటే ఎక్కువ నాణేలకు, పని అంతా F కి హద్దు నిర్ణయించడమే: నాణేల నుంచి లెక్కించిన ఏదో ఒక విలువను F మించదని నిరూపించడం.

మొండిగా నిలిచిన 2 అనే గుణకం

పాల్ ఎర్డోష్, రోనాల్డ్ గ్రాహమ్ మూడు లేదా అంతకంటే ఎక్కువ జనకాలకు ఇలా నిరూపించారు:

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

ఇక్కడ aₙ అతిపెద్ద విలువ, aₙ₋₁ రెండో అతిపెద్ద విలువ, n విలువల సంఖ్య, ⌊ ⌋ అంటే క్రిందికి పూర్ణాంకానికి సవరించడం (rounding down). సిల్వెస్టర్ సూత్రంలాగే, ఇందులోనూ రెండు అతిపెద్ద నాణేలు ఉంటాయి.

వారు అత్యంత ప్రతికూల సందర్భాన్ని కూడా అంచనా వేశారు: n విలువలన్నీ గరిష్ఠంగా t ఉన్నప్పుడు సాధ్యమయ్యే అతిపెద్ద F. వారి అంచనాల మధ్య ఉన్న సుమారు 2 రెట్ల అంతరం ఒక ఊహకు (conjecture) దారితీసింది, అది ఎర్డోష్ సమస్య #433 గా నమోదైంది. జాక్ డిక్స్‌మియర్ దాన్ని పరిష్కరించారు, ప్రతి సమూహానికీ వర్తించే ఒక సరళమైన హద్దును కూడా నిరూపించారు: F ≤ aₙ²/(n − 1). 2 అనే గుణకం పోయింది, కానీ దానితో పాటు రెండో అతిపెద్ద నాణెం కూడా పోయింది.

రెండు అతిపెద్ద నాణేలనూ నిలుపుకోవడం

జెజియాంగ్ విశ్వవిద్యాలయపు కాలేజ్ ఆఫ్ కంప్యూటర్ సైన్స్ అండ్ టెక్నాలజీకి చెందిన లిన్ చెన్, టింగ్‌వెయ్ హు, యుచెన్ మావో, గ్వోచువాన్ ఝాంగ్ రెండూ కావాలనుకున్నారు: 2 అనే గుణకం ఉండకూడదు, రెండో అతిపెద్ద నాణెం నిలిచి ఉండాలి. రెండు లేదా అంతకంటే ఎక్కువ విలువలున్న ఏ సమూహానికైనా వర్తించే వారి సమాధానం:

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

ఇక్కడ ⌈ ⌉ అంటే పైకి పూర్ణాంకానికి సవరించడం (rounding up). ఎర్డోష్, గ్రాహమ్ హద్దుతో పోలిస్తే, 2 అనే గుణకం మాయమైంది; దానికి మూల్యంగా n కి బదులు n − 1 తో భాగించి, పైకి సవరించాల్సి వస్తుంది. డిక్స్‌మియర్ హద్దుతో పోలిస్తే, రెండో అతిపెద్ద నాణెం అతిపెద్ద నాణెంతో పోలిస్తే చిన్నదైనప్పుడు కొత్త హద్దు గణనీయంగా చిన్నదిగా ఉండగలదు.

3, 4, 6 ఉదాహరణలో, ఎర్డోష్, గ్రాహమ్ హద్దు 10 ఇస్తుంది, డిక్స్‌మియర్ హద్దు 18 ఇస్తుంది, కొత్తది 4 × 3 − 6 − 1 = 5 ఇస్తుంది — సరిగ్గా నిజమైన విలువ. ఇందులో ఆశ్చర్యం లేదు: ఈ సమూహం కింద వివరించిన తీవ్ర సందర్భాల కుటుంబానికి చెందినది, అవి హద్దును సరిగ్గా చేరేలా నిర్మించినవి; సాధారణ సమూహాలపై పత్రం ఎలాంటి పోలికనూ ఇవ్వదు.

శేషాల ఆధారంగా మొత్తాలను వర్గీకరించడం

నిరూపణ ఎర్డోష్, గ్రాహమ్ మార్గాన్నే అనుసరిస్తుంది. ప్రతి మొత్తాన్నీ అతిపెద్ద నాణెం aₙ తో భాగించినప్పుడు వచ్చే శేషం ఆధారంగా వర్గీకరించండి. చిన్న నాణేల మొత్తం ఏదైనా ఒక శేషాన్ని చేరిన తర్వాత, aₙ ప్రతులను కలుపుతూ పోతే అదే శేషం గల ప్రతి పెద్ద మొత్తాన్నీ చేరవచ్చు. ప్రతి శేషాన్నీ తక్కువ ఖర్చుతో చేరవచ్చని చూపడమే చేయవలసిన పని.

ముఖ్య సాధనం క్నీజర్ సిద్ధాంతం (Kneser’s theorem); మొత్తాల సమితి ఎంత పెద్దదిగా ఉండాలో అది చెబుతుంది. సుమారు aₙ/n నాణేల మొత్తాలు సగానికి పైగా శేషాలను కవర్ చేస్తాయని చూపడానికి ఎర్డోష్, గ్రాహమ్ దాన్ని ఉపయోగించారు, తర్వాత అన్నింటినీ కవర్ చేయడానికి రెట్టింపు చేశారు. ఈ మొత్తాల్లోని ప్రతి నాణెం విలువ గరిష్ఠంగా aₙ₋₁, కాబట్టి నాణేల సంఖ్యను రెట్టింపు చేస్తే ఖర్చూ రెట్టింపు అవుతుంది: 2 అనే గుణకం అక్కడి నుంచే వస్తుంది.

కొత్త నిరూపణ ⌈aₙ/(n − 1)⌉ నాణేల మొత్తాలను ఉపయోగిస్తుంది. ఈ మొత్తాలు కొన్ని శేషాలను చేరలేకపోయినప్పుడు, తప్పిపోయినవి యాదృచ్ఛికంగా చెల్లాచెదురుగా ఉండవని క్నీజర్ సిద్ధాంతం చెబుతుంది: అవి సమాన విరామాల్లో ఉండే శేషాల పూర్తి కుటుంబాలుగా ఏర్పడతాయి. ఎంత ఎక్కువ కుటుంబాలు తప్పిపోతే, చేరిన ప్రతి కుటుంబంలోకీ అంత ఎక్కువగా చిన్న నాణేలు కిక్కిరిసిపోవాలి; కాబట్టి ఆ ప్రతి కుటుంబంలోనూ కొన్ని చిన్న నాణేలు ఉంటాయి, తప్పిపోయిన కుటుంబాలను చేరడానికి కావలసిన ఆ కొద్ది అదనపు నాణేలు చవకగా ఉంటాయి. మొత్తం ఖర్చు ఎప్పుడూ ⌈aₙ/(n − 1)⌉ × aₙ₋₁ ను మించదు.

ఆ మొదటి అడుగు చివరి “− 1” లేకుండా హద్దును ఇస్తుంది. చివరి ఒక్క యూనిట్ వేరొక వాదన నుంచి వస్తుంది; అది ఒకే ఒక విధంగా మాత్రమే ఏర్పడగల మొత్తాల గురించిన షెర్క్, కెంపర్‌మాన్ సిద్ధాంతంపై ఆధారపడుతుంది: సరిహద్దు మొత్తమైన 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 అనే రెండు నాణేలలా ప్రవర్తిస్తుంది, సిల్వెస్టర్ సూత్రం ఇచ్చే F కొత్త హద్దుతో సరిగ్గా సరిపోతుంది. n = 3, q = 3 అయితే, ఈ పద్ధతి సరిగ్గా పైనున్న 3, 4, 6 ఉదాహరణనే ఇస్తుంది.

తక్కువ నాణేలు, తక్కువ పైకప్పు

ఈ హద్దును సాంద్రత (density) పరంగా కూడా చదవవచ్చు. అతిచిన్న i విలువలతో పాటు అతిపెద్ద విలువతో ఏర్పడిన ఏ కుదించిన సమూహానికైనా ఇది వర్తిస్తుంది — వాటికి ఇంకా ఉమ్మడి కారణాంకం లేనంత వరకు. నాణేలను తొలగిస్తే చెల్లించడం కష్టమవుతుందే తప్ప సులభం కాదు, కాబట్టి కుదించిన సమూహానికి నిరూపించిన పైకప్పు పూర్తి సమూహానికీ వర్తిస్తుంది. ఫలితాన్ని నియంత్రించేది సుమారుగా aᵢ/i — మొదటి i విలువలు 1 నుంచి aᵢ వరకు ఉన్న సంఖ్యలను ఎంత దట్టంగా నింపుతాయో దానికి విలోమం: అత్యంత దట్టమైన సమూహం గెలుస్తుంది. ముఖ్యంగా, మిగిలిన నాణేలన్నింటికీ ఉమ్మడిగా ఏ కారణాంకమూ లేనప్పుడల్లా రెండో అతిపెద్ద నాణేన్ని నేరుగా పక్కన పెట్టవచ్చని రచయితలు గమనించారు.

పత్రం పూర్తిగా సైద్ధాంతికంగానే ఉంటుంది: సాధారణ నాణేల సమూహాలపై కొత్త హద్దు ఎంత చిన్నదో అది ఏ సంఖ్యనూ ఇవ్వదు, దాని కచ్చితత్వం (sharpness) మూడు లేదా అంతకంటే ఎక్కువ నాణేల విలువలకు మాత్రమే నిరూపించబడింది.