ƊAN CACA SHIDA DA KE DOKE JUNA A ZAGAYE

Jefa ’yan caca biyu tare; lambar da ta fi girma ta yi nasara. Yanzu bari kowace fuska ta ɗauki kowace ƙima daga 1 zuwa 6, ana yarda da maimaitawa: ɗan caca zai iya karanta 1, 1, 2, 5, 5, 5. Shin za a iya jera irin waɗannan ’yan caca shida ta yadda kowanne zai doke na gaba kuma na ƙarshe ya doke na farko, kowace nasara ƙarama gwargwadon yiwuwa? Terry Easlick, na Université de Montréal, ya nuna da kwamfuta cewa shida ne mafi ƙanƙantar adadin fuskoki da wannan ke aiki da shi, kuma akwai hanyoyi biyu daidai na yin hakan.

Gwabzawa goma sha tara cikin talatin da shida

Gwabzawa tsakanin ’yan caca biyu masu fuska shida tana da sakamako 36 masu daidaiton yiwuwa: kowace fuska ta ɗaya da kowace fuska ta ɗayan. Don samun fifiko, ɗan caca dole ya fito da lamba mafi girma a fiye da rabinsu, don haka aƙalla 19: yiwuwar 19/36, kusan kashi 52.8%. Da fuskoki n akwai haɗe-haɗe n × n, kuma mafi ƙanƙantar nasara ita ce mafi ƙanƙantar cikakkiyar lamba sama da rabinsu: 13 cikin 25 ga fuskoki biyar, 51 cikin 100 ga goma.

Ga yadda ƙirgar ke aiki ga ’yan cacar (1, 1, 2, 5, 5, 5) da (1, 3, 4, 4, 4, 4). 5 ɗin nan uku suna doke dukan fuskoki shida na ɗan caca na biyu: haɗe-haɗe 18. 2 yana doke 1 ɗaya tilo na ɗan caca na biyu: ƙarin ɗaya, 19 gaba ɗaya. 1 ɗin nan biyu suna kunnen doki da wannan 1, kuma ɗan caca na biyu yana cin sauran 15. Ɗan caca na farko yana cin gwabzawa 19 cikin 36: nasara mafi ƙanƙanta da ke akwai.

’Yan caca da ke doke juna a zagaye ana kiransu marasa ci-gaba (non-transitive): kowane ɗan caca a cikin zagayen wani yana doke shi, don haka babu wanda ya fi duka. Tambayar Easlick: da ƙimomi daga 1 zuwa n a kan fuskoki n, ga wane n ne ’yan caca n za su iya samar da irin wannan zagaye, kowace gwabzawa an ci ta da mafi ƙanƙantar tazara daidai, ba tare da wani zagaye na ’yan caca fiye da n ba a ko’ina cikin ’yan caca masu fuska n a wannan tazarar?

Taswirar kowane ɗan caca mai yiwuwa

A nan ɗan caca jerin ƙimomi ne kawai, ba bisa wani tsari na musamman ba. Da fuskoki shida akwai 462 daga cikinsu, ciki har da ɗan caca na yau da kullum (1, 2, 3, 4, 5, 6). Easlick yana zana kowanne a matsayin ɗigo, sannan ya ƙara kibiya daga ɗan caca ɗaya zuwa wani a duk lokacin da na farkon ya ci gwabzawa 19 cikin 36 daidai. Ga fuskoki shida, wannan yana ba da kibiyoyi 5,491.

Zagayen ’yan caca sai ya zama hanyar kibiyoyi da ke komawa inda ta fara. Don samo su, shirinsa na kwamfuta, da aka rubuta da harshen Julia, yana raba taswirar zuwa sassa masu haɗe sosai (strongly connected components): manyan rukunoni da za ka iya tafiya daga kowane ɗan caca zuwa kowane wani a kan kibiyoyin, ka kuma dawo. Kowane zagaye yana cikin ɗaya daga cikin waɗannan rukunoni gaba ɗaya, don haka rukunin ɗan caca ɗaya ba shi da ko ɗaya. Rabuwar tana amfani da algorithm ɗin Tarjan, da aka wallafa a 1972. Marubucin ya bayyana cewa ya yi amfani da GPT-5.6 don taimakawa wajen rubuta shirye-shiryen (scripts), kuma ra’ayoyin lissafin nasa ne gaba ɗaya.

Babu, babu, babu, sannan biyu

Da fuskoki uku akwai ’yan caca 10 masu yiwuwa da kibiyoyi 3 kawai; da huɗu, ’yan caca 35 da kibiyoyi 67; da biyar, ’yan caca 126 da kibiyoyi 620. A dukan lamuran uku kowane rukuni yana ɗauke da ɗan caca ɗaya kawai: a mafi ƙanƙantar tazara, babu zagaye ko kaɗan.

Da fuskoki shida, 448 daga cikin ’yan caca 462 suna zaune su kaɗai. Sauran 14 suna samar da iyalai biyu na ’yan caca bakwai, kowanne an haɗa shi da kibiyoyi 10. A cikin kowane iyali, shirin yana lissafa zagaye huɗu: uku na ’yan caca uku da ɗaya na shida. Babu zagaye da zai iya ɗaukar ’yan caca fiye da bakwai, kuma cikakken jerin zagaye a kowane iyali ba ya nuna ko ɗaya na bakwai, wanda marubucin ya lura ana iya dubawa da hannu ma. Waɗannan zagaye biyu na shida su kaɗai ne. Na farko:

(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) → koma zuwa na farko.

Na biyu:

(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) → koma zuwa na farko.

Iyali na farko na ’yan caca bakwai: kowane akwati ɗan caca ɗaya ne, da lambarsa a cikin jerin kwamfutar da fuskokinsa shida. Kibiya tana nufin “yana cin gwabzawa 19 cikin 36 daidai”. Da ja, zagayen shida. — Zanen SCC 1, shafi na 5, Easlick (2026), arXiv:2610.40321.

Mafita biyu, hoton madubi ɗaya

Zagaye biyun ba su zama masu zaman kansu ba. Maye gurbin kowace ƙimar fuska v da 7 − v: 1 ya zama 6, 2 ya zama 5, 3 ya zama 4, da akasin haka. Fuskar da ta fi girma yanzu ta fi ƙanƙanta, don haka kowace kibiya tana juya alƙibla. Easlick ya tabbatar da cewa wannan musanya tana mayar da iyali na farko zuwa na biyu: zagayen farko, idan aka karanta shi a baya, yana zama na biyu. Yi musanyar sau biyu kuma kowane ɗan caca yana komawa kansa.

Bayan shida, zagaye suna girma fiye da ’yan caca

Daga fuskoki bakwai zuwa goma, akasin haka ne ke faruwa: zagaye da yawa, amma masu tsawo da yawa. Da fuskoki bakwai, 1,081 daga cikin ’yan caca 1,716 masu yiwuwa suna samar da babban iyali ɗaya, kuma zagaye mai tsawo na farko da binciken ya dawo da shi yana haɗa ’yan caca 14. Da fuskoki takwas, iyali na ’yan caca 4,321 yana ɗauke da zagaye na 29; da tara, ’yan caca 20,451 da zagaye na 10. Da fuskoki goma, ’yan caca 92,378 da kibiyoyi 157,244,770, iyali na ’yan caca 81,791 yana ɗauke da zagaye na 110. Waɗannan su ne zagaye na farko masu tsawo fiye da adadin fuskoki da binciken ya samo, ba mafi tsawo ba.

Zagaye na ’yan caca 110 masu fuska goma, kowanne yana doke na gaba a gwabzawa 51 cikin 100 daidai. Bi kibiyoyin layi bayan layi; layin da ke hagu yana rufe zagayen. — Zanen lamarin n = 10, shafi na 10, Easlick (2026), arXiv:2610.40321.

Irin waɗannan zagaye suna karya sharaɗi na biyu: babu zagayen da zai ƙunshi ’yan caca fiye da adadin fuskoki. Easlick yana hasashen cewa shida ba wai mafi ƙanƙantar adadin fuskoki da ke da wannan siffa ba ne kawai, har ma mafi girma.

Fuskoki goma sha ɗaya, har yanzu ba a kai ba

Wannan hasashe har yanzu a buɗe yake. Da fuskoki goma sha ɗaya akwai ’yan caca 352,716 masu yiwuwa; da goma sha biyu, 1,352,078. Lissafin lamuran biyu zai ɗauki lokaci mai tsawo ƙwarai; takardar ba ta ba da rahoton wani lissafi a kansu ba, kuma marubucin yana zato ne kawai cewa su ma suna ɓoye zagaye na aƙalla ’yan caca 12 da 13. Takardar ta ƙare da inda tambayar ta fito: wasannin ɗan caca da yawa da marubucin ya yi da mahaifiyarsa.