Dos trencaclosques “orientals”, o no

El joc de les Torres de Hanoi, publicat pel matemàtic francès Édouard Lucas l’any 1883, no té a veure amb la ciutat de Hanoi, senzillament és la que apareix al conte de l’enunciat. Físicament consta de tres varetes verticals, a la primera de les quals hi ha inserits un conjunt de discs ―foradats― de mides creixents. L’objectiu del joc és passar tots els discs de la primera a la tercera vareta, respectant les següents condicions:

❀ En cada moviment només podem transferir un sol disc d’una vareta a una altra.
❀ No es pot mai col·locar un disc sobre un altre que sigui més petit que ell.

Foto d’unes Torres de Hanoi amb vuit discs de colors alternats

El mínim de moviments necessaris per assolir l’objectiu del joc, si anomenem n al nombre de discs, és de 2n–1, o sigui que pels vuit discs de la foto serien 255 moviments; o, pels casos d’entre 2 i 7 discs: 3, 7, 15, 31, 63 o 127 moviments respectivament.

Quins són precisament aquests moviments mínims?

Existeix un algorisme per poder-los fer, d’una manera quasi automàtica, sense haver de pensar gaire.

❀ Imaginem els discs, a la vareta inicial, pintats alternativament començant per la base, de dos colors, per exemple clar i fosc ―a la foto, que és manipulada, els veiem realment així.
❀ Tots els moviments que fem en el joc, han de respectar aquesta alternança de colors. No es pot posar mai un disc clar sobre clar, ni fosc sobre fosc.
❀ Com a primer moviment, si el nombre de discs total és senar, el movem a la vareta de destí, si és parell, el movem a l’altre vareta.
❀ A partir d’aquí, sempre ens trobarem que a cada torn només hi ha un moviment possible ―respectant l’alternança de color― diferent al de retrocedir la peça que acabem de moure. Aquest moviment ens porta automàticament a la solució en el nombre de jugades mínim possible.

Solució del cas de 4 discs. Aquí podem considerar clar els discs verds i fosc els vermells.

Aquest joc, curiosament, és similar a un altre, també amb nom oriental, les «anelles xineses», també estudiat per Édouard Lucas. El joc  consisteix en treure —o posar fent els moviments contraris— un passador en un conjunt d’anelles penjades d’una tija, cadascuna de les quals abraça la tija de l’anterior. També té solucions en 3, 7, 15, 31, 63 o 127 moviments per a dues a set anelles. I, en la solució, els avenços i retrocessos del passador també tenen a cada pas una única possibilitat que alterni passar per dins i per fora de la següent anella, i no sigui retrocedir a la posició anterior.

Les meves anelles xineses, cal treure la peça daurada (que no ho és, és pintada a la foto)
Aquesta entrada ha esta publicada en Divulgació, Educació, Problemes. Afegeix a les adreces d'interès l'enllaç permanent.

Deixa un comentari

L'adreça electrònica no es publicarà. Els camps necessaris estan marcats amb *

*