Δευτέρα, 16 Απριλίου 2012

Το μπλουζάκι του Περικλή

Ο συνάδελφος Περικλής, καθηγητής Πληροφορικής, έχει πολύ ενδιαφέροντα μπλουζάκια από μαθηματική άποψη, το καθένα και ένα ωραίο πρόβλημα.
Εκείνο το πρωινό, στάθηκα αρκετή ώρα μπροστά του, προσπαθώντας να αποκωδικοποιήσω το δέντρο με τους αριθμούς. Στην βάση ήταν η μονάδα και μετά το 2, το 4, το 8, το 16,... Υπέθεσα ότι οι αριθμοί διπλασιάζονταν. Όμως το 5 μετά το 16 μου "χαλούσε" αυτόν τον υπέροχο κανόνα. Το ίδιο συνέβαινε και μετά: ενώ ακολουθούσαν μερικά βήματα διπλασιασμού, ξαφνικά, "πέφταμε" σε μικρότερο αριθμό: 5, 10, 20, 40, 80, 160, 53...

Δεν μπορούσα να εντοπίσω κάποια σχέση. Του ζήτησα να κάνει μεταβολή να δω και την πίσω όψη της μπλούζας. Εκεί υπήρχε ένας κανόνας, που ο Περικλής ψιθύρισε πως ήταν το "σκονάκι" της γριφώδους μπλούζας του: Αν ο Ν είναι άρτιος, τότε Ν=Ν/2. Αν ο Ν είναι περιττός, τότε Ν=3Ν+1.

Τότε μόνο κατάλαβα ότι διάβαζα "ανάποδα" το δέντρο. Δεν έπρεπε να ξεκινώ από την ρίζα του, αλλά από τις πάνω άκρες των κλώνων του, που κάθεμιά φιλοξενούσε και έναν τυχαίο φυσικό αριθμό. Αν ο αριθμός ήταν άρτιος, ο αμέσως πιο κάτω ήταν το μισό του, ενώ αν ήταν περιττός, ο αμέσως πιο κάτω ήταν ο τριπλάσιός του αυξημένος κατά μια μονάδα. Με αυτόν τον τρόπο δημιουργείται μια ακολουθία αριθμών, ο κλώνος ολόκληρος.
Αλλά δεν θα είχαμε το μπλουζάκι, ούτε εγώ θα έγραφα την ανάρτηση, αν το 1937 ο Lothar Collatz δεν διατύπωνε την εικασία (εικασία Collatz) ότι με την διαδικασία αυτή, ανεξάρτητα από ποιον φυσικό αριθμό Ν ξεκινάμε, καταλήγουμε πάντα στην μονάδα, την ρίζα του δέντρου!

Πραγματικά απίστευτο! Το δοκίμασα κι εγώ με διάφορους φυσικούς αριθμούς που δεν υπήρχαν στην μπλούζα και πάντα κατέληγα στην μονάδα.
Από όσα μου είπε ο Περικλής και όσα αναζήτησα στο διαδίκτυο, κατάλαβα ότι η εικασία αυτή απασχόλησε πολλούς γνωστούς μαθηματικούς, όπως τον Conway. Εντύπωση μου έκανε η δήλωση του Erdos "Τα Μαθηματικά δεν έχουν ωριμάσει αρκετά για να ασχολούνται με τέτοια προβλήματα", ο οποίος μάλιστα προσέφερε το έπαθλο των $500 σε όποιον το λύσει.
Το 2007 οι ερευνητές Kurtz και Simon, αξιοποιώντας δουλειά του Conway, απέδειξαν ότι η φυσική γενίκευση του προβλήματος Collatz, είναι πρόβλημα αλγοριθμικά μη αποφασίσιμο.

Πηγές:

  1. xkcd store, Collatz Conjecture
  2. Collatz conjecture, Wikipedia