Η γενίκευση του γρίφου με τις 8 βασίλισσες σε μια σκακιέρα

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

Ο γρίφος με τις 8 βασίλισσες εμφανίστηκε το 1848 σε ένα γερμανικό σκακιστικό περιοδικό.

Αποδεικνύεται ότι υπάρχουν 92 διαφορετικοί τρόποι της συγκεκριμένης διάταξης από τις συνολικά 4.426.165.368 τυχαίες διατάξεις!

Αν τώρα αντί οκτώ βασιλισσών στην κλασική σκακιέρα 8×8 τετραγώνων, θέλουμε να τοποθετήσουμε n-βασίλισσες σε μια εκτεταμένη σκακιέρα nxn τετραγώνων, έτσι ώστε η μια να μην απειλεί την άλλη, πόσοι τέτοιοι διαφορετικοί τρόποι διάταξης υπάρχουν;

Το πρόβλημα με τις n-βασίλισσες που διατυπώθηκε το 1869

Πρόκειται για ένα μαθηματικό πρόβλημα που εύκολα παρουσιάζεται, αλλά πολύ δύσκολα επιλύεται. Ακόμα και οι υπολογιστές αδυνατούν να το προσεγγίσουν από ένα σημείο και μετά. Για παράδειγμα, σε μια σκακιέρα 27×27 τετραγώνων υπάρχουν 2,34 τετράκις εκατομμύρια πιθανές λύσεις. Όταν μάλιστα η σκακιέρα γίνει 1.000×1.000 και ο υπολογιστής πρέπει να τοποθετήσει 1.000 βασίλισσες, τότε χάνεται στην άβυσσο των πολύ μεγάλων αριθμών.

Κι όμως, ο Michael Simkin, κατάφερε να αποδείξει – χωρίς να χρησιμοποιήσει προσομοιώσεις υπολογιστών – ότι για τεράστιες σκακιέρες με μεγάλο αριθμό βασιλισσών (n\rightarrow \infty) , υπάρχουν περίπου (0,143n)n διατάξεις.

Έτσι, σε μια σκακιέρα με 106x106 τετράγωνα ο αριθμός των δυνατών διατάξεων ενός εκατομμυρίου βασιλισσών (που δεν απειλούνται μεταξύ τους) είναι ένας ιλιγγιωδώς τεράστιος αριθμός, περίπου όσο το 1 ακολουθούμενο 5 εκατομμύρια μηδενικά! (\cong 1,09 \cdot 10^{5155336})

Διαβάστε πως το κατάφερε ΕΔΩ: Mathematician Answers Chess Problem About Attacking Queens και ΕΔΩ: A lower bound for the n-queens problem



Κατηγορίες:ΜΑΘΗΜΑΤΙΚΑ

Ετικέτες: ,

2 replies

  1. Οταν ημουν εφηβοσ ηταν ενα απο τα αγαπημενα μου προβληματα (δηλαδη να βαλω 8 βασιλισσεσ ωστε η μια να μην απειλει την αλλη ) .Φυσικα δεν βρηκα και τισ 92 διαταξεισ αλλα μρ οσεσ ανακαλυψα μεχρι να το παρατησω ημουνα ευχαριστημενοσ!!!!!

  2. Νομίζω μια μέθοδος ειναι να τις τοποθετείς στις δυο ακραίες θέσεις της κίνησης του ίππου

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Google

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση /  Αλλαγή )

Σύνδεση με %s

Ο ιστότοπος χρησιμοποιεί το Akismet για την εξάλειψη των ανεπιθύμητων σχολίων. Μάθετε πως επεξεργάζονται τα δεδομένα των σχολίων σας.

Αρέσει σε %d bloggers: