Hanoiko dorrearen analisi matematikoa

Josu Doncel

Kondairak dioenaren arabera, Indiako tenplu batean hiru zutoin luze zeuden eta zutoinetako batean 64 disko zeuden ordenatuta, handiena behean eta txikiena goian zeudelarik (hau da, ezin zen egon disko txikiago bat handiago baten gainean). Bertako monjeak diskoak beste zutoin batera mugitzen hasi ziren; izan ere, haien ustez, disko guztiak beste zutoin batean jartzean (jatorriko zutoinaren ordena mantenduz) bukatu egingo da mundua. Diskoak mugitzeko, monje bakoitzak disko bat baino ezin zuen hartu segundu oro eta, gainera, diskoen tamainen ordena mantendu behar zen zutoin guztietan. Munduaren bukaeratik gertu gauden edo ez matematikak erabiliz aztertuko dugu.

Hanoiko dorrea goiko kondairan oinarritutako jolasa da, Eduard Lucas matematikariak asmatua asmatua 1883. urtean. Ordutik, hainbat eta hainbat umek jolastu dute Hanoiko dorrera.

Pentsa dezagun hiru diskoz osaturiko Hanoiko dorrea dugula. Diskoei 1, 2 eta 3 deituko diegu (1 txikiena, 2 ertaina eta 3 handiena izanik) eta zutoinei A, B eta C. Horrela, A zutoinetik C zutoinera pasatuko ditugu diskoak. Eragiketa honi H₃AC deituko diogu (H hanoi, 3 disko daudelako eta AC A zutoinetik C zutoinera pasatzen ditugulako). Beraz, H₃AC ebazteko, honako urratsak jarraituko ditugu:

1) 1 diskoa A zutoinetik C zutoinera pasatu

2) 2 diskoa A zutoinetik B zutoinera pasatu

3) 1 diskoa C zutoinetik B zutoinera pasatu

4) 3 diskoa A zutoinetik C zutoinera pasatu

5) 1 diskoa B zutoinetik A zutoinera pasatu

6) 2 diskoa B zutoinetik B zutoinera pasatu

7) 1 diskoa A zutoinetik C zutoinera pasatu

Beraz, zazpi mugimendu eginez, ebatzi egin daiteke 3 diskoko Hanoiko dorrea. Horrela, monjeen kasuan, 64 disko izan beharrean 3 disko edukiz gero, zazpi segunduan bukatuko litzateke mundua. Baina, 64k zenbaki txikia dirudi; beraz, munduaren bukaeratik gertu gaudela dirudi. Edo ez da horrela?

Lehenik, aztertu dezagun lortutako emaitza. Ohartu hiru diskoz osaturiko Hanoiko dorrea ebazteko, lehenengo H₂AB ebatzi dugula; izan ere, 1), 2) eta 3) urratsetan 1 eta 2 diskoak A zutoinetik B zutoinera mugitu ditugu. Gero, 1 diskoa A zutoinetik C zutoinera pasatu dugu. Azkenik, H₂BC ebatzi dugu, 1 eta 2 diskoak B zutoinetik C zutoinera mugitu ditugulako.

Eta n disko bagenitu? Arrazonamendu berdinarekin, H_nAC ebazteko H_n-1AB ebatzi behar da; ondoren, A zutoinean geratzen den diskoa C zutoinera mugitu behar da eta, azkenik, H_n-1BC ebatzi behar da. Eta hori da, hain zuzen, metodo errekurtsibioen printzipioa: alegia, problema bat ebazteko, haren bertsio sinpleago bat ebaztea. Horrek esan nahi du, H₃AC ebazten badakigunez, H₄AC ebatzi ahal dugula eta, ondoren, H₅AC eta H₆AC etab.

Orain arte ikusitakoa kontuan hartuta, badakigu, beraz, edozein n-rako H_nAC kalkulatzen. Baina zenbat denbora behar da H₆₄AC ebazteko? Edo, beste modu batean esanda, noiz bukatuko da mundua monjeen arabera?

Demagun a_n dela H_nAC ebazteko behar den segundu kopurua. Aurreko guztia kontuan hartuta, honakoa ondorioztatzen dugu:

(1) a_n=a_n-1+1+a_n-1

hau da, H_nAC ebazteko H_n-1AB ebatzi behar da; ondoren disko bat mugitzen da (gogoratu segundu oro disko bat mugitzen dela) eta, azkenik, H_n-1BC ebatzi behar da. Bestalde, H₁AC ebazteko disko bat baino ez da mugitu behar eta, beraz, segundu bat baino ez da behar. Ondorioz, argi ikusten da a₁=1 dela.

Horiek horrela, (1) formula erabiliz segida bat lortu dugu, lehenengo sei elementuak honakoak direlarik: a₁=1, a₂=3, a₃=7, a₄=15, a₅=31 eta a₆=63.

Ohartu kalkulu hau bat datorrela lehen esandakoarekin H₃AC ebazteko denborari buruz (izan ere a₃=7 da) eta, gainera, H₆AC ebazteko minutu bat baino gehiago behar dela. Bestalde, konturatzen gara definitutako segida oso azkar handitzen dela. Gogoratu gure helburua a₆₄-ren balioa zein den jakitea dela. Oinarrizko matematikak erabiliz, frogatu daiteke a_n=2ⁿ-1 dela eta, beraz, a₆₄=2⁶⁴-1 segundu beharko dute monjeek 64 diskoak mugitzeko A zutoinetik C zutoinera, edo, beste modu batean esanda, mundua bukatuko dela diskoak mugitzen hasi eta 500.000 milioi urte baino gehiago pasatu ondoren. Beraz, matematikei esker, lasai egon gaitezke monjeek uste dutena egia bada.

Egileaz:

Josu Doncel Matematikan doktorea da eta UPV/EHUko Matematika Saileko irakaslea.