🔢 Η εικασία του Collatz: Το απλούστερο άλυτο πρόβλημα των Μαθηματικών;

🔢 Η εικασία του Collatz: Δύο απλοί κανόνες, ένα άλυτο μυστήριο

Μπορεί ένα πρόβλημα που καταλαβαίνει εύκολα ακόμη και ένας μαθητής να αντιστέκεται για δεκαετίες στους καλύτερους μαθηματικούς; Η εικασία του Collatz δείχνει ότι μπορεί.

Δεν χρειάζεται παρά να διαλέξουμε έναν θετικό ακέραιο και να εφαρμόζουμε επανειλημμένα δύο στοιχειώδεις κανόνες. Οι αριθμοί άλλοτε μικραίνουν και άλλοτε εκτοξεύονται προς τα πάνω, όμως τελικά φαίνεται ότι όλοι οδηγούνται στο 1. Το «φαίνεται», ωστόσο, απέχει πολύ από το «αποδείχθηκε».

Οι δύο κανόνες

Ξεκινάμε από οποιονδήποτε θετικό ακέραιο \(n\). Έπειτα ορίζουμε τον επόμενο όρο ως εξής:

\[ T(n)= \begin{cases} \dfrac{n}{2}, & \text{αν ο } n \text{ είναι άρτιος},\\[6pt] 3n+1, & \text{αν ο } n \text{ είναι περιττός}. \end{cases} \]

Εφαρμόζουμε ξανά τον ίδιο κανόνα στον αριθμό που προκύπτει και συνεχίζουμε.

Ένα απλό παράδειγμα: ξεκινώντας από το 6

Το 6 είναι άρτιο, οπότε το διαιρούμε με το 2. Το 3 είναι περιττό, άρα το πολλαπλασιάζουμε με το 3 και προσθέτουμε 1:

\[ 6\to3\to10\to5\to16\to8\to4\to2\to1. \]

Χρειάστηκαν μόλις οκτώ βήματα. Αν συνεχίσουμε και μετά το 1, εμφανίζεται ο κύκλος:

\[ 1\to4\to2\to1\to4\to2\to\cdots \]

Τι ακριβώς υποστηρίζει η εικασία;

Για κάθε θετικό ακέραιο \(n\), η επαναλαμβανόμενη εφαρμογή των δύο κανόνων θα οδηγήσει τελικά στο 1.

Η πρόταση είναι γνωστή ως εικασία \(3n+1\), πρόβλημα των Συρακουσών και, σε ορισμένες πηγές, ως πρόβλημα του Ulam ή του Kakutani. Αποδίδεται στον Γερμανό μαθηματικό Lothar Collatz και άρχισε να κυκλοφορεί στα τέλη της δεκαετίας του 1930.

Δοκίμασέ το πριν συνεχίσεις

Ξεκίνησε από τον αριθμό 11 και εφάρμοσε τους δύο κανόνες. Σε πόσα βήματα θα φτάσεις στο 1;

Εμφάνιση λύσης

\[ 11\to34\to17\to52\to26\to13\to40\to20\to10\to5\to16\to8\to4\to2\to1. \]

Η διαδρομή φτάνει στο 1 ύστερα από 14 βήματα.

Η παράξενη περιπέτεια του 27

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

Αυτός ο απρόβλεπτος τρόπος κίνησης έδωσε στις τροχιές του Collatz το παρατσούκλι «ακολουθίες χαλαζιού»: όπως ένας χαλαζόκοκκος μέσα σε ένα σύννεφο ανεβαίνει και κατεβαίνει πολλές φορές, έτσι και οι αριθμοί παρουσιάζουν απότομες ανόδους και πτώσεις.

Δείτε ολόκληρη την τροχιά του 27

27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Γιατί είναι τόσο δύσκολη;

Η δυσκολία βρίσκεται στην εναλλαγή δύο εντελώς διαφορετικών κινήσεων. Η διαίρεση με το 2 μειώνει τον αριθμό, ενώ ο κανόνας \(3n+1\) τον αυξάνει. Για έναν μεμονωμένο αριθμό μπορούμε να ακολουθήσουμε εύκολα την τροχιά. Για όλους τους θετικούς ακεραίους, όμως, πρέπει να αποκλείσουμε δύο ενδεχόμενα:

1. Να υπάρχει κάποιος αρχικός αριθμός του οποίου η τροχιά αυξάνεται χωρίς όριο.

2. Να υπάρχει κάποιος άλλος κύκλος, διαφορετικός από τον \(1\to4\to2\to1\).

Το γεγονός ότι έχουν ελεγχθεί τεράστια πλήθη αριθμών δεν αποκλείει ένα αντιπαράδειγμα πολύ πιο μακριά. Οι φυσικοί αριθμοί είναι άπειροι και κανένας πεπερασμένος υπολογιστικός έλεγχος δεν μπορεί από μόνος του να καλύψει όλους.

Μέχρι πού έχει φτάσει ο υπολογιστικός έλεγχος;

Το αρχικό κείμενο ανέφερε έλεγχο μέχρι το \(2^{58}\). Το όριο αυτό είναι πλέον παλιό. Δημοσιευμένος υπολογιστικός έλεγχος του David Bařina έχει επιβεβαιώσει τη σύγκλιση για όλους τους αρχικούς αριθμούς κάτω από το:

\[ 2^{71}\approx2{,}36\cdot10^{21}. \]

Πρόκειται για περίπου \(2{,}36\cdot10^{21}\) αρχικούς αριθμούς. Το αποτέλεσμα αποτελεί εξαιρετικά ισχυρή αριθμητική ένδειξη, αλλά όχι απόδειξη της εικασίας.

Η μεγάλη πρόοδος του Terence Tao

Το 2019 ο Terence Tao απέδειξε ένα από τα ισχυρότερα γενικά αποτελέσματα που γνωρίζουμε για το πρόβλημα. Με απλουστευμένα λόγια, έδειξε ότι για «σχεδόν όλους» τους αρχικούς αριθμούς —με την τεχνική έννοια της λογαριθμικής πυκνότητας— η τροχιά κατεβαίνει τελικά κάτω από οποιοδήποτε όριο που αυξάνεται προς το άπειρο, όσο αργά κι αν αυξάνεται.

Το θεώρημα δείχνει ότι η συντριπτική πλειονότητα των τροχιών πέφτει πολύ χαμηλά σε σχέση με το σημείο εκκίνησης. Δεν αποδεικνύει, όμως, ότι όλες φτάνουν στο 1 και επομένως δεν λύνει την εικασία.

Ένα απλό ερώτημα που παραμένει ανοιχτό

Η εικασία του Collatz αποτελεί χαρακτηριστικό παράδειγμα της απόστασης ανάμεσα στον πειραματισμό και την απόδειξη. Μπορούμε να γράψουμε ένα μικρό πρόγραμμα, να δοκιμάσουμε δισεκατομμύρια αριθμούς και να δούμε κάθε τροχιά να καταλήγει στο 1. Αυτό μας πείθει ότι η εικασία πιθανότατα είναι αληθινή — δεν μας εξηγεί όμως γιατί πρέπει να ισχύει για κάθε θετικό ακέραιο.

Οι κανόνες χωρούν σε δύο γραμμές. Η απόδειξη δεν έχει βρεθεί εδώ και σχεδόν έναν αιώνα.

Πηγές και έλεγχος στοιχείων: David Bařina, υπολογιστική επαλήθευση μέχρι \(2^{71}\), τρέχον έργο υπολογιστικού ελέγχου, Terence Tao, Almost all orbits of the Collatz map attain almost bounded values.

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →