ఒకదాన్నొకటి రద్దు చేసుకునే మొత్తాలపై 1969 నాటి ఒక పరికల్పన తప్పని తేలింది
ఆరు గంటలు గల ఒక గడియారాన్ని, కదలికల ఒక జాబితాను తీసుకోండి: “ముల్లును 1 గంట ముందుకు తిప్పు”, “4 గంటలు ముందుకు”, ఇలా. ఒక్కొక్కటి ఒక గంట గల ఐదు కదలికలతో, వాటిలో ఏ సమూహమూ ముల్లును సరిగ్గా మొదటి స్థానానికి ఎప్పుడూ తీసుకురాదు. ఆరు కదలికలతో, అవి ఏవైనా సరే, ఏదో ఒక సమూహం ఎప్పుడూ తీసుకొస్తుంది. గణిత శాస్త్రవేత్తలు ఈ గడియార అంకగణితాన్ని C₆ అని రాస్తారు, ఇక్కడ ఆరు అనే సంఖ్య ఆ గడియారపు డావెన్పోర్ట్ స్థిరాంకం (Davenport constant).
ఇప్పుడు అలాంటి r గడియారాలను పక్కపక్కనే పెట్టి, ప్రతి కదలిక ప్రతి ముల్లునూ దాని సొంత మొత్తంలో తిప్పేలా చేయండి. D(C₆^r) అని రాసే ఈ గడియారాల సమితి యొక్క డావెన్పోర్ట్ స్థిరాంకం అంటే, మొత్తం కలిపి ప్రతి ముల్లునూ ఒకేసారి మొదటి స్థానానికి తీసుకొచ్చే ఒక సమూహానికి హామీ ఇచ్చే కనిష్ఠ కదలికల సంఖ్య — పేపర్ మాటల్లో, ఒక సున్నా-మొత్తం (zero-sum) ఉపశ్రేణి. ఈ స్థిరాంకం గ్రాఫ్ సిద్ధాంతం, పరిమిత జ్యామితి, సంయోజన శాస్త్రం (combinatorics), కారణాంకీకరణ సిద్ధాంతం (factorization theory) లోని సమస్యలతో ముడిపడి ఉంది.
1969 నాటి ఒక సూత్రం
ఒక సులభమైన దిగువ హద్దు (lower bound) ఉంది. ప్రతి గడియారంపై, ఆ గడియారాన్ని మాత్రమే తాకే, ఒక్కొక్కటి ఒక గంట గల ఐదు కదలికలను తీసుకోండి: r గడియారాలతో, అది 5r కదలికలు అవుతుంది, వాటిలో ఏ సమూహమూ రద్దు కాదు. కాబట్టి కనీసం 5r + 1 కదలికలు అవసరం. సాధారణంగా, n గంటలు గల గడియారాలకు, కనీసం r(n − 1) + 1.
1969లో, వాన్ ఎమ్డె బోయాస్ (van Emde Boas), క్రాయిస్వైక్ (Kruyswijk) ఈ సులభమైన హద్దే ఎప్పుడూ ఖచ్చితమైన సమాధానం అని ఊహించారు (conjectured):
D(C_n^r) = r(n − 1) + 1.
గంటల సంఖ్య ఒక ప్రధాన సంఖ్య యొక్క ఘాతం (power of a prime) అయిన గడియారాలు, లేదా గరిష్ఠంగా రెండు గడియారాలు వంటి కొన్ని సందర్భాలకు 1960లలో ఇది నిరూపించబడింది. అంతకు మించి, ఖచ్చితమైన విలువ అందకుండానే ఉండిపోయింది: 2018 నాటికి కూడా, నాలుగు ఆరు-గంటల గడియారాల సందర్భం కూడా తెలియలేదు. అయినప్పటికీ, ఈ పరికల్పన ఆ రంగంలో “ఒక ప్రముఖ దీర్ఘకాల సమస్య”గా మారింది, అది నిజమవుతుందని అందరూ ఆశించారు.
ఎప్పటికీ రద్దు కాని 116 కదలికలు
టియాంజిన్ విశ్వవిద్యాలయం (Tianjin University)కు చెందిన వీడాంగ్ గావో (Weidong Gao), గ్రాజ్ విశ్వవిద్యాలయం (University of Graz)కు చెందిన ఆల్ఫ్రెడ్ గెరోల్డింగర్ (Alfred Geroldinger), టియాంగాంగ్ విశ్వవిద్యాలయం (Tiangong University)కు చెందిన గువోచింగ్ వాంగ్ (Guoqing Wang), సన్ యాట్-సెన్ విశ్వవిద్యాలయం (Sun Yat-Sen University)కు చెందిన షియాంగ్నెంగ్ జెంగ్ (Xiangneng Zeng) అది విఫలమవుతుందని ఇప్పుడు చూపిస్తున్నారు.
బృందం కదలికలను నిర్మాణ దిమ్మెల్లా కూర్చుతుంది:
- ఒక చిన్న పట్టిక నుంచి నిర్మించిన, ఐదు ఆరు-గంటల గడియారాలపై 24 కదలికల ఒక జాబితా: వాటిలో ఏ సమూహపు మొత్తమైనా మూడు స్థానాల ఒక చిన్న సమితిలో పడితే, అది ఎప్పుడూ అదే సున్నా-కాని స్థానంలోనే పడుతుంది;
- ఆ మూడు స్థానాలను పంచుకునే అలాంటి రెండు జాబితాలు, ఇవి రద్దయ్యే సమూహమేదీ లేని 48 కదలికలను ఇస్తాయి;
- రద్దయ్యే సమూహమేదీ ఇందులోనూ లేని 20 కదలికల ఒక వేరే జాబితా.
పక్కపక్కనే ఉంచితే, ఇవి 23 ఆరు-గంటల గడియారాలపై 2 × 48 + 20 = 116 కదలికలను ఇస్తాయి, వాటిలో ఏ సమూహమూ ప్రతి ముల్లునూ మొదటి స్థానానికి తీసుకురాదు. సాధ్యమైన అలాంటి అతి పొడవైన జాబితా 23 × 5 = 115 అని పరికల్పన చెప్పింది. కాబట్టి 23 గడియారాలకు, డావెన్పోర్ట్ స్థిరాంకం 116 కాదు, కనీసం 117.
ఈ దిమ్మె ప్రతులను ఒకదానిపై ఒకటి పేర్చవచ్చు: సాధారణ ఫలితం D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1, ఇక్కడ ⌊r/23⌋ అనేది 23 చొప్పున ఎన్ని పూర్తి దిమ్మెలు r లో ఇముడుతాయో లెక్కిస్తుంది. కాబట్టి ఆరు-గంటల గడియారాలకు ఈ పరికల్పన r 23 కి చేరిన వెంటనే తప్పు అవుతుంది, అంతకంటే పెద్ద ప్రతి r కి కూడా. అదే సిద్ధాంతం ఆచ్ఛాదనలపై (coverings) ఊహించిన ఒక ఫలితాన్ని కూడా తప్పని నిరూపిస్తుందని రచయితలు పేర్కొంటున్నారు.
ఇంకా తేలనిది
ఈ నిరూపణ D(C₆^r) యొక్క అసలు విలువను ఇవ్వదు, పరికల్పన నిషేధించే ఒక హద్దును మాత్రమే ఇస్తుంది. 23 కంటే తక్కువ గడియారాలకు — అక్కడ కొత్త హద్దు పాత సూత్రానికి సమానం — అది కొత్తగా ఏమీ చెప్పదు, ఆరు కాకుండా వేరే గంటల సంఖ్య గల గడియారాలకు కూడా ఏమీ చెప్పదు. నోట్ ఐదు పేజీల నిడివి గలది, సహచర సమీక్ష (peer review) ఇంకా జరగాల్సి ఉంది.
