Turnul din Hanoi

Unul dintre jocurile aparent simple, dar cu un adânc substrat matematic, este binecunoscutul Turn din Hanoi. Acest joc a fost inventat de matematicianul francez Edouard Lucas şi a fost comercializat ca jucărie pentru toate vârstele încă din anul 1883. La început era confecţionat din lemn şi consta în câteva discuri de mărimi diferite şi 3 beţişoare. Provocarea este de a muta turnul format din discuri de pe un beţişor pe alt beţişor liber, urmând două reguli simple: la fiecare mutare se mută un singur disc şi niciodată nu se aşază un disc mai mare peste un disc mai mic. Bineînţeles, scopul este acela de a realiza mutarea turnului folosind cât mai puţine mutări.

Se spune că acest joc este inspirat de legenda Turnului lui Brahma, aflat într-un templu al oraşului indian Benares. Acest turn este format din 64 de discuri de aur, de a căror mutare se ocupă preoţii templului, respectând regulile de mai sus. Legenda spune că atunci când turnul discurilor de aur va fi complet transferat pe o altă tijă, templul se va prăbuşi iar lumea va lua sfârşit. Ceea ce ne face să ne întrebăm cu îngrijorare care este numărul minim de mutări în cazul turnului cu 64 de discuri... Pentru a răspunde la această întrebare, vom începe prin a cerceta ce se întâmplă în cazul jocului cu mai puţine discuri.

Să notăm cele 3 beţişoare folosind literele A, B, C. La început, turnul se află pe beţişorul A, iar noi vrem să îl mutăm pe beţişorul C. Vom nota cu n numărul discurilor, iar cu U_n  numărul minim de mutări atunci când avem un turn format din n discuri.
Cu ajutorul jocului de mai jos, putem observa că:
• pentru n = 1, turnul se mută printr-o singură mutare, deci U₁  = 1;
• pentru n = 2, turnul se poate muta prin 3 mutări, deci U₂  = 3;
• pentru n = 3, turnul se poate muta prin 7 mutări, deci U₃  = 7.

Dar în cazul unui turn format din n discuri? Să ne gândim: în procesul de mutare a acestui turn, ajungem la momentul în care toate discurile înafară de cel mai mare sunt mutate pe un alt beţişor (B) decât cel iniţial (A), formând un turn cu n-1 discuri. Dacă presupunem că am ajuns la acest moment folosind numărul minim de mutări, înseamnă că până acum am făcut U_n-1  mutări. În continuare, mutăm discul cel mai mare de pe A pe C, folosind o singură mişcare. Apoi nu ne rămâne decât să mutăm turnul cu n-1 discuri de pe B pe C, peste discul cel mai mare. Acest lucru poate fi făcut prin minim U_n-1 mutări. Acum să numărăm câte mutări am făcut în total: U_n  = U_n-1  +1 + U_n-1  = 2 U_n-1  + 1
Astfel am obţinut o relaţie de recurenţă între numărul minim de mutări pentru un turn cu n discuri şi unul format din n-1 discuri, motiv pentru care acest joc este foarte des folosit ca exemplu pentru tehnici de programare care folosesc recurenţa.
Folosind procedeul numit inducţie matematică, se poate demonstra uşor că numărul minim de mutări în cazul turnului cu n discuri este: U_n  = 2ⁿ - 1.
Aşadar, revenind la Turnul lui Brahma, numărul minim de mutări este 2⁶⁴ - 1, adică un număr de 20 de cifre! Dacă 2⁶⁴ - 1  ar fi secunde, atunci asta ar însemna  circa  584 942 417 355 de ani.  Deci putem sta liniştiţi, sfârşitul lumii e departe: chiar dacă preoţii ar munci fără încetare şi ar face o mutare pe secundă, tot le-ar trebui multe mii de milioane de ani pentru a-şi termina treaba.

După ce matematicienii au epuizat de întors pe toate feţele acest joc, ei au descoperit şi alte variante, mult mai provocatoare din punct de vedere matematic. De exemplu, care ar fi numărul maxim de mutări prin care se poate transfera turnul de pe un beţişor pe altul, fără a reveni la o configuraţie anterioară? Dar dacă jocul ar avea 4 sau mai multe beţişoare în loc de 3? Acestea sunt doar câteva exemple care ne arată cum se poate transforma o problemă relativ simplă într-una de o mare complexitate matematică, prin modificarea minimă a unei singure variabile din enunţul problemei... dar până la urmă, în astfel de lucruri stă frumuseţea matematicii!