Μαθηματικός του Harvard λύνει πρόβλημα 150 ετών χάρη στο σκάκι

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

Συγκεκριμένα, ο μεταδιδακτορικός συνεργάτης του Κέντρου Μαθηματικών Επιστημών και Εφαρμογών του HarvardMichael Simkin βρήκε τη λύση στο μαθηματικό πρόβλημα, βασιζόμενος σε μεγάλο βαθμό στους κανόνες του σκακιού.

Η βασίλισσα θεωρείται το πιο ισχυρό κομμάτι στο ταμπλό επειδή μπορεί να κινηθεί προς οποιαδήποτε κατεύθυνση, συμπεριλαμβανομένων των διαγωνίων. Πόσες βασίλισσες λοιπόν μπορεί κανείς να χωρέσει στη σκακιέρα χωρίς να διασταυρωθούν οι δρόμοι τους; Το εν λόγω σκεπτικό θυμίζει επίσης παζλ sudoku.

Το πρόβλημα

Φανταστείτε μία κλασική σκακιέρα, η οποία ουσιαστικά αποτελεί ένα τετράγωνο πλέγμα οκτώ επί οκτώ. Η πιο γνωστή εκδοχή του γρίφου ταιριάζει με τη σκακιέρα, επειδή περιλαμβάνει οκτώ βασίλισσες, και σε αυτή την περίπτωση υπάρχουν 92 λύσεις. Όμως το “πρόβλημα των n βασιλισσών” δεν σταματά εδώ, καθώς η φύση του είναι ασυμπτωτική, πράγμα που σημαίνει ότι οι απαντήσεις του προσεγγίζουν μια απροσδιόριστη τιμή που φτάνει στο άπειρο.

 

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

Σκεφτείτε το εξής: Για οκτώ βασίλισσες, υπάρχουν μόνο 92 λύσεις, αλλά για 27 βασίλισσες, υπάρχουν περισσότερες από 200 τετράκις εκατομμύρια λύσεις. Εν ολίγοις η επίλυση του προβλήματος για αριθμούς μεγαλύτερους από 27 γίνεται εξαιρετικά δύσκολη ή και αδύνατη χωρίς μεγαλύτερη υπολογιστική ισχύ από αυτή που διαθέτουμε αυτήν τη στιγμή.

Ο τρόπος σκέψης του Simkin

Σε αυτό το σημείο επενέβη ο Simkin. Το έργο του προσέγγισε το θέμα μέσω μίας έξυπνης μαθηματικής εκτίμησης του αριθμού των λύσεων καθώς αυξάνεται το ν. Για την ακρίβεια, κατέληξε στον ακόλουθο τύπο : (0,143ν)ν. Με άλλα λόγια, υπάρχουν περίπου (0,143ν)ν τρόποι για να τοποθετηθούν οι βασίλισσες έτσι ώστε καμία να μην επιτίθεται στην άλλη σε μια σκακιέρα ν επί ν.

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

“Σε μια εξαιρετικά μεγάλη σκακιέρα με ένα εκατομμύριο βασίλισσες, για παράδειγμα, το 0,143 θα πολλαπλασιαζόταν επί ένα εκατομμύριο, με αποτέλεσμα περίπου 143.000. Αυτός ο αριθμός θα αυξανόταν στη δύναμη του εκατομμυρίου, δηλαδή θα πολλαπλασιαζόταν με τον εαυτό του τον ίδιο αριθμό φορές. Η τελική απάντηση είναι ένας αριθμός με πέντε εκατομμύρια ψηφία”, εξηγεί το Harvard σε δελτίο τύπου.

Για να καταλήξει στη λύση του, ο Simkin πήρε πρώτα τους μέσους όρους της κατανομής των βασιλισσών στο ταμπλό. Χρησιμοποίησε αυτές τις τιμές για να καθορίσει την τιμή του κατώτερου ορίου, δηλαδή τον ελάχιστο αριθμό λύσεων που θα έχει μία συγκεκριμένη τιμή του ν. Χρησιμοποιώντας μία στρατηγική γνωστή ως “Αρχή Μεγιστοποίησης της Εντροπίας”, ο Simkin μελέτησε μια υπομονάδα του πλέγματος που δημιούργησε (και την οποία ονόμασε “queenon”) για να βρει την τιμή του ανώτερου ορίου.

Και οι δύο προσεγγίσεις χρησιμοποιούν τον μέσο όρο ή/και την τυχαιότητα ως μέσο για να βοηθήσουν στη μοντελοποίηση της σωστής τιμής. Ο Simkin διαπίστωσε ότι οι δύο διαφορετικές συναρτήσεις που έθεσε για τις τιμές του κατώτερου και του ανώτερου ορίου είναι σχεδόν ίσες, πράγμα που σημαίνει ότι το σύνολο των πιθανών απαντήσεων είναι άμεσα συνδεδεμένες, δημιουργώντας μία στέρεη μαθηματική εκτίμηση.

Όλη αυτή η σκληρή δουλειά σημαίνει ότι, για πρώτη φορά από το 1869, έχουμε μια ιδέα για τη λύση του προβλήματος των ν βασιλισσών. Για τον Simkin και το τμήμα του στο Harvard, είναι ένα τεράστιο επίτευγμα. To πιο αστείο από όλα βέβαια, είναι το ότι δεν παίζει σκάκι. “Εξακολουθώ να απολαμβάνω την πρόκληση του παιχνιδιού, αλλά υποθέτω ότι τα μαθηματικά είναι πιο επιεική”, εξηγεί στη δήλωσή του.

 

πηγή: https://esquire.com.gr/

Αφήστε μια απάντηση

Η ηλ. διεύθυνση σας δεν δημοσιεύεται. Τα υποχρεωτικά πεδία σημειώνονται με *