Turnurile din Hanoi
Turnurile din Hanoi sunt un puzzle matematic clasic. Trei tije, o stivă de discuri de mărimi diferite și două reguli stricte: mută câte un disc și nu pune niciodată un disc mai mare pe unul mai mic.
Trei tije și un con de discuri
Tabla are trei tije. Discurile au toate mărimi diferite și se pun pe tije. La început tot setul stă pe o tijă, ordonat după mărime, cu cel mai mare jos și cel mai mic sus, așa că stiva este un con. Scopul este să muți tot turnul pe altă tijă.
Cele trei reguli
1. Mută un singur disc o dată. 2. O mutare ia discul de sus de pe o stivă și îl pune pe altă stivă sau pe o tijă goală. 3. Un disc mai mare nu poate sta niciodată pe unul mai mic. Aceste trei reguli sunt tot jocul. Cu ele, fiecare poziție permisă este un mod de a împărți discurile pe tije, astfel încât fiecare tijă să rămână ordonată.
Cea mai scurtă soluție este 2ⁿ − 1
Cel mai mic număr de mutări care rezolvă un turn de n discuri este 2ⁿ − 1. Un disc cere 1 mutare. Două discuri cer 3. Trei cer 7, patru 15 și cinci 31. Fiecare disc nou dublează soluția anterioară și adaugă mutarea care duce discul cel mai mare: dacă n − 1 discuri cer T mutări, atunci n discuri cer 2T + 1. Această recurență dă exact 2ⁿ − 1. Opt discuri, cel mai înalt turn din aplicația PictorX, cer 255 de mutări. Nu există un drum permis mai scurt.
Cum funcționează recursivitatea
Ca să muți n discuri de pe tija de start pe tija țintă, folosind tija rămasă ca tijă auxiliară: 1. Mută cele n − 1 discuri de sus de pe tija de start pe tija auxiliară. 2. Mută discul cel mai mare de pe tija de start direct pe tija țintă. 3. Mută cele n − 1 discuri de pe tija auxiliară pe tija țintă, peste discul cel mai mare. Pasul 2 este permis pentru că discul cel mai mare poate sta pe orice tijă. Pașii 1 și 3 sunt același puzzle, cu un disc mai puțin. Apelul se oprește la un singur disc, care se mută o dată. Desfășurat, produce cele 2ⁿ − 1 mutări, iar niciun pas nu pune vreodată un disc mai mare pe unul mai mic.
Legenda celor 64 de discuri de aur
Matematicianul francez Édouard Lucas a prezentat puzzle-ul în 1883. Odată cu el a spus o legendă despre un templu indian din Kashi Vishwanath, unde preoții mută o stivă de 64 de discuri de aur după aceleași reguli. Când se va face ultima mutare, spune legenda, lumea se va sfârși. Șaizeci și patru de discuri cer 2⁶⁴ − 1 mutări: 18.446.744.073.709.551.615. La o mutare perfectă pe secundă, zi și noapte, înseamnă aproximativ 585 de miliarde de ani. Preoții nu vor termina.
Joacă în PictorX
Deschide Turnurile din Hanoi și pe tija de start este deja un turn de patru discuri. Cincisprezece mutări sunt minimul. Trage discul de sus pe altă tijă sau dă clic pe o tijă și apoi pe cea dorită. Tastele 1, 2 și 3 fac același lucru. Un disc mai mare pe unul mai mic este refuzat. Discuri merge de la 1 la 8, așa că poți verifica 1, 3, 7, 15, 31, 63, 127 și 255 cu formula. Pas redă o mutare dintr-o soluție cea mai scurtă. Rezolvă redă restul. „Urmărește 3 discuri” arată strategia recursivă în mișcare. Anulează și Refă parcurg mutările tale. Salvează un PNG sau deschide tabla în editorul PictorX.
Întrebări frecvente
Care sunt regulile Turnurilor din Hanoi?
Mută câte un disc. Ia discul de sus de pe o tijă și pune-l pe altă tijă. Nu pune niciodată un disc mai mare pe unul mai mic. Tot turnul pornește de pe o tijă și trebuie să ajungă pe alta.
Câte mutări are cea mai scurtă soluție?
2ⁿ − 1. Un disc înseamnă 1 mutare, două discuri 3, trei 7, patru 15 și cinci 31. Fiecare disc adăugat dublează soluția anterioară și adaugă o mutare.
Cine a inventat Turnurile din Hanoi?
Matematicianul francez Édouard Lucas l-a prezentat în 1883. Povestea preoților și a celor 64 de discuri de aur de la Kashi Vishwanath este legenda pe care a atașat-o puzzle-ului.
Cât ar dura 64 de discuri?
2⁶⁴ − 1 mutări, adică 18.446.744.073.709.551.615. La o mutare pe secundă, înseamnă aproximativ 585 de miliarde de ani.
Unelte conexe
Turnurile din Hanoi
Mută un turn de discuri pe trei tije, în browser. Câte un disc, niciodată unul mai mare pe unul mai mic. Cea mai scurtă soluție are 2ⁿ − 1 mutări.
Acul lui Buffon
Lasă ace să cadă pe o podea liniată, în browser. Numără intersecțiile și urmărește cum experimentul lui Buffon din 1777 estimează π.
Acul lui Buffon
Problema acului lui Buffon din 1777: de ce un ac lăsat să cadă pe linii paralele estimează π, cum rezultă probabilitatea 2l/(πd) a acului scurt din aria de sub o curbă a sinusului și de ce experimentul converge lent.
Cercuri de înmulțire
Unește fiecare număr de pe un cerc cu multiplul său. Desenează o tablă a înmulțirii, o cardioidă sau o figură din fir pe hârtie, cu cretă sau pe lemn.
Conjectura Collatz
Explorează problema Collatz 3n+1 în browser. Urmărește șiruri grindină, crește un arbore Collatz geometric și mărește fractalul Collatz continuu.
Furnica lui Langton
Rulează furnica lui Langton în browser. Urmărește simetria, haosul și autostrada de 104 pași, apoi încearcă reguli multicolore, mai multe furnici, o grilă hexagonală și turmite.
Eşti gata să încerci?
Deschide PictorX în browser-ul tău
Joacă Turnurile din Hanoi