KETE SITA ZINAZOSHINDANA KWA ZAMU KATIKA MZUNGUKO

Rusha kete mbili pamoja; namba kubwa zaidi hushinda. Sasa acha kila upande ubebe thamani yoyote kuanzia 1 hadi 6, marudio yakiruhusiwa: kete moja inaweza kusomeka 1, 1, 2, 5, 5, 5. Je, kete sita za aina hiyo zinaweza kupangwa mstari mmoja ili kila moja iishinde inayofuata na ya mwisho iishinde ya kwanza, kila ushindi ukiwa mwembamba kadiri inavyowezekana? Terry Easlick, wa Université de Montréal, ameonyesha kwa kompyuta kwamba sita ndiyo idadi ndogo kabisa ya pande ambayo hili linawezekana, na kwamba kuna njia mbili hasa za kulifanya.

Mapambano kumi na tisa kati ya thelathini na sita

Pambano kati ya kete mbili zenye pande sita lina matokeo 36 yenye uwezekano sawa: kila upande wa moja dhidi ya kila upande wa nyingine. Ili kuwa na ubora, kete lazima itoke juu zaidi katika zaidi ya nusu yake, kwa hiyo angalau 19: uwezekano wa 19/36, takriban 52.8%. Zikiwa na pande n kuna mipangilio ya jozi n × n, na ushindi mwembamba kabisa ni namba kamili ndogo kabisa iliyo juu ya nusu yake: 13 kati ya 25 kwa pande tano, 51 kati ya 100 kwa kumi.

Hivi ndivyo hesabu inavyofanya kazi kwa kete (1, 1, 2, 5, 5, 5) na (1, 3, 4, 4, 4, 4). Zile 5 tatu hushinda pande zote sita za kete ya pili: jozi 18. Ile 2 hushinda 1 pekee ya kete ya pili: moja zaidi, 19 kwa jumla. Zile 1 mbili hutoka sare na 1 hiyo, na kete ya pili hushinda 15 zilizobaki. Kete ya kwanza hushinda mapambano 19 kati ya 36: ushindi mwembamba kuliko yote uliopo.

Kete zinazoshindana katika mzunguko huitwa zisizo-transitivu (non-transitive): kila kete katika mzunguko hushindwa na nyingine, kwa hiyo hakuna iliyo bora kuliko zote. Swali la Easlick: zikiwa na thamani kuanzia 1 hadi n kwenye pande n, ni kwa n zipi ambapo kete n zinaweza kuunda mzunguko kama huo, kila pambano likishindwa kwa tofauti ndogo kabisa hasa, bila mzunguko wowote wa zaidi ya kete n popote miongoni mwa kete zenye pande n kwa tofauti hiyo?

Ramani ya kila kete inayowezekana

Hapa kete ni orodha tu ya thamani, bila mpangilio wowote maalum. Zikiwa na pande sita kuna kete 462, kete ya kawaida (1, 2, 3, 4, 5, 6) ikiwa mojawapo. Easlick huichora kila moja kama nukta, kisha huongeza mshale kutoka kete moja hadi nyingine kila mara ya kwanza inaposhinda mapambano 19 hasa kati ya 36. Kwa pande sita, hilo hufanya mishale 5,491.

Mzunguko wa kete basi ni njia ya mishale inayorudi mahali ilipoanzia. Ili kuipata, programu yake, iliyoandikwa kwa lugha ya Julia, huigawa ramani kuwa vijenzi vilivyounganika kwa nguvu (strongly connected components): makundi makubwa kabisa ambamo unaweza kusafiri kutoka kete yoyote hadi nyingine yoyote kwa kufuata mishale, na kurudi tena. Kila mzunguko uko ndani kabisa ya mojawapo ya makundi haya, kwa hiyo kundi la kete moja halina mzunguko wowote. Mgawanyo huo hutumia algoriti ya Tarjan, iliyochapishwa mwaka 1972. Mwandishi anaeleza kwamba alitumia GPT-5.6 kusaidia kuandika skripti, na kwamba mawazo ya kihisabati ni yake kabisa.

Hakuna, hakuna, hakuna, kisha miwili

Zikiwa na pande tatu kuna kete 10 zinazowezekana na mishale 3 tu; zikiwa na nne, kete 35 na mishale 67; zikiwa na tano, kete 126 na mishale 620. Katika visa vyote vitatu kila kundi lina kete moja tu: kwa tofauti ndogo kabisa, hakuna mzunguko wowote.

Zikiwa na pande sita, kete 448 kati ya 462 hukaa peke yake. Zile 14 nyingine huunda familia mbili za kete saba, kila moja ikiunganishwa na mishale 10. Ndani ya kila familia, programu huorodhesha mizunguko minne: mitatu ya kete tatu na mmoja wa kete sita. Hakuna mzunguko unaoweza kushikilia zaidi ya kete saba, na orodha kamili ya mizunguko katika kila familia haionyeshi wowote wa kete saba, jambo ambalo mwandishi anabainisha kuwa linaweza pia kukaguliwa kwa mkono. Mizunguko hii miwili ya kete sita ndiyo pekee. Wa kwanza:

(1, 1, 2, 5, 5, 5) → (1, 3, 4, 4, 4, 4) → (2, 2, 2, 3, 6, 6) → (1, 1, 2, 5, 5, 6) → (1, 3, 3, 4, 4, 4) → (2, 2, 3, 3, 3, 6) → kurudi kwa ya kwanza.

Wa pili:

(1, 1, 4, 5, 5, 5) → (3, 3, 3, 3, 4, 6) → (2, 2, 2, 5, 6, 6) → (1, 4, 4, 4, 5, 5) → (3, 3, 3, 4, 4, 6) → (1, 2, 2, 5, 6, 6) → kurudi kwa ya kwanza.

Familia ya kwanza ya kete saba: kila kisanduku ni kete moja, pamoja na namba yake katika orodha ya kompyuta na pande zake sita. Mshale unamaanisha «hushinda mapambano 19 hasa kati ya 36». Kwa rangi nyekundu, mzunguko wa kete sita. — Mchoro wa SCC 1, ukurasa 5, Easlick (2026), arXiv:2610.40321.

Suluhisho mbili, taswira moja ya kioo

Mizunguko hiyo miwili haijitegemei. Badilisha kila thamani ya upande v kwa 7 − v: 1 inakuwa 6, 2 inakuwa 5, 3 inakuwa 4, na kinyume chake. Upande uliokuwa juu zaidi sasa uko chini zaidi, kwa hiyo kila mshale hugeuza mwelekeo wake. Easlick anathibitisha kwamba ubadilishanaji huu hugeuza familia ya kwanza kuwa ya pili: mzunguko wa kwanza, ukisomwa kinyumenyume, unakuwa wa pili. Fanya ubadilishanaji huo mara mbili na kila kete hurudi kuwa yenyewe.

Zaidi ya sita, mizunguko huzidi kete

Kuanzia pande saba hadi kumi, kinyume hutokea: mizunguko mingi, lakini mirefu mno. Zikiwa na pande saba, kete 1,081 kati ya 1,716 zinazowezekana huunda familia moja kubwa mno, na mzunguko mrefu wa kwanza unaorudishwa na utafutaji huunganisha kete 14. Zikiwa na pande nane, familia ya kete 4,321 ina mzunguko wa 29; zikiwa na tisa, kete 20,451 na mzunguko wa 10. Zikiwa na pande kumi, kete 92,378 na mishale 157,244,770, familia ya kete 81,791 ina mzunguko wa 110. Hii ni mizunguko ya kwanza mirefu kuliko idadi ya pande ambayo utafutaji uliipata, si ile mirefu kuliko yote.

Mzunguko wa kete 110 zenye pande kumi, kila moja ikiishinda inayofuata katika mapambano 51 hasa kati ya 100. Fuata mishale safu kwa safu; mstari ulio upande wa kushoto hufunga mzunguko. — Mchoro wa kisa n = 10, ukurasa 10, Easlick (2026), arXiv:2610.40321.

Mizunguko kama hiyo huvunja sharti la pili: hakuna mzunguko unaoweza kuwa na kete nyingi kuliko idadi ya pande. Easlick anakisia kwamba sita si tu idadi ndogo kabisa ya pande yenye sifa hii, bali pia ndiyo kubwa kabisa.

Pande kumi na moja, bado haziwezi kufikiwa

Dhana hiyo bado iko wazi. Zikiwa na pande kumi na moja kuna kete 352,716 zinazowezekana; zikiwa na kumi na mbili, 1,352,078. Visa vyote viwili vingechukua muda mrefu zaidi sana kukokotoa; makala haiaripoti ukokotoaji wowote kwa ajili yake, na mwandishi anakisia tu kwamba navyo pia huficha mizunguko ya angalau kete 12 na 13. Makala inahitimisha kwa chanzo cha swali hilo: michezo mingi ya kete ambayo mwandishi alicheza na mama yake.