Το ατομικό παιχνίδι « Ο Πύργος του Ανόι » που κυκλοφορεί στο εμπόριο, αποτελείται από τρεις κατακόρυφους άξονες Α,  Β, και Γ και μερικούς άνισου μεγέθους δίσκους. Στο σχ. 1 υπάρχουν 4 δίσκοι, αριθμημένοι, με τους αριθμούς 1, 2, 3, και 4 κατά σειρά μεγέθους από τον μικρότερο προς τον μεγαλύτερο. Είναι τοποθετημένοι σε σχήμα πύργου, στον άξονα Α. Το πρόβλημα είναι το εξής: Να μεταφερθεί ο Πύργος από τη θέση Α στη θέση Β ή στη θέση Γ, χρησιμοποιώντας την τρίτη θέση σαν βοηθητική, και μετακινώντας κάθε φορά μόνο ένα δίσκο, αλλά με τον περιορισμό πως δεν μπορεί να τοποθετηθεί ένας μεγαλύτερος δίσκος πάνω σ’ ένα μικρότερο. Το παιχνίδι που κυκλοφορεί στην αγορά έχει 7 δίσκους.

Ιστορική παρένθεση
Το παιχνίδι ονομάσθηκε « Πύργος του Ανόι » από το σχήμα του πύργου που θυμίζει την αρχιτεκτονική των ναών στις χώρες της Άπω ανατολής.
Το παιχνίδι πρωτοεμφανίστηκε από τον Γάλλο μαθηματικό Έντουαρτ Λούκας γύρω στα 1883 με προέλευση μάλλον από τις Ινδίες.
Υπάρχει για το παιχνίδι ο παρακάτω θρύλος με τίτλο « Πύργος του Βράχμα »
«Όταν ο Βράχμα δημιούργησε τον κόσμο, έστησε σένα ναό στην πόλη Μπενάρες,  64 δακτυλίδια άνισου μεγέθους όλα περασμένα σένα μπαστούνι έτσι ώστε αν κρατήσουμε το μπαστούνι κατακόρυφα να σχηματίζουν τον γνωστό μας πύργο
Oι ιερείς του ναού έπρεπε να δουλεύουν μέρα νύχτα, χωρίς σταμάτημα, για να μεταφέρουν τα δακτυλίδια σένα άλλο μπαστούνι, χρησιμοποιώντας  ένα τρίτο σαν βοηθητικό, έτσι ώστε να μην τοποθετήσουν μεγαλύτερο δακτυλίδι πάνω από μικρότερο και μετακινώντας ένα μόνο δακτυλίδι σε κάθε κίνηση.
Ο θρύλος λεει πως πριν προλάβουν οι ιερείς να μεταφέρουν όλα τα δακτυλίδια στο άλλο μπαστούνι, ο ναός θα καταρρεύσει μέσα στην σκόνη και ο κόσμος θα χαθεί μέσα σε τρομακτικό κρότο βροντής».

Είχε άραγε ο Βράχμα δίκιο; (Την απάντηση θα δούμε παρακάτω)

Μπορεί ένας παίκτης ν' αρχίζει να παίζει και κά­ποτε να καταφέρει να τοποθετήσει τον πύργο στη θέση Β ή Γ, θα έχει κάνει όμως τον ελάχι­στο αριθμό κινήσεων; Ποίος είναι αυτός o αριθμός;

Άρα έχουμε το πρόβλημα.
1. Να υπο­λογιστεί ο ελάχιστος αριθμός κινήσεων που πρέπει να κάνει ο παίκτης ώστε να μετακινήσει τον πύργο από την θέση Α στην θέση Β ή Γ όταν οι δίσκοι είναι ορισμένου πλήθους ν (ν φυσικός - π.χ. 7 δίσκοι)
2. Ποιες κινήσεις πρέπει να γίνουν και με πια τακτική για να πετύχουμε την λύση με τον ελάχιστο αριθμό κινήσεων;
Θα προσεγγίσουμε την λύση «επαγωγικά» αρχίζοντας με ένα δίσκο και αυξάνοντας το πλήθος των δίσκων σταδιακά.

Α) Όταν ο δίσκος είναι ένας τότε ο αριθμός των κινήσεων προφανώς είναι μια.

Β) Όταν οι δίσκοι είναι δύο τότε ο αριθμός των κινήσεων είναι τρεις. [βλέπε εικόνα]

Γ) Όταν οι δίσκοι είναι τρεις τότε ο αριθμός των κινήσεων είναι επτά.[βλέπε εικόνα]

Παρατηρούμε ότι ο πύργος των δύο δίσκων έχει πρώτα μεταφερθεί στην θέση Γ ( 3 κινήσεις ) μετά έγινε η μεταφορά του τρίτου δίσκου στην θέση Β ( 1 κίνηση ) και μετά μεταφέρθηκε ξανά στην θέση Β ( 3 κινήσεις ).

Δ) Όταν οι δίσκοι είναι τέσσερις τότε ο αριθμός των κινήσεων είναι δεκαπέντε.[βλέπε εικόνα]

Παρατηρούμε την μεταφορά του πύργου των τριών δίσκων στην θέση Γ ( 7 κινήσεις ) μετά την μεταφορά του τέταρτου δίσκου στην θέση Β ( 1 κίνηση ) και τέλος την μεταφορά του πύργου των τριών δίσκων στην θέση Β ( 7 κινήσεις ) σύνολο 15 κινήσεις. Συνεχίζοντας με τον ίδιο τρόπο και αυξάνοντας κατά ένα τον αριθμό των δίσκων θα έχουμε :

Α. Ως προς την τεχνική που θα ακολουθήσουμε για την εκτέλεση των κινήσεων.

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

Β. Ως προς τον υπολογισμό των ελαχίστων κινήσεων:

Άρα το πλήθος των ελαχίστων κινήσεων για 7 δίσκους είναι 127. (Μερική απάντηση στο 1^ο ερώτημα για 7 δίσκους)

 Πώς όμως θα υπολογίσουμε τον αριθμό των ελαχίστων κινήσεων όταν ο αριθμός των δίσκων είναι πολύ μεγάλος; Ο παραπάνω υπολογισμός σημαίνει ότι πρέπει να βρούμε πρώτα το πλήθος για ένα δίσκο λιγότερο, και πριν για δύο λιγότερους κ. ο. κ. πράγμα που κάνει τον υπολογισμό αρκετά δύσκολο και όσο πιο μεγάλος είναι ο αριθμός των δίσκων τόσο ο υπολογισμός γίνεται πολύ δύσκολος σχεδόν αδύνατος.

 Θα δείξουμε με την μέθοδο της επαγωγής* ότι το πλήθος των κινήσεων δίνεται από τον τύπο

Πλήθος κινήσεων  για ν δίσκους  = 2^ν – 1
Απόδειξη
Για  ν = 1 Π(1) = 2¹ -  1 = 2 – 1 = 1 ( ισχύει )
Έστω ότι ισχύει για ν = ρ δηλαδή το πλήθος των κινήσεων με ρ δίσκους Π(ρ) =  2^ρ -  1
Τότε σύμφωνα με τα παραπάνω πλήθος των κινήσεων με ρ+1 δίσκους
Π(ρ+1) =  Π(ρ) +1+ Π(ρ) = (2^ρ -  1) + 1 + (2^ρ -  1) = 2. 2^ρ -  1 = 2^ρ+1 -  1
άρα ισχύει και για ν = ρ+1 άρα θα ισχύει για κάθε ν.

  Άρα απαντήσαμε και στο 1^ο  ερώτημα :
Πλήθος των κινήσεων με ν δίσκους Π(ν)  = 2^ν -  1

 *Θεώρημα επαγωγής ·       Αν  μια πρόταση Π(ν), ν φυσικός , ισχύει για ν = 1 και δεχόμενοι ότι ισχύει για  ν = ρ  αποδείξουμε ότι ισχύει και για  ν = ρ+1 τότε ισχύει για κάθε  ν.

Για να δούμε τώρα αν ο Βράχμα είχε δίκιο
Οι ελάχιστες κινήσεις που πρέπει να γίνουν σύμφωνα  με την απόδειξη παραπάνω είναι :
Π(64) = 2⁶⁴ – 1 = 18.446.744.073.709.551.615
Αν οι ιερείς κάνουν μία κίνηση κάθε δευτερόλεπτο τότε θα χρειασθούν: 18.446.744.073.709.551.615 δευτερόλεπτα, άρα επειδή ένας χρόνος έχει 365 ημέρες, 365*24 =  8760 ώρες, 8760*60  =  525600 λεπτά, 525600*60 = 31536000 δευτερόλεπτα.
 Τότε θα χρειασθούν 18446744073709551615 / 31.536.000 = 584.942.417.355 χρόνια περίπου 600 δισεκατομμύρια χρόνια για να ολοκληρωθούν οι κινήσεις.
Όμως η επιστήμονες αστρονόμοι υπολογίζουν ότι ο Ήλιος μας έχει ακόμη ζωή για 5 δισεκατομμύρια χρόνια πριν καταρρεύσει και συμπαρασύρει μαζί στην καταστροφή και όλο το πλανητικό σύστημα.

Άρα ο Βράχμα είχε απόλυτα δίκιο.

Θα μπορούσαμε να εξετάσουμε και το εξής ερώτημα : Πόσα θα έπρεπε να είναι το πολύ τα δακτυλίδια ώστε οι ιερείς να προφθάσουν να τα μετακινήσουν πριν καταστραφεί ο κόσμος; ( Απάντηση:  ν  =  57 )