Η εικασία Collatz (8)

Την προηγούμενη εβδομάδα ασχοληθήκαμε αρκετά με μία εναλλακτική προσέγγιση της εικασίας Collatz, η οποία βασίζεται σε μία επαγωγική ιδέα. Για την ακρίβεια, είπαμε ότι αν καταφέρουμε και αποδείξουμε ότι από όποιον αριθμό κι αν ξεκινήσουμε, μετά από πεπερασμένο πλήθος βημάτων καταλήγουμε σε έναν αριθμό μικρότερο από τον αρχικό μας όρο, τότε η εικασία Collatz είναι αληθής. Έτσι, αντί να μελετούμε αν τελικά μία ακολουθία καταλήγει στο 1, αρκεί να εξετάζουμε αν όλες οι ακολουθίες Collatz καταλήγουν σε έναν όρο μικρότερο από τον αρχικό τους.

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

Με απλά βήματα…

Ξεκινώντας από πιο ήπιους στόχους, αρχικά θα ασχοληθούμε με τους αριθμούς της μορφής $4k-1$ καθώς, όπως έχουμε δει, αυτοί οι αριθμοί δεν οδηγούν με κάποιον προφανή τρόπο σε κάποιον αριθμό μικρότερο από αυτούς. Για την ακρίβεια, τα πρώτα βήματα κάθε ακολουθίας Collatz που ξεκινάει από έναν τέτοιον αριθμό είναι τα εξής:

«τριπλασιασμός»,
υποδιπλασιασμός,
«τριπλασιασμός»,
υποδιπλασιασμός.

Αυτά μας οδηγούν, τελικά, στον αριθμό $9k-1$ ο οποίος είναι περίπου $\dfrac{9}{4}$ φορές μεγαλύτερος από τον αρχικό – και άρα έχουμε δουλειά να κάνουμε…

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

Εικασία Collatz — Μπλε = «τριπλασιασμός», κόκκινο = υποδιπλασιασμός.

Στο παραπάνω σχήμα βλέπουμε, αρχικά, ότι πράγματι αν ξεκινήσουμε από έναν αριθμό της μορφής $4k-1$ τότε κάνουμε τα τέσσερα πρώτα βήματα που είπαμε παραπάνω. Γι’ αυτό και στο σχήμα μας δημιουργούνται 4 στήλες, εναλλάξ μπλε και κόκκινες. Μετά, δεδομένου ότι ένας αριθμός της μορφής $9k-1$ είναι είτε άρτιος είτε περιττός ανάλογα με το τι είναι ο $k,$ έχουμε αυτό το εναλλάξ μοτίβο στην πέμπτη στήλη – άλλοτε μπορούμε να υποδιπλασιάσουμε κι άλλοτε όχι. Πιο μετά έχουμε ένα ακόμα πιο περίπλοκο μοτίβο, το οποίο έχει μέσα και κενά – αφού υπάρχουν ακολουθίες πράξεων που τερματίζουν στο πέμπτο βήμα. Στην έβδομη στήλη επίσης μπορούμε να παρατηρήσουμε ένα μοτίβο, το ίδιο και στην όγδοη, και ίσως και στις επόμενες – απλά μπορεί το «δείγμα» των εκατό σημείων που έχουμε να μην επαρκεί για να παρατηρήσουμε πράγματι αυτά τα μοτίβα.

Για παράδειγμα, αν σχεδιάσουμε 200 τέτοιες περιπτώσεις αντί για 100, τότε μπορούμε να εντοπίσουμε πιο εύκολα και άλλα μοτίβα σε μεγαλύτερες στήλες:

Αλλά, θα κάτσουμε να αναλύσουμε άπειρα στο πλήθος μοτίβα, με την ελπίδα ότι θα βγάλουμε άκρη; Ίσως και ναι – αν, για παράδειγμα, παρατηρήσουμε ότι κι αυτά με τη σειρά τους έχουν κάποιο μοτίβο με το οποίο εμφανίζονται. Ωστόσο, πριν από αυτό ίσως έχει νόημα να ακολουθήσουμε μία πιο αφηρημένη προσέγγιση στο ζήτημά μας. Όπως είπαμε, δοθέντος ενός αριθμού της μορφής $n=4k-1$ θέλουμε να δούμε αν μετά από πεπερασμένο πλήθος βημάτων θα καταλήξουμε σε αριθμό μικρότερο του $n.$ Οι πράξεις που κάνουμε είναι, δύο, όπως έχουμε επίσης, με τη μία να μεγαλώνει τους όρους που έχουμε στη διάθεσή μας και την άλλη να τους μικραίνει. Αν, «μπακάλικα», πούμε ότι ένας «τριπλασιασμός» είναι τριπλασιασμός, δηλαδή ότι $3n+1\approx 3n,$ τότε, μετά από $x$ τριπλασιασμούς και $y$ υποδιπλασιασμούς, ο $x+y-$ οστός όρος της ακολουθίας μας θα είναι, περίπου, ο εξής:

$c_{x+y}\approx\dfrac{3^x}{2^y}n.$

Επομένως, αν θέλουμε κάποτε να καταλήξουμε σε έναν όρο κάτω από το $n$ θα πρέπει, τελικά, οι υποδιπλασιασμοί και οι «τριπλασιασμοί» μας να ικανοποιούν την ακόλουθη σχέση (περίπου):

$\dfrac{3^x}{2^y}n<n\Leftrightarrow 3^x<2^y.$

Τώρα, αυτή είναι μία συμπαθητική σχέση ανάμεσα σε δύο εκθετικές συναρτήσεις. Υψώνοντας στην $\frac{1}{y}$ – δηλαδή, παίρνοντας $y-$ οστές ρίζες – παίρνουμε το εξής:

$3^{x/y}<2\Leftrightarrow \dfrac{x}{y}<\log_32.$

Τώρα, αν ανοίξουμε μία αριθμομηχανή δε θα βρούμε εύκολα λογαρίθμους με βάση 3, ωστόσο, γνωρίζουμε τον αγαπητό μας τύπο αλλαγής βάσης:

$\log_32=\dfrac{\ln2}{\ln3}\approx0.6309.$

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

Σαφώς, το παραπάνω δεν μπορούμε κάπως να το υπολογίσουμε, αλλά μπορούμε σίγουρα να δοκιμάσουμε διάφορες περιπτώσεις. Αντί, όμως, να δοκιμάσουμε για κάθε αριθμό ξεχωριστά θα προσπαθήσουμε να υπολογίσουμε κατά «μέσο όρο» τι συμβαίνει. Με τον συμβολισμό των παραπάνω μπλε-κόκκινων σχημάτων, αυτό που θέλουμε είναι οι μπλε κουκκίδες να είναι περίπου το 63,09% των κόκκινων. Έτσι, με τη βοήθεια του ακόλουθου script, υπολογίζουμε για διάφορα τέτοια σχήματα τον παραπάνω λόγο και τον σχεδιάζουμε, συναρτήσει του πλήθους των αριθμών που αφορά το σχήμα:

def blue_red_ratio(n):
    blue = 0
    red = 0
    for i in range(n):
        k = 4 * i + 3
        (next, op) = next_collatz(k)
        while next >= k:
            if op == 0:
                red += 1
            else:
                blue += 1
            (next, op) = next_collatz(next)
    return blue / red

def plot_blue_red_ratio(n):
    ratios = []
    for i in range(1, n + 1):
        ratios.append(blue_red_ratio(i))
    plt.plot([x for x in range(1, n + 1)], ratios, 'b-', label="blue/red ratio")
    plt.xlabel('# of numbers of the form $4k-1$ checked')
    plt.ylabel('blue/red ratio')
    plt.grid()
    plt.plot([1, n], [0.6309, 0.6309], 'r-', label='y=0.6309')
    plt.legend()
    plt.show()

if __name__ == '__main__':
    n = 20
    plot_blue_red_ratio(n)

Με τη βοήθεια του παραπάνω, σχεδιάζουμε το ακόλουθο σχήμα:

Αλλά, τι να μας κάνουν μόνο 20 περιπτώσεις. Ας δούμε πώς πάει η κατάσταση όταν έχουμε μέχρι και 1000 αριθμούς:

Η αλήθεια είναι ότι δεν παρατηρούμε ο λόγος των «τριπλασιασμών» προς τους υποδιπλασιασμούς να συγκλίνει προς τα εκεί που θα θέλαμε. Αλλά αυτό δεν είναι απαραίτητα αποθαρρυντικό καθώς όλοι οι παραπάνω υπολογισμοί, ανεξάρτητα από το φαινομενικά «ακριβές» αποτέλεσμα 0,6309, έγινα στο «περίπου». Αυτό που έχει ιδιαίτερο ενδιαφέρον είναι ότι πράγματι, ο λόγος των «τριπλασιασμών» προς τους υποδιπλασιασμούς που χρειαζόμαστε στη δύσκολη περίπτωση των αριθμών $4k-1$ δείχνει, τελικά, να σταθεροποιείται σε κάποια τιμή σχετικά κοντά (ας πούμε) σε αυτήν που θα θέλαμε – περίπου.

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

Με τι πιθανότητα, ξεκινώντας από έναν αριθμό, καταλήγουμε με «βήματα Collatz» σε έναν μικρότερο αριθμό;

Με αυτό το ερώτημα θα κλείσουμε τις σκέψεις μας αυτήν την εβδομάδα. Για περισσότερα, αναμείνατε την επόμενη ανάρτηση της σειράς!

Μέχρι τότε, καληνύχτα!

Η κεντρική εικόνα είναι ο πίνακας Στο τραπέζι του Henri Fantin-Latour.

Διαβάστε επίσης: Τι λέει το Θεώρημα του Bolzano;

Ακολουθήστε το aftermathsgr στα social media: