Turnurile din Hanoi: numărul minim de mutări

Turnurile din Hanoi, cu trei tije și $n$ discuri, se rezolvă în minimum $2^n-1$ mutări. La fiecare mutare deplasezi un singur disc, iar un disc mai mare nu poate fi pus peste unul mai mic. Formula este valabilă pentru mutarea întregului turn de pe o tijă pe alta, respectând aceste reguli.

Pentru șase discuri, minimul este 63 de mutări. Adăugarea unui disc nu adaugă o singură mutare: pentru șapte discuri ai nevoie de 127. Explicația vine din munca necesară pentru a elibera discul cel mai mare și apoi pentru a reconstrui turnul deasupra lui.

Care sunt regulile exacte ale jocului?

Ai trei tije, pe care le numim A, B și C. Toate discurile pornesc pe A, în ordine descrescătoare de jos în sus. Discul cel mai mare este la bază, cel mai mic la vârf. Scopul este să refaci aceeași stivă pe C.

Poți lua numai discul de sus al unei tije. Îl poți pune pe o tijă goală sau deasupra unui disc mai mare. Nu muți o stivă întreagă într-o singură operație și nu așezi discuri temporar în afara celor trei tije.

Discurile au dimensiuni diferite, iar tijele au același rol în reguli. B este o tijă auxiliară în rezolvarea finală, dar în subproblemele mici rolurile se schimbă. Uneori chiar C devine locul de lucru temporar.

Pentru explorare, poți folosi trei zone desenate pe hârtie și cartonașe de dimensiuni diferite. Notează fiecare mutare. Altfel este ușor să refaci involuntar o stare anterioară și să nu mai știi câte mutări ai folosit.

Cum rezolvi două discuri?

Cu un singur disc, îl muți direct de pe A pe C: o mutare. Cu două discuri, cel mic blochează accesul la cel mare. Mai întâi muți discul mic pe B, apoi discul mare pe C, iar la final discul mic de pe B pe C.

Sunt trei mutări. Nu există o soluție în două, deoarece discul mic trebuie să plece de pe A înaintea celui mare și trebuie să ajungă apoi pe C. El este mutat de două ori, iar discul mare cel puțin o dată.

Acesta este primul exemplu în care distingi o soluție posibilă de o soluție minimă. Enumerarea celor trei mutări dovedește că poți termina în trei. Explicația blocajului dovedește că nu poți termina în mai puține.

Această deosebire dintre experiment și justificare se potrivește cu învățarea prin înțelegere, nu doar memorare: un tipar numeric este începutul unei explicații, nu finalul ei.

Cum arată cele șapte mutări pentru trei discuri?

Numerotează discurile de la 1, cel mai mic, la 3, cel mai mare. O rezolvare de pe A pe C este:

Mutare	Disc	Plecare	Sosire
1	1	A	C
2	2	A	B
3	1	C	B
4	3	A	C
5	1	B	A
6	2	B	C
7	1	A	C

Primele trei mutări transferă turnul mic, format din discurile 1 și 2, de pe A pe B. Mutarea a patra transferă discul mare pe C. Ultimele trei reconstruiesc turnul mic pe C, deasupra lui.

Observă că discul mare este mutat o singură dată în această soluție. Nu trebuie să inventezi șapte decizii independente: rezolvi de două ori problema cu două discuri și intercalezi mutarea discului mare.

De unde apare relația de recurență?

Notează cu $T_n$ numărul minim de mutări pentru $n$ discuri. Strategia descrisă oferă trei etape:

1. Muți cele $n-1$ discuri mici de pe A pe B.
2. Muți discul cel mai mare de pe A pe C.
3. Muți cele $n-1$ discuri mici de pe B pe C.

Fiecare transfer al turnului mic poate fi făcut în $T_{n-1}$ mutări. Rezultă o soluție cu $2T_{n-1}+1$ mutări. Pentru a afirma că aceasta este valoarea minimă, mai trebuie arătat că nicio strategie nu poate folosi mai puține.

Înainte de prima mutare a discului mare, toate discurile mici trebuie să formeze un turn pe singura tijă care nu participă la acea mutare. Această pregătire costă cel puțin $T_{n-1}$ mutări.

După ultima mutare a discului mare pe tija destinație, toate discurile mici sunt din nou pe cealaltă tijă liberă. Transferul lor final costă cel puțin încă $T_{n-1}$. Între aceste etape există cel puțin o mutare a discului mare. Orice mutări suplimentare nu pot coborî această limită.

Avem deci și o limită inferioară, și o strategie care o atinge:

$$T_n=2T_{n-1}+1,\qquad T_1=1.$$

Cum obții formula fără să ghicești?

Adaugă unu în ambele părți ale relației: $T_n+1=2(T_{n-1}+1)$. Noul șir, format din numerele $T_n+1$, se dublează la fiecare pas.

La un disc, $T_1+1=2$. La două discuri obții 4, la trei obții 8, iar la $n$ discuri obții $2^n$. Scăzând unu, rezultă $T_n=2^n-1$.

Poți verifica primele valori:

Discuri	Mutări minime
1	1
2	3
3	7
4	15
5	31
6	63

Nu sunt numere impare oarecare. Diferențele dintre termeni sunt 2, 4, 8, 16 și 32. Un șir care ar continua cu 47 după 31 nu ar respecta dublarea cerută de strategie.

Cât durează o rezolvare într-un model simplificat?

Dacă presupui exact o mutare pe secundă, zece discuri cer $2^{10}-1=1023$ de secunde. Aceasta înseamnă 17 minute și trei secunde. Pentru 15 discuri ai 32.767 de secunde, adică nouă ore, șase minute și șapte secunde.

Acestea sunt durate teoretice pentru ritmul presupus, fără pauze și fără greșeli. Nu reprezintă estimări despre cât poate lucra un copil sau despre durata unei lecții. Rolul lor este să arate cât de repede crește numărul operațiilor.

Dacă dublezi numărul discurilor, nu dublezi timpul. De la cinci la zece discuri treci de la 31 la 1.023 de mutări. Formula permite verificarea acestei diferențe înainte să încerci fizic o configurație prea lungă.

Ce poți afla dintr-un buget de mutări?

Ai voie cel mult 100 de mutări. Șase discuri cer 63, iar șapte cer 127. Prin urmare, poți garanta rezolvarea optimă a unui turn de cel mult șase discuri în limita dată.

Nu rotunjești șapte discuri la șase și jumătate. Numărul discurilor este întreg, iar limita de mutări trebuie respectată. Verifici două valori vecine ale formulei și alegi cea mai mare admisă.

Dacă dificultatea este calculul puterii înaintea scăderii, reia ordinea efectuării operațiilor. Expresia $2^n-1$ înseamnă că scazi unu după ridicarea la putere; nu este $2^{n-1}$.

Cum recunoști o soluție validă, dar neoptimă?

O succesiune poate respecta toate regulile și totuși să conțină ocoluri. Dacă muți discul mic de pe A pe B și imediat înapoi pe A, ai revenit la aceeași stare după două mutări. Nu ai apropiat turnul de configurația finală.

Pentru patru discuri, o rezolvare validă în 17 mutări nu contrazice formula. Formula spune că minimul este 15, nu că orice succesiune legală are exact 15 mutări. La verificare, controlezi separat legalitatea fiecărui pas și numărul total.

Exerciții cu răspunsuri explicate

1. Câte mutări minime cer opt discuri? 255, deoarece $2^8-1=255$.
2. Dacă un turn cere 31 de mutări, câte cere unul cu un disc în plus? 63, din $2\cdot31+1$.
3. Câte discuri poți muta optim în cel mult 500 de mutări? 8. Nouă discuri ar cere 511.
4. Dacă ai zero discuri, câte mutări sunt necesare? 0. Convenția $T_0=0$ este compatibilă cu formula și cu începutul recurenței.

Dacă poți reproduce pașii, dar nu poți justifica minimul, lucrează separat demonstrația blocării discului mare. Este o întrebare concretă de discutat cu un profesor din anunțurile pentru meditații la matematică.

Întrebări frecvente

Formula rămâne aceeași cu patru tije?

Nu o poți aplica automat. O tijă suplimentară permite alte strategii și schimbă problema de minimizare.

Pot muta două discuri mici împreună?

Nu în jocul analizat aici. Fiecare mutare deplasează un singur disc; schimbarea regulii schimbă și numărătoarea.

Unde pot explora jocul?

Activitatea NRICH despre Turnurile din Hanoi propune investigarea cazurilor mici. Tabelul de mutări, demonstrația și exercițiile de aici sunt prezentate ca o rezolvare construită separat.