tromaktiko: Ο Κύβος του Ρούμπικ «μπορεί πάντα να λυθεί με 20 ή λιγότερες κινήσεις»

Παρασκευή 13 Αυγούστου 2010

Ο Κύβος του Ρούμπικ «μπορεί πάντα να λυθεί με 20 ή λιγότερες κινήσεις»



Πιο εύκολο από ό,τι φαίνεται, τουλάχιστον για τους υπολογιστές της GoogleΟποιαδήποτε διάταξη στον Κύβο του Ρούμπικ μπορεί να επιλυθεί με 20 κινήσεις το πολύ, υπολογίζουν Αμερικανοί ερευνητές, οι οποίοι δέχτηκαν τη βοήθεια της Google για να λύσουν ένα πρόβλημα που κεντρίζει την προσοχή των μαθηματικών εδώ και τέσσερις δεκαετίες.
Ο μέγιστος αριθμός κινήσεων που απαιτούνται για τη λύση του κύβου είχε...
βαφτιστεί «ο αριθμός του Θεού», καθώς υποτίθεται ότι μια οντότητα που γνωρίζει τα πάντα θα γνώριζε και την απάντηση στο πρόβλημα.

Η νέα μελέτη εξέτασε ουσιαστικά όλους τους δυνατούς συνδυασμούς και καταλήγει στο συμπέρασμα ότι ο μαγικός αριθμός είναι 20. Η εκτίμηση αυτή θα ισχύει μέχρι να ανακαλυφθεί κάποια διάταξη που χρειάζεται 21 κινήσεις, ένα ενδεχόμενο μάλλον απίθανο.

«Γνωρίζουμε πλέον με βεβαιότητα ότι ο μαγικός αριθμός είναι το 20» είπε στο BBC ο Μόρλει Ντέιβιντσον, καθηγητής Μαθηματικών στο Πολιτειακό Πανεπιστήμιο του Κεντ και επικεφαλής της ερευνητικής ομάδας.

Η μελέτη υποβάλλεται τώρα για έλεγχο και δημοσίευση σε επιστημονική επιθεώρηση.

Δύσκολοι υπολογισμοί

Ο Κύβος του Ρούμπικ εφευρέθηκε το 1974 από τον Ούγγρο αρχιτέκτονα Έρνο Ρούμπικ, και έχει περισσότερα από 43 δισεκατομμύρια δισεκατομμύρια δυνατές διατάξεις ή σημεία εκκίνησης.

Στη νέα μελέτη, οι ερευνητές ήταν αδύνατο να εξετάσουν όλους τους πιθανούς συνδυασμούς. Για να κάνουν πιο εύκολο το πρόβλημα, εντόπισαν και απέκλεισαν τους συμμετρικούς και παρόμοιους συνδυασμούς και περιορίστηκαν σε 56 εκατομμύρια ομάδες των 20 δισεκατομμυρίων διατάξεων.

Η πλειονότητα των διατάξεων αυτών επιλύεται με 15 έως 19 κινήσεις, βρέθηκαν όμως και 100 εκατομμύρια σημεία εκκίνησης που λύνονται μόνο με 20 κινήσεις.

Η πρώτη εκτίμηση για τον μαγικό αριθμό δημοσιεύτηκε το 1981 από τον μαθηματικό Μ.Θίσλουεϊτ, και ήταν 52 κινήσεις. Μια μεταγενέστερη εκτίμηση που έριχνε τον «αριθμό του Θεού» στις 18 κινήσεις καταρρίφθηκε το 1995, όταν βρέθηκε μια διάταξη του κύβου που απαιτούσε 20.

«Είχαμε τη μυστική ελπίδα στις δοκιμές μας ότι θα υπήρχε μία [διάταξη] που απαιτεί 21 κινήσεις» σχολίασε ο Δρ Ντέιβιντσον.

Δεδομένου ότι ένα καλό PC θα χρειαζόταν 35 χρόνια για να εξετάσει όλους τους πιθανούς συνδυασμούς, η ομάδα του Ντέιβιντσον δέχθηκε τη βοήθεια που προσέφερε η Google.

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

«Ακόμα δεν γνωρίζουμε τι μηχανήματα χρησιμοποίησαν» στη Google, παραδέχτηκε ο Ντέιβιντσον στο Beep.
     



Εδώ σχολιάζεις εσύ!