Hanojska kula i smak sveta

Legenda kaže da je indijski vladar za koga je jedan matematičar izumeo igru šah bio toliko oduševljen igrom da je postavio šahovsku tablu u svaki indijski hram, a matematičaru ponudio da sam izabere nagradu za svoj genijalni izum. Kada mu je matematičar zatražio da mu za prvo šahovsko polje pokloni jedno zrno žita, za drugo polje dva, za treće četiri i uvećavajući količinu za duplo isplati tako svih 64 šahovskih polja, vladar se iznenadio njegovom skromnošću. Još veće iznanađenje je usledilo kada su kralja obavestili da takav niz zrna žita, iako u početku izgleda zanemarljiv, obzirom da eksponencijalno raste onemogućava da sva skladišta u celom kraljevstvu ispune zahtev poslednjeg polja od {2^{63}} zrna žita. Sličan neočekivani zaplet imamo i u slučaju Hanojske kule koju poznajemo kao igračku sastavljenu od tri štapa sa diskovima nanizanim po veličini na jedan od štapova. Zadatak je prebaciti sve diskove sa prvog štapa na treći pridržavajući se jednostavnih pravila. U jednom potezu moguće je pomeranje samo jednog diska, i dozvoljeno je samo stavljanje manjeg diska preko većeg. Legenda kaže da u jednom hramu u Hanoju postoji verzija ove igračke sa 64 diska od zlata koje svakodnevno premeštaju monasi hrama sa ciljem da reše ovaj zadatak što bi ujedno dovelo i do smaka sveta. Iako je ovaj zadatak sa 3 diska moguće rešiti u samo 7 poteza, a sa 4 diska u 15, i ovde broj poteza raste eksponencijalno pa 64 diska zahtevaju {2^{64}-1} potez, ili u slučaju jednog poteza u sekundi potrebno je 585 milijardi godina. To ostavlja monasima dovoljno vremena da dobro razmisle da li žele da ispune zadatak do kraja.

Ingmar Bergman – Sedmi pečat

Оставите одговор

Молимо вас да се пријавите користећи један од следећих начина да бисте објавили свој коментар:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се /  Промени )

Google photo

Коментаришет користећи свој Google налог. Одјавите се /  Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се /  Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се /  Промени )

Повезивање са %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.