Δευτέρα, 11 Μαΐου 2009

ΟΙ ΠΥΡΓΟΙ ΤΟΥ ΑΝΟΪ ΚΑΙ ΤΟ ΤΕΛΟΣ ΤΟΥ ΚΟΣΜΟΥ

Το παζλ με τους πύργους του Ανόϊ επινοήθηκε από τον Γάλλο μαθηματικό François Édouard Anatole Lucas to 1883.

Ο θρύλος που το συνοδεύει μας ταξιδεύει στην Ινδία και λέει ότι στον μεγάλο ναό του Βράχμα στις Μπενάρες, πάνω σ' ένα μπρούτζινο βάθρο που είναι το κέντρο του κόσμου βρίσκονται 64 χρυσοί δίσκοι που σχηματίζουν ένα πύργο. Στην βάση είναι ο μεγαλύτερος δίσκος και στην κορυφή ο μικρότερος.
Οι δίσκοι είναι διάτρητοι και διαπερνώνται από τρεις διαμαντένιους άξονες.



(Στην φωτογραφία απεικονίζεται ο γρίφος με 8 αντί για 64 δίσκους).

Οι ιερείς του ναού κουβαλούν ένα δίσκο κάθε φορά χρησιμοποιώντας και τους τρεις άξονες και προσπαθούν να μεταφέρουν τον πύργο, δηλαδή και τους 64 δίσκους από τον πρώτο στον τρίτο άξονα σύμφωνα με τις εντολές του Βράχμα-ως εξής:



  • Οι δίσκοι μπορούν να μεταφερθούν σε οποιοδήποτε άξονα αλλά μόνο ένας δίσκος κάθε φορά


  • Κανένας δίσκος δεν μπορεί να τοποθετηθεί πάνω από μικρότερό του.



Για να γίνει η μεταφορά τηρώντας αυτή την προϋπόθεση, υποχρεωτικά θα χρησιμοποιηθούν και οι τρείς άξονες.

Αρχικά, όταν ο Βράχμα δημιούργησε τον κόσμο όλοι οι δίσκοι ήταν περασμένοι στον ίδιο άξονα. Σήμερα, με την μεταφορά των δίσκων από τους ιερείς βρισκόμαστε περίπου στα μισά της προσπάθειας. Και το συνταρακτικό:

Όταν όλοι οι δίσκοι έχουν μεταφερθεί στον τρίτο άξονα θα έρθει το τέλος του κόσμου και όλα θα γίνουν σκόνη.

Μην αγχώνεσθε όμως.

Για να υπολογίσετε τον ελάχιστο αριθμό μετακινήσεων δίσκων και τελικά να υπολογίσετε τον χρόνο της καταστροφής, πρέπει να κατανοήσετε τον μηχανισμό της μεταφοράς των δίσκων.

Προσπαθήστε να κάνετε την μεταφορά ξεκινώντας αρχικά με 3 δίσκους.




ΛΥΣΗ (πιο κάτω):






Αν οι τρείς άξονες είναι από αριστερά Α, Β και Γ και οι δίσκοι από τον μεγαλύτερο στον μικρότερο είναι 1, 2 και 3 τότε θα είναι:

ΑΡΧΗ=Α123 -Β0(κενό) -Γ0 (κενό)

>ΚΙΝΗΣΕΙΣ>

Γ3 (δίσκος 3 στον άξονα Γ) - [Κατάσταση Δίσκων Α12-Β0-Γ3]
Β2 (δίσκος 2 στον άξονα Β) - [Κατάσταση Δίσκων Α1-Β2-Γ3]
Β23 (δίσκος 3 στον άξονα Β που υπάρχει ήδη ο δίσκος 2 > προσοχή ο δίσκος 2 δεν μπορεί να πάει στον άξονα Γ δηλ Γ32 γιατί από κάτω θα είναι ο μικρότερος δίσκος 3) - [Α1-Β23-Γ0]
Γ1 - [Α0-Β23-Γ1]
Α3 - [Α3-Β2-Γ1]
Γ12 - [Α3-Β0-Γ12]
Γ123 ΤΕΛΙΚΗ ΚΙΝΗΣΗ ΚΑΙ ΟΛΙΚΗ ΜΕΤΑΦΟΡΑ ΤΟΥ ΠΥΡΓΟΥ ΤΩΝ 3 ΔΙΣΚΩΝ


Ο ελάχιστος αριθμός κινήσεων (Kmin) για μεταφορά πύργου με (n) δίσκους δίνεται από τον τύπο:

Kmin = 2^n - 1 (δύο στην n-ιοστή δύναμη πλήν 1)

Για n=3 τότε Kmin =7

Για n=4 τότε Kmin=15

Όπως θα καταλάβατε, μπορούμε να κοιμόμαστε ήσυχοι προς το παρόν, γιατί οι κινήσεις που χρειάζονται για να μεταφερθούν και οι 64 δίσκοι σύμφωνα με τις εντολές του Βράχμα είναι 2^64-1 δηλαδή
18 446 744 073 709 551 615
που αντιστοιχεί σε διάστημα μεγαλύτερο από πέντε δισεκατομμύρια αιώνες ακόμα και στην περίπτωση που κάθε μετακίνηση δίσκου γίνεται σε χρόνο ενός δευτερολέπτου!!!
του φεΖ ;-)


Περισσότερες πληροφορίες στην διεύθυνση:

http://www.mazeworks.com/hanoi/index.htm

Δεν υπάρχουν σχόλια:

Google+ Followers

Translate

Αναγνώστες