Logicus - Antrenamentul conexiunilor rapide

Călugărul Therevada își conduse învățăcelul în grădinița cu trandafiri din spatele mănăstirii budiste și îi arătă cele 3 bețe de bambus înfipte în nisipul din mijlocul aleii. Pe unul din ele înălțase, zicea el, turnul lui Brahma din Hanoi – un turn în trepte din 10 discuri din lemn de santal, găurite la mijloc și dispuse descrescător de la bază spre vârf. Therevada îi ceru învățăcelului să mute turnul din Hanoi așa cum era și din cât mai puține mutări pe unul din celelalte două bețe, folosindu-se la nevoie și de al treilea băț de bambus, dar respectând următoarele 2 condiții:
(i) discurile să fie mutate pe rând, unul câte unul, nu în grupuri de mai multe în același timp;
(ii) la fiecare mutare, se suprapune un disc cu diametru mai mic peste un disc cu diametru mai mare, niciodată invers.
Învățăcelul s-a gândit puțin, apoi a mutat turnul lui Brahma, exact așa cum îi ceruse mentorul său. Mai mult, a găsit chiar și o formulă matematică pentru rezolvarea cazului general a unui turn alcătuit din n discuri de santal, n fiind un număr natural nenul oarecare. Puteți spune câte mutări a efectuat învățăcelul în cazul turnului din 10 discuri și ce formulă generală a găsit?

Soluție:

Să notăm cu A bățul pe care se afla inițial turnul, cu B bățul pe care a ales învățăcelul să mute turnul și cu C bățul rămas.
Învățăcelul a început studiul problemei pornind de la cazuri mai simple, cu un număr de discuri mai mic.
Astfel, dacă pe bățul A există un singur disc, acesta poate fi mutat pe bățul B folosind o singură mutare.
Dacă pe A sunt două discuri, atunci se mută primul disc (cel cu diametrul mai mic) pe bățul C, al doilea disc pe B şi apoi primul disc de pe C pe B, deasupra celui de-al doilea. În total – 3 mutări, cu prima mutare făcută pe bățul C.
Dacă pe A sunt 3 discuri, se mută primele două discuri pe C din trei mutări, după cum s-a văzut la pasul anterior, cu începere de pe B. Apoi, se mută al treilea disc pe bățul B şi din nou cele două discuri de pe C pe B din trei mutări, cu începere de pe A. În total,

mutări, cu începere de pe bățul B.
Dacă pe A sunt 4 discuri, se mută primele 3 discuri pe C din 7 mutări, cu începere de pe C. Apoi, se mută al patrulea disc pe B şi din nou cele 3 discuri de pe C pe B din 7 mutări, cu începere de pe B. În total,

mutări, cu începere de pe bățul C.
În mod analog, 5 discuri se vor transfera de pe A pe B folosind

mutări, cu începere de pe B.
Pentru 6 discuri sunt necesare

mutări, cu începere de pe C.
Pentru 7 discuri sunt necesare

mutări, cu începere de pe B.
Pentru 8 discuri sunt necesare

mutări, cu începere de pe C.
Pentru 9 discuri sunt necesare

mutări, cu începere de pe B.
În sfârşit, pentru 10 discuri sunt necesare

mutări, cu începere de pe C.
În general, pentru n discuri numărul total de mutări este dat de formula de recurenţă:

Din aceasta, învățăcelul a dedus şi formula termenului general al şirului

și anume

(formulă pe care învățăcelul a demonstrat-o apoi prin inducţie matematică după n.)
Pentru n=10, a regăsit numărul de mutări calculat anterior:

• Prec
• Mai departe