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

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

Θεωρώντας τις συναρτήσεις $d(x)=2x$ και $t(x)=\dfrac{x-1}{3}$ με την πρώτη ορισμένη για κάθε $x\in\mathbb{N}$ και τη δεύτερη για $x=4,7,10,\ldots$ είναι αλήθεια ότι κάθε θετικός ακέραιος αριθμός $n$ γράφεται στη μορφή $f(1)$ όπου $f$ είναι μία συνάρτηση που προκύπτει από πεπερασμένες στο πλήθος συνθέσεις των $d,t;$

Με τον παραπάνω τρόπο, αντί να ψάχνουμε ξεκινώντας από κάθε αριθμό που μπορεί να μας έρθει στο κεφάλι αν, τελικά, υποδιπλασιάζοντας ή πολλαπλασιάζοντας με το 3 και προσθέτοντας 1, θα καταλήξουμε στη μονάδα, μπορούμε πολύ απλά να ξεκινάμε από τη μονάδα και να κάνουμε διάφορους επιτρεπτούς συνδυασμούς των d και t.

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

$T:=\{3k+1:k=1,2,\ldots\}=\{4,7,10,\ldots\}.$

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

$d\circ t,\ t\circ d.$

Η πρώτη είναι αρκετά απλή, δεδομένου ότι η $d$ ορίζεται για όλους τους θετικούς ακεραίους και η $t$ παίρνει θετικές ακέραιες τιμές – οπότε πάντα έχει νόημα να πούμε $d(t(x))$ για κάθε $x=1,2,\ldots.$ Από την άλλη, η σύνθεση $t\circ d$ θέλει λίγη παραπάνω σκέψη – εντάξει, ίσως όχι και πολλή. Στην ουσία, η παραπάνω σύνθεση έχει νόημα μόνο όταν η τιμή $d(x)$ βρίσκεται στο πεδίο ορισμού της $t.$ Με άλλα λόγια, πρέπει η τιμή της $d$ να είναι κάποιος αριθμός του συνόλου $T.$ Τώρα, δεδομένου ότι το σύνολο τιμών της $d$ είναι το:

$d\left(\mathbb{Z}_+\right)=\{2,4,6,\ldots\},$

το σύνολο των σημείων που μας ενδιαφέρει είναι εκείνοι οι θετικοί ακέραιοι οι οποίοι αν πολλαπλασιαστούν με το 2 τότε μας δίνουν κάποιον αριθμό από το $T$ – έτσι ώστε να μπορεί να έχει νόημα το $t(d(x)).$ Με λίγα παραπάνω σύμβολα, αναζητούμε εκείνα τα $x\in\mathbb{Z}_+$ τα οποία να λύνουν την εξίσωση:

$2x=3k+1,$

για κάποιον θετικό ακέραιο $k.$ Εύκολα βλέπουμε ότι:

$x=\dfrac{3k+1}{2},$

υπό την προϋπόθεση, σαφώς, ότι $\dfrac{3k+1}{2}\in\mathbb{Z}.$ Για να ισχύει αυτό, θα πρέπει (και αρκεί) να είναι ο $3k+1$ άρτιος, επομένως θα πρέπει ο $3k$ να είναι περιττός. Τώρα, δεδομένου ότι γινόμενο αρτίων και γινόμενο άρτιου επί περιττό μας δίνει άρτιο, η μόνη μας επιλογή είναι ο $k$ να είναι περιττός. Έτσι, αν $k=2n+1$ για $n=0,1,\ldots,$ έπεται ότι:

$x=\dfrac{6n+3+1}{2}=\dfrac{6n+4}{2}=3n+2.$

Επομένως, έχουμε ότι το πεδίο ορισμού της $t\circ d$ είναι το:

$S:=\{3n+2:n=0,1,\ldots\}=\{2,5,8,\ldots\}.$

Τώρα, ας δοκιμάσουμε λίγο να κάνουμε ένα ταξίδι ξεκινώντας από το 1 και εφαρμόζοντας διαδοχικά τις $d,t:$

Αρχικά, μπορούμε να εφαρμόσουμε μόνο την $d$ καθώς $1\not\in S.$ Έτσι, παίρνουμε το 2.
Στη συνέχεια, και πάλι μπορούμε να εφαρμόσουμε μόνο την $d,$ οπότε και παίρνουμε το 4.
Ομοίως, εφαρμόζουμε μόνο την $d$ και παίρνουμε το 8.
Ομοίως, εφαρμόζουμε την $d$ και παίρνουμε το 16.
Τώρα, αφού $16\in T,$ έχουμε ένα δίλημμα, αφού μπορούμε να εφαρμόσουμε τόσο την $d$ – αυτό μπορεί να συμβαίνει πάντα – όσο και την $t.$ Ας πούμε ότι επιλέγουμε την $t,$ οπότε παίρνουμε τον αριθμό 5.
Εδώ πάλι μπορούμε να εφαρμόσουμε τόσο την $t$ όσο και την $d.$

Ναι, αλλά δε θα κάτσουμε να παίζουμε και την κολοκυθιά! Σαφώς, δεν είναι λύση το να κοιτάμε απλά αν μπορούμε να εφαρμόσουμε μία ή και τις δύο συναρτήσεις που έχουμε στη διάθεσή μας, γιατί αυτό θα μας οδηγήσει στο να πρέπει να απαριθμήσουμε όλα τα (άπειρα) μονοπάτια που μπορούμε να ακολουθήσουμε.

Οπότε, αφού έχουμε να αντιμετωπίσουμε κάτι τόσο περίπλοκο μπροστά μας, θα προσπαθήσουμε να το «συμπιέσουμε» εντοπίζοντας διάφορα μοτίβα σε αυτό. Για παράδειγμα, όπως είπαμε, η συνάρτηση $t$ μπορεί να εφαρμόζεται μόνο σε αριθμούς που είναι της μορφής $3k+1.$ Αν την εφαρμόσουμε σε έναν τέτοιον αριθμό τότε θα πάρουμε σαν αποτέλεσμα τον αριθμό $k.$ Από εδώ, τώρα, δεν έχουμε και πολλά να πούμε με μια πρώτη ματιά, καθώς δεν έχουμε στα χέρια μας κάποια υπόθεση για τον $k.$ Στην περίπτωση όμως που πετάξουμε την ευκαιρία μας να εφαρμόσουμε την $t,$ η μοίρα θα σταθεί δίκαιη και θα μας δώσει μία άλλη, σχετικά σύντομα. Πράγματι, αν υποθέσουμε ότι έχουμε έναν αριθμό της μορφής $3k+1,$ τότε έχουμε:

$d(3k+1)=6k+2=3(2k)+2\in S.$

Συνεπώς, μπορούμε αν ξαναεφαρμόσουμε την $d$ να βρούμε έναν αριθμό στον οποίον να εφαρμόσουμε την $t$ – καθώς το $S$ είναι το πεδίο ορισμού της $t\circ d.$

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

Αν κάτσουμε λίγο και δούμε ξανά τι έχουμε γράψει παραπάνω, θα δούμε ότι αυτό που λέμε δεν είναι ανέφικτο – αντιθέτως, μάλιστα. Στην ουσία, όλα τα παραπάνω μπορούμε να τα φανταστούμε σαν έναν «περίπατο». Σκεφτείτε ότι πατάμε πάνω σε πλακάκια που γράφουν αριθμούς – θετικούς ακέραιους, για την ακρίβεια – και ότι σε κάθε αριθμό είτε πάμε όπως μας λέει η συνάρτηση $d$ – δηλαδή, στον διπλάσιο – είτε όπως μας λέει η $t,$ αν αυτό είναι επιτρεπτό. Έτσι, μπορούμε να σχηματίσουμε σταδιακά ένα δέντρο με όλες τις δυνατές επιλογές που μπορούμε να κάνουμε στην πορεία μας. Πιο αναλυτικά, ξεκινώντας από το πλακάκι που γράφει 1, τα πρώτα μας βήματα έχουν ως εξής:

Αναγκαστικά, μεταβαίνουμε στο πλακάκι με αριθμό 2.
Αναγκαστικά, μεταβαίνουμε στο πλακάκι με αριθμό 4.
Αναγκαστικά, μεταβαίνουμε στο πλακάκι με αριθμό 8.
Αναγκαστικά, μεταβαίνουμε στο πλακάκι με αριθμό 16.
Εδώ έχουμε την πρώτη μας διακλάδωση στο δέντρο μας:
- είτε μεταβαίνουμε στο πλακάκι με αριθμό 32,
- είτε μεταβαίνουμε στο πλακάκι με αριθμό 5.

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

Ένα τέτοιο θα στολίσουμε τα Χριστούγεννα!

Ωραίο δεντράκι αυτό. Μπορούμε, μάλιστα, να συνεχίσουμε λίγο ακόμα τον περίπατό μας. Για την ακρίβεια, από το πλακάκι 5 μπορούμε να ακολουθήσουμε την εξής διαδρομή μέχρι την επόμενη στάση μας:

Αναγκαστικά, μεταβαίνουμε στο πλακάκι με αριθμό 10.
Εδώ έχουμε και πάλι δύο επιλογές:
- είτε να μεταβούμε στο πλακάκι με αριθμό 20,
- είτε να μεταβούμε στο πλακάκι με αριθμό 3.

Από το πλακάκι 32, από την άλλη, έχουμε τις εξής επιλογές:

Αναγκαστικά, μεταβαίνουμε στο πλακάκι 64.
Εδώ έχουμε ξανά δύο επιλογές:
- είτε να μεταβούμε στο πλακάκι με αριθμό 128,
- είτε να μεταβούμε στο πλακάκι με αριθμό 21.

Με αυτές τις νέες πληροφορίες μας, ο χάρτης μας έχει την εξής μορφή:

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

Μέχρι την άλλη Παρασκευή, καλή διασκέδαση!

Η κεντρική εικόνα είναι ο πίνακας Το κάρο με τα άχυρα, Montfoucault του Camille Pissarro.

Σαφώς, αν μετά από 84 χρόνια η μαθηματική κοινότητα δεν έχει αποφανθεί για το τι συμβαίνει, δεν προσδοκά το aftermaths να δώσει τη λύση. Ωστόσο, οι τομείς των μαθηματικών που δείχνουν με μία πρώτη ματιά σχετικοί με την παραπάνω εικασία είναι ιδιαίτερα ενδιαφέροντες και η παραπάνω εικασία είναι μία καλή και απλή αφορμή για να ασχοληθούμε μαζί τους. Σε αυτή τη σειρά, λοιπόν, με αφορμή την εικασία του Collatz, θα εξερευνάμε σε σχεδόν καθημερινό επίπεδο μικρά ψήγματα μαθηματικών και απλές – ή και όχι τόσο απλές – σκέψεις και ιδέες πάνω σε ένα ανοικτό πρόβλημα.

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

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

One comment

Ο/Η Η εικασία Collatz (4) – aftermaths.gr λέει:

18 Σεπτεμβρίου 2021 στο 01:21

[…] παρουσιάσει – για μία γρήγορη υπενθύμιση, δείτε εδώ και για όλες τις δημοσιεύσεις της σειράς δείτε εδώ. Να […]

Μου αρέσει!Μου αρέσει!

Απάντηση