UNGANISHA KILA NUKTA NA KILA NYINGINE: MIKATIZO MICHACHE ZAIDI, IMETHIBITISHWA

Weka nukta tano kwenye karatasi na uunganishe kila jozi kwa mkunjo (mstari unaoweza kupinda): mikunjo kumi kwa jumla. Inaweza kupinda upendavyo, lakini hakuna mkunjo unaoruhusiwa kupita kwenye nukta ya tatu. Jaribu kuepuka kila mkatizo, na utashindwa. Kwa nukta tano, angalau mkatizo 1 hauepukiki; kwa sita, angalau 3; kwa kumi, angalau 60.

Wanahisabati huita picha kama hiyo mchoro wa grafu kamili Kₙ — pointi n, kila jozi ikiunganishwa — na idadi ndogo kabisa ya mikatizo ambayo mchoro wowote unaweza kufikia huitwa idadi yake ya mikatizo (crossing number). Martin Balko, wa Chuo Kikuu cha Charles katika Jamhuri ya Czech, analiita swali hili “mojawapo ya matatizo maarufu zaidi katika nadharia ya grafu ya kitopolojia”.

Hesabu ya msanii

Mwishoni mwa miaka ya 1950, msanii Mwingereza Anthony Hill alitengeneza michoro ya Kₙ yenye hasa

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

mikatizo, ambapo ⌊ ⌋ inamaanisha kukadiria kwenda chini hadi namba kamili. Dhana kwamba hakuna mchoro unaoweza kufanya vizuri zaidi ilichapishwa kwanza na Guy, baadaye ikajadiliwa na Harary na Hill, na ikafanywa maarufu na Erdős na Guy. Inajulikana kama dhana ya Harary–Hill (Harary–Hill conjecture), au dhana ya Guy.

Fomula hii hupanda haraka:

nukta 4 au chache zaidi: mikatizo 0
nukta 5: 1
nukta 7: 9
nukta 10: 60
nukta 14: 315

Miongo sita ya majibu ya sehemu

Michoro yenye mikatizo Z(n) hasa ilikuwepo kwa kila idadi ya nukta; sehemu ngumu ilikuwa kuonyesha kwamba hakuna mchoro unaofanya vizuri zaidi.

Kwa zaidi ya miaka sitini, hilo lilithibitishwa tu kwa aina maalum za michoro — kwa mfano nukta zote zikiwa kwenye mstari mmoja ulionyooka na kila mkunjo ukibaki upande mmoja wa mstari huo, au nukta zikiwa kwenye tufe na kila mkunjo ukifuata njia fupi zaidi. Balko mwenyewe, pamoja na Fulek na Kynčl, alikuwa ametatua aina moja kama hiyo. Kufikia 2021, kompyuta zilikuwa zimethibitisha fomula hadi nukta 14. Kwa idadi kubwa sana za nukta, matokeo bora ya jumla yalihakikisha angalau 98.5%, kisha 98.99%, ya Z(n).

Uthibitisho, kisha ulio wazi zaidi

Mwaka 2026, OpenAI ilitangaza uthibitisho kwa kila idadi ya nukta, ambao makala ya Balko inauorodhesha kama “OpenAI Math Release preprint” na kuupa sifa ya teorema hiyo. Makala haisemi jinsi uthibitisho huo ulivyopatikana. Kwa maneno ya Balko, uthibitisho wa awali “ni mfupi kiasi”, lakini “ni mgumu kabisa kufuatilia”. Makala yake ya awali (preprint) inawasilisha toleo lililorahisishwa ambalo, anaandika, “linahitaji tu maarifa ya msingi ya aljebra ya mstari na nadharia ya grafu”. Mwanahisabati mwingine, Gelasio Salazar, anaandaa maelezo tofauti, ya kina.

Kuhesabu vigawo badala ya mikatizo

Kwa kuwa michoro inayojulikana tayari inafikia Z(n), ni kikomo cha chini tu kinachohitaji uthibitisho. Kinahitaji hatua nne.

Namba witiri zinatosha. Mchoro bora unaweza kuchorwa upya ili mikunjo inayoshiriki nukta isikatizane kamwe; kila mkatizo basi unahusisha nukta 4 tofauti. Futa kila moja ya nukta 6 kwa zamu: kila picha ya nukta 5 inayobaki ina angalau mkatizo 1, na kila mkatizo unanusurika katika ufutaji 2 hasa kati ya 6 (hutoweka kila mara moja ya nukta zake 4 inapofutwa, na hunusurika ufutaji 2 uliobaki). Kwa hiyo mara mbili ya idadi ya mikatizo ni angalau 6: yaani angalau 3, ambayo ni Z(6). Hesabu hiyohiyo inafanya kazi kwa kila namba shufwa.
Familia ya polinomia. Ipe kila nukta namba yake. Mkatizo unahusisha mikunjo miwili, hivyo nukta nne, hivyo namba nne. Balko anatumia polinomia za vigeu vinne, zilizochaguliwa ili familia iwe na hasa vigawo Z(n) huru wakati n ni witiri — kwa nukta 7, 3 × 3 = 9.
Mikatizo michache mno huacha nafasi. Kutaka polinomia iwe sifuri kwenye mkatizo ni mlinganyo mmoja. Ukiwa na milinganyo michache kuliko vigawo huru, aljebra ya mstari daima huacha suluhisho lisilo sifuri. Kwa hiyo mchoro wenye mikatizo chini ya Z(n) ungekuja na polinomia isiyo sifuri inayokuwa sifuri kwenye mikatizo yake yote; chukua ile yenye kipeo (degree) cha chini kabisa.
Uso bapa unapinga. Jiometri inaingia kupitia ukweli mmoja wa kitambo: kitanzi kilichofungwa kwenye uso bapa hukatiza kingine kutoka kulia kwenda kushoto mara nyingi sawasawa na kutoka kushoto kwenda kulia. Kwa uzani (weights) uliochaguliwa vizuri, hili linatoa jumla ya miraba ya thamani za polinomia, baadhi zikihesabiwa kuwa chanya, baadhi kuwa hasi, ambayo jumla yake ni sifuri. Vipengele chanya vyote viko kwenye mikatizo, ambapo polinomia ni sifuri, kwa hiyo vile hasi lazima navyo viwe sifuri. Matumizi ya pili ya ukweli wa kitanzi yanaifanya igawanyike kwa kigawanyo (factor) maalum kisichobadilika; kugawanya kunatoa polinomia isiyo sifuri yenye kipeo cha chini zaidi na sifa ileile, jambo lisilowezekana, kwa kuwa tulichukua ile ya chini kabisa.

Hoja hiyo ya ishara chanya na hasi ndiyo badiliko kuu la Balko: inachukua nafasi ya hoja ya awali “inayohusisha umbo la bilinia lisilo dhaifu (nondegenerate bilinear form) na nafasi-kamilishi za othogonali (orthogonal complements)”. Pia anathibitisha ukweli wa kitanzi kwa njia tofauti na anatenga kila nukta kwa njia ya moja kwa moja zaidi.

Mitandao mingine iliyotatuliwa kwa mpigo mmoja

Jibu linabaki Z(n) ikiwa mtu anahesabu, badala ya mikatizo, jozi za mikunjo zinazokatizana angalau mara moja, au zinazokatizana idadi witiri ya mara — mradi mikunjo inayoshiriki nukta haikutani kamwe mahali pengine. Ikiunganishwa na upunguzaji wa awali, teorema hii pia inatoa idadi kamili za mikatizo kwa grafu kamili zilizoondolewa baadhi ya viungo, kwa nakala za grafu kamili zilizounganishwa kama mnyororo kando ya njia au kuzunguka mzingo shufwa (even cycle), na kwa familia ya mitandao inayofanana na fraktali inayoitwa grafu za Sierpiński zilizopanuliwa (extended Sierpiński graphs).

Ondoa mkunjo mmoja tu kutoka kwa grafu kamili ya nukta 6, na kiwango chake cha chini kinashuka kutoka mikatizo 3 hadi 2; kwa nukta 8, kutoka 18 hadi 15.