Ce este acest puzzle, uneori numit "Turnul Brahmin", iar E. Ignatiev numește "Piramida copiilor"? Dacă luați piramida pentru copii (discuri sunt aranjate în ordine crescătoare: de sus - cel mai mic, iar cea mai mică - cea mai mare) și două piramide provin din aceeași copii, puzzle-ul este deja în mâinile tale.
Numărăm tijele: cea pe care se află discurile, va primi numărul 1, celelalte - numerele 2 și 3. Sarcina este de a transfera discurile de la tija 1 pe tija 3, folosind tija 2 ca intermediar. Trebuie respectate două condiții:
- o mutare poate transfera un singur disc,
- Nu puteți pune un disc mai mare pe unul mai mic.
Există o legendă care în orașul indian Benares, zeul Brahma plasat într-unul dintre templele de pe bronz podea trei tije de diamant în grosime corp de albină pe unul dintre ei a pus 64 de discuri de aur și de la crearea lumii neobosit, înlocuind reciproc, preoți transporta discuri de la un stick la altul, în conformitate cu regulile descrise. Când preoții vor purta toate discurile de la prima la a treia tija - spune legenda.- ajuns la capăt.
Să ne dăm seama cum să mutăm discurile de la prima tija la cea de-a treia și, pentru un singur lucru, vom afla dacă sfârșitul promis al lumii vine în curând.
Dacă în piramida era doar un disc, atunci soluția este evidentă - o vom transfera la cel de-al treilea terminal și înțelegerea sa terminat. Am terminat sarcina necesară într-o mișcare. Și dacă ar exista două discuri? Apoi, primul set la a doua cremalieră mai mici, apoi setați al doilea disc la a treia tija, apoi un prenesem mai mic, iar al treilea arbore de antrenare, plasându-l pe partea de sus a celeilalte. Asta e tot. Pentru trei acțiuni, am reușit să schimbăm ambele discuri în a treia tijă. Rețineți că 1 = 2 ^ 1 - 1, și 3 = 2 ^ 2 - 1. Acum, să presupunem că suntem capabili de a trece la a treia piramida tija de n discuri de 2 ^ n-1 acțiune. Arătăm că în acest caz putem transfera la a treia tija și o piramidă de n + 1 discuri și pentru o acțiune 2 ^ (n + 1) - 1.
Într-adevăr, lăsați discurile n + 1 să stea pe piramida. În ziua în care schimbăm numerotarea tijelor: a doua este numită a treia, iar a treia este a doua. Acum putem transfera n discurile superioare de la prima tija la al treilea prin efectuarea a 2 ^ n - 1 acțiuni. La prima tijă era un singur disc. O vom transfera la o a doua tijă liberă. Redenumim tijele din nou: vom returna al doilea numar de tija trei, primul ne dau numarul doi si al treilea numarul unu. Acum avem n discuri pe prima tijă, al doilea este liber, iar pe al treilea există cel mai mare disc. Ramane sa se transfere de la prima tija la al treilea disc n, pe care le putem face pentru 2 ^ n - 1 operatii. Asta e tot. Am colectat toate discurile n + 1 pe a treia tijă, efectuând acțiunea 2 ^ (n + 1) - 1.
Prin urmare, în conformitate cu principiul inducției matematice, rezultă că pentru orice întreg k pozitiv poate fi, având o piramidă cu unități k pentru a le trece de la prima la a treia tijă, urmând regulile 2 ^ k - 1 acțiune.
Această dovadă este ușor de aranjat sub forma unui algoritm de acțiuni. Acest algoritm este sugerat programatorilor în cărțile menționate pentru înregistrarea sa într-una sau alta limbă algoritmică.
Nu este greu de arătat că în mai puțin de 2 k - 1 acțiunea de a transfera discurile k de la prima tija la cea de-a treia este imposibilă. Prin urmare, preoții legendari vor avea nevoie de 2 ^ 64-1 acțiuni pentru a-și desfășura activitatea. Dacă cheltuiți pentru fiecare acțiune doar o secundă, veți avea nevoie de 18.446.744.073.709.551.615 s, adică mai mult de 500 de miliarde de ani.
Să examinăm mai atent procesul de transfer al discurilor. Pentru a face acest lucru, le numărăm în ordine crescătoare: prima este cea mai mică, etc. Acum începem să transferăm discurile în conformitate cu algoritmul și să notăm numerele discurilor transferate:
Este curios că fiecare transfer ciudat este transferul primului disc. O altă observație: aranjați tijele la vârfurile unui triunghi echilateral și urmăriți mișcarea primului disc. Se pare că se mișcă într-un cerc în aceeași direcție; În acest caz, dacă numărul inițial de discuri este egal, apoi în sensul acelor de ceasornic și dacă este ciudat - împotrivă. Aceste observații au făcut posibil ca în 1961 să se formuleze următorul algoritm de transfer pentru discuri:
transfera mai întâi primul disc, iar apoi nu este primul, apoi din nou prima, atunci nu primul, și așa mai departe cu primul disc este transferat într-o singură direcție .. sensul acelor de ceasornic, în cazul unui număr par de discuri și invers acelor de ceasornic, în cazul unui număr impar.
Rețineți că instrucțiunea "nu primul disc este transferat" determină complet ce disc și unde să se transfere în acest moment, deoarece discul mai mic este întotdeauna pus pe unul mai mare.
Recent, un elev de la Perm, Misa Fedorov, a propus un alt algoritm, care, ca cel descris mai sus, poarta k discuri de la prima tija la al treilea pentru acțiuni 2 ^ k - 1.
Misha introduce conceptul de "turn gol". Tijele cu strunguri strânse pe ele le cheamă pe turnuri, iar turnul, care nu participă la operația de transfer de discuri în acest moment, sună goală. Algoritmul lui M. Fedorov este formulat pe scurt:
în procesul de deplasare a turnului gol trebuie să se deplaseze într-un cerc în aceeași direcție: în sensul acelor de ceasornic, dacă numărul de discuri este ciudat și în sens contrar acelor de ceasornic, dacă numărul lor este egal.
Misha Fedorov a relatat cu succes despre munca sa la Conferința Științifică și Tehnică a Copiilor Școlari. Rețineți că dacă primul algoritm conduce la rezultatul dorit prin construcție, atunci validitatea celui de-al doilea și celui de-al treilea ar trebui să fie dovedită, iar acest lucru nu este foarte simplu. Deși, de fapt, toți cei trei algoritmi sunt înregistrări diferite ale aceluiași proces de transfer de unitate.
Un proces în esență diferit apare în cazul în care regulile de transfer sunt și mai complicate. Cititorul nostru A. Tarasenko propune găsirea unui algoritm care să permită transferarea discurilor de la prima tija la cea de-a treia, în care primul disc nu ar fi niciodată la a doua tijă. El susține că o astfel de procedură este posibilă pentru acțiunea 2 * 3 ^ (k-1) - 1. În general, dacă interzicem ca cel de-al doilea disc să apară pe a doua tijă, atunci numărul de schimburi devine 2 ^ 2 * 3 ^ (k-2) -1. Și, în general, dacă interziceți să puneți al doilea disc pe cel de-al doilea terminal, atunci aveți nevoie de 2 ^ n * 3 ^ (k-n) -1 acțiune.
Am scris, de asemenea, despre o altă modificare a acestui puzzle în numărul precedent al revistei (la pagina 4 a copertei). V.Panaev sugerează să se ia în considerare întrebarea: este întotdeauna posibil să se transfere discurile de la prima tija la cea de-a treia, dacă inițial ei se aflau pe prima tijă într-o ordine arbitrară. Dăm dovadă că o astfel de schimbare este întotdeauna posibilă.
Pentru a dovedi posibilitatea unei astfel de schimbări, ne confruntăm întâi cu o sarcină mai simplă. Să se ceară asamblarea unei piramide de pe discuri înșurubate pe două tije, cu o treime liberă, discurile fiind amplasate pe tije în creșteri ale diametrelor. În plus, să presupunem că deja știm cum să rezolvăm o astfel de problemă pentru mai puține discuri.
Să presupunem că cel mai mare disc este pe primul tija, apoi pentru a construi piramida pe a treia tija, trebuie să faci trei operații:
- colectează pe a doua tija o piramidă fără cel mai mare disc;
- Mutați cel mai mare disc pe a treia tijă;
- mișcați piramida de la a doua tija la a treia.