Το «πρόβλημα 3n+1» (η εικασία του Collatz)

Χάρτης fractal της εικασίας Collatz γύρω από τον οριζόντιο άξονα των πραγματικών αριθμών

Καμιά φορά τα πιο απλά ερωτήματα είναι πολύ δύσκολο να απαντηθούν. Ας δούμε ένα διάσημο παράδειγμα. Ο καθένας μπορεί να το τσεκάρει χρησιμοποιώντας μολύβι και χαρτί ή ακόμα και ένα απλό υπολογιστή τσέπης. Είναι τόσο απλό στην διατύπωση εξαιρετικά δύσκολο όμως να αποδειχθεί. Το είδος του προβλήματος που νομίζουμε ότι γνωρίζουμε την απάντηση αλλά δεν μπορούμε να το αποδείξουμε.

Σκεφτείτε έναν θετικό ακέραιο αριθμό, όποιον εσείς θέλετε. Ακολουθείστε τώρα την εξής διαδικασία.

• Αν ο αριθμός είναι άρτιος (ζυγός), διαιρέστε τον με το 2.
• Αν ο αριθμός είναι περιττός (μονός), πολλαπλασιάστε τον με το 3 και προσθέστε το 1.

ή αλλιώς:

Παρατηρείστε το αποτέλεσμα:
Π.χ. ότι σκεφτήκαμε το 11. Είναι περιττός, άρα πολλαπλασιάζουμε με 3 και προσθέτουμε 1, ο επόμενος αριθμός είναι 3Χ11+1=34, ο 34 τώρα είναι άρτιος άρα διαιρούμε με το 2 και έχουμε αποτέλεσμα 17. Ειναι περιττός και συνεχίζουμε τριπλασιάζοντας και προσθέτοντας την μονάδα, 3Χ17+1=52. Συνεχίζουμε την ιδία διαδικασία και οι αριθμοί που προκύπτουν είναι 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Από το σημείο αυτό και μετά έχουμε την επαναλαμβανόμενη ακολουθία 4,2,1,4,2,1,4,2,1…..
Άρα θεωρούμε ότι όταν φτάσουμε στο 1 σταματάμε.

Δείτε την αλυσίδα των αριθμών

11->43->17->52->26->13->40 ->20 ->10->5->16->8->4->2->1

Το πρόβλημα τέθηκε το 1936 από τον μαθηματικό Lothar Collatz, ο όποιος αναρωτήθηκε:
«Θα καταλήγουμε πάντα στο 1, από όποιον αριθμό και αν ξεκινήσουμε;».

Αυτό έχει επαληθευτεί αριθμητικά για τους αριθμούς μέχρι και τον 5,76 x 10¹⁸ (περίπου 6 δισεκατομμύρια δισεκατομμύρια), αλλά χωρίς αναλυτική μαθηματική απόδειξη. Και υπάρχει πάντα η πιθανότητα  ένας απίστευτα μεγάλος αριθμός να παραβιάσει την εικασία Collatz.

Μία σύντομη αναδρομή

Ο οριζόντιος άξονας αντιστοιχεί στον άξονα των ακέραιων μεταξύ 100 και 10000 χωρισμένο σε διαδοχικές πενηντάδες (2000 πενηντάδες ακέραιων). Για καθεμία πενηντάδα αντιστοιχεί και μία τιμή στη συνάρτηση. Η τιμή της συνάρτησης φαίνεται στον κάθετο άξονα και αντιστοιχεί στη μέση τιμή του μήκους που έχουν οι ακολουθίες των ακέραιων της εκάστοτε πενηντάδας. Παρατηρούμε ότι υπάρχει μία γενική αυξητική τάση του πλήθους των στοιχείων μιας ακολουθίας, που όμως περιέχει έντονες αυξομειώσεις.

Η καταγωγή του προβλήματος δεν είναι γνωστή με βεβαιότητα. Το σίγουρο είναι ότι για πολύ καιρό κυκλοφορούσε στους μαθηματικούς κύκλους και ιδιαίτερα μεταξύ μαθηματικών που δούλευαν στη θεωρία αριθμών. Ο ίδιος ο Collatz από τα φοιτητικά του χρόνια έδειξε ενδιαφέρον για το πρόβλημα από τις αρχές της δεκαετίας του 1930 και από ότι φαίνεται αναφερόταν ήδη στις διαλέξεις των Edmund Landau, Oskar Perron και Issai Schur.

Η πρώτη γραπτή εμφάνιση του προβλήματος υπάρχει στο σημειωματάριό του με ημερομηνία 1η Ιουλίου 1930 και δεν δημοσίευσε ποτέ κάποιο σχετικό άρθρο με το πρόβλημα παρά μόνο το κυκλοφόρησε προφορικά στο διεθνές συνέδριο μαθηματικών στο Cambridge το 1950. Στα πρακτικά του συνεδρίου εμφανίζεται και το πρόβλημα.

Στα επόμενα χρόνια το πρόβλημα γίνεται ιδιαίτερα δημοφιλές. O Hasse συζητούσε με διάφορους άλλους μαθηματικούς πιθανές γενικεύσεις, ενώ ο Kakutani ευθύνεται σε μεγάλο βαθμό για τη διάδοσή του, που είχε λάβει διαστάσεις επιδημίας! Χαρακτηριστική είναι η μαρτυρία του Kakutani  ότι «Για έναν περίπου μήνα όλος ο κόσμος στο Yale δούλευε πάνω στο πρόβλημα χωρίς αποτέλεσμα». Εκτός από τον Kakutani στο πανεπιστήμιο του Chicago ο Lagarias φρόντισε να μεταδώσει την επιδημία του προβλήματος χωρίς πάλι κανένα αποτέλεσμα. Κυκλοφορούσε μάλιστα και ένα αστείο πως το πρόβλημα ήταν κομμάτι μιας συνωμοσίας που είχε σκοπό να καθυστερήσει τη μαθηματική έρευνα στις Η.Π.Α.

Οι ακολουθίες των ακεραίων που έχουν ως αρχική τους τιμή μεγαλύτερους ακέραιους δεν μεταβάλλεται σε πλήθος αρκετά. Μέχρι που φτάνουμε στον αριθμό 27 όπου δημιουργείται μία ακολουθία με 111 ακέραιους και μέχρι να καταλήξει στο 1 έχει φτάσει μέχρι και το 9232. Ωστόσο, όσο μεγάλες κι αν είναι αυτές οι ακολουθίες, πάντοτε φαίνεται να τερματίζουν στον 1.

Το 2011, ο Gerhard Opfer του Πανεπιστημίου του Αμβούργου – που υπήρξε και μαθητής του Collatz – παρουσίασε μία απόδειξη της εικασίας (βλ. εδώ) που είχε όμως σημαντικά κενά, τα οποία επεσήμαναν διάφοροι μαθηματικοί στο διαδίκτυο, οπότε και την απέσυρε (τουλάχιστον προσωρινά).

Δεν είναι τυχαίο που ο διάσημος Ούγγρος μαθηματικός Πολ Έρντος, όταν ξεκίνησε να ασχολείται με το πρόβλημα, κατέληξε στο συμπέρασμα ότι τα μαθηματικά δεν είναι ακόμη έτοιμα για να προσεγγίσουν τέτοιου είδους προβλήματα…

Κλικ εδώ για να δείτε και μόνοι σας τα βήματα που χρειάζεται οποιοσδήποτε αριθμός για να φτάσει στο 1 με βάση το πρόβλημα του 3n+1.