TORRES DE HANOI (La tour d'Hanoi).

Aquest joc consisteix en una base amb 3 pals on inserir uns discs. S’han de moure les peces (arrossegueu-les amb el cursor) d’una en una i d’un pal a l’altre, fins a tenir-les totes en l'últim pal.

Els discs es poden moure d'un en un i mai no es poden deixar sobre un altre disc de mida més petita. La gràcia del joc és desplaçar tots els discs amb el mínim nombre de moviments.

Amb el cursor arrossega els discs d’un pal a un altre. L’objectiu és aconseguir desplaçar tots els discs fins a l’últim pal amb el menor nombre de moviments possible. No està permès col·locar un disc més gran sobre un de més petit.

Pots jugar amb quantitats diferents de discs, de 2 a 6.

Mentre juguesamb l'interactiu, a la dreta de la imatge es va configurant el “mapa” (graf) que ens ajuda a saber cap a on ens hem de moure. Cada posició legal del joc està representada per un punt i cada moviment permès està representat per un segment que uneix la posició de sortida i la posició d'arribada. Per resoldre el joc de la forma més ràpida cal anar en línia recta seguint la vora del triangle

Orientacions:

  • 1. Es pot començar a jugar amb menys peces.
  • 2. Cal aprofitar la recurrència dels moviments (repetició).

A partir del 5è disc, el graf és tan dens que la seva representació gràfica impedeix l'operativa normal. De totes maneres, per ampliar aquesta experiència, us proposem un petit repte:

Serieu capaços de dibuixar el graf corresponent a 5 discs??

Saber-ne més

Trobaràs més informació sobre aquest joc a Les Torres de Hanoi: un bon mapa sempre ajuda!

El 1883 es va començar a vendre a França un trencaclosques oriental, recuperat pel professor N. Claus (de Siam). Segons una llegenda índia, al Temple de Benarés, sota el punt que marca el centre del món, hi ha una placa de llautó amb tres agulles de diamant. Durant la creació, Deu va situar 64 discs d’or pur de diferents mides en una de les agulles, formant una torre. Els monjos porten generacions canviant de lloc, un a un, els discs de la torre entre les tres agulles de forma que mai un disc més gran es trobi sobre un més petit. Quan acabin de traslladar tots els discs a una altra agulla hauran acabat la feina, i la torre i el temple s’esfondraran, provocant un gran tro que farà desaparèixer el món. La versió que es venia tenia 8 discs de fusta.

De fet, tota aquesta història va ser un invent del matemàtic francès Édouard Lucas (N. Claus de Siam és un anagrama de Lucas d’Amiens). Tot i la simplicitat del repte, ha donat molt de joc al llarg de la història de les matemàtiques recreatives.

Curiosament, es tracta d’un bon exemple per parlar del concepte de recursivitat quan es parla de programació d’ordinadors, atès que hi ha un algoritme recursiu molt simple que ho resol.

Per moure el disc número vuit, primer hem de treure els set de sobre situant-los en forma de torre en una altre posició i per fer això, primer haurem hagut de moure el disc set, és a dir la torre de sis, i abans la de cinc, etc.

Per tant l’algoritme per n discs, amb posicions A, B i C, és:

  1. Si n=1, passa el disc 1 de A a C i acaba.
  2. Trasllada la torre 1...n−1 fent servir aquest mateix algoritme, de A a B, fent servir com auxiliar C.
  3. Porta el disc n de A a C.
  4. Trasllada la torre 1...n−1 fent servir aquest mateix algoritme, de B a C, fent servir com auxiliar A.

A cop d’ull no sembla que resolgui res, però funciona, donant la solució òptima (amb menys moviments).

Es verifica per n=1: 1 = 21 – 1

Si es verifica per n, es verifica per n+1: 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1

(L’algoritme es fa servir dues vegades per a n, més un moviment del disc n+1)

Per a n=8 el nombre de moviments és de 28 - 1 = 255.

Si feu el càlcul dels moviments que han de fer els monjos, podreu comprovar que fan falta unes quaranta vegades l’edat de l’Univers, podem estar tranquils.

Es pot trobar més informació a: http://www.rodoval.com/heureka/hanoi/index.html

Propostes per a professorat: Torres de Hanoi

Enllaç per jugar amb més discs: http://www.mazeworks.com/hanoi/index.htm

FCRi finançat per: FECYT