Σάββατο, 19 Μαρτίου 2011

Σκακιστικοί γρίφοι (1)

Εκτός από τις σκακιστικές συνθέσεις (τα σκακιστικά προβλήματα), υπάρχουν πάρα πολλοί σκακιστικοί γρίφοι, που χρησιμοποιούν σκακιέρες και πεσσούς, αλλά το θέμα τους είναι βασικά μαθηματικό.
Οι πεσσοί έχουν διαφορετικές δυνατότητες, άρα μπορούμε να "παίξουμε" με διάφορες τοποθετήσεις ή κινήσεις κομματιών.

Ας δούμε μερικούς γρίφους, αρκετά εύκολους.
Περιμένω απαντήσεις της μορφής [Γρίφος_τάδε, λύση / λύσεις].
Στο διαδίκτυο οι λύσεις υπάρχουν. Δεν χρειάζεται να ψάξετε.
Αυτό που ζητάω είναι να αντιμετωπίσετε μόνοι σας την πρόκληση και να ανακαλύψετε μία λύση. Αν θέλετε, βρείτε και πόσες διαφορετικές (όχι από κατοπτρική θέση ή περιστροφή της σκακιέρας) λύσεις έχει ο γρίφος.

Γ001 : Πόσους, το πολύ, λευκούς πύργους μπορούμε να τοποθετήσουμε σε μια 8x8 σκακιέρα, ώστε να "απειλούνται" όλα τα τετράγωνα εκτός από εκείνα που είναι κατειλημμένα;

Γ002 : Πόσες, το πολύ, λευκές βασίλισσες μπορούμε να τοποθετήσουμε σε μια 8x8 σκακιέρα, ώστε να "απειλούνται" όλα τα τετράγωνα εκτός από εκείνα που είναι κατειλημμένα;

Γ003 : Πόσους, το πολύ, λευκούς ίππους μπορούμε να τοποθετήσουμε σε μια 8x8 σκακιέρα, ώστε να "απειλούνται" όλα τα τετράγωνα εκτός από εκείνα που είναι κατειλημμένα;

Γ004 : Σε μια σκακιέρα βλέπουμε πολλά τετράγωνα, διαφόρων μεγεθών (1x1, 2x2, 3x3, ..., 8x8), με πλευρές παράλληλες με τις άκρες της σκακιέρας. Πόσα είναι;



Απαντήσεις

Να σημειώσω εδώ ότι ο πρώτος που έστειλε e-mail με πλήρεις εμπεριστατωμένες λύσεις ήταν ο Carlo de Grandi. Ακολούθησε ο Υδάτινος που έδωσε με σχόλιο απάντηση μόνο στον Γρίφο-4.

Γρίφος_001 : Πόσους, το πολύ, λευκούς πύργους μπορούμε να τοποθετήσουμε σε μια 8x8 σκακιέρα, ώστε να "απειλούνται" όλα τα τετράγωνα εκτός από εκείνα που είναι κατειλημμένα;

Γ001


Γ001α
Μπορούμε να τοποθετήσουμε, εύκολα, 8 πύργους. Η προφανής λύση είναι να τους βάλουμε σε μιά διαγώνιο (Δες Γ001). Θα μπορούσαμε όμως να τους βάλουμε σε άλλη θέση, ώστε να καταλαμβάνουν μία γραμμή και μία στήλη ο καθένας (Δες Γ001α).
Αν πούμε ότι ο πρώτος μπορεί να τοποθετηθεί σε 8 θέσεις της πρώτης στήλης, τότε ο δεύτερος μπορεί να τοποθετηθεί σε 7 θέσεις της δεύτερης στήλης, και ούτω καθεξής, μέχρι που ο τελευταίος έχει μόνο ένα τετράγωνο για να τοποθετηθεί στην όγδοη στήλη. Συνολικά υπάρχουν 8*7*6*5*4*3*2*1 τοποθετήσεις, (στα μαθηματικά αυτό το γινόμενο λέγεται [8 παραγοντικό] και συμβολίζεται με [8!]), ήτοι 8!=40320 τοποθετήσεις.
Ο φίλος DeGrandi μας ενημερώνει ότι το πρόβλημα είναι του Άγγλου μαθηματικού Ernest Dudeney (1857-1930), ο οποίος μεταξύ άλλων προσδιόρισε την επινόηση των διασταυρωμένων λέξεων στο σταυρόλεξο.


Γρίφος_002 : Πόσες, το πολύ, λευκές βασίλισσες μπορούμε να τοποθετήσουμε σε μια 8x8 σκακιέρα, ώστε να "απειλούνται" όλα τα τετράγωνα εκτός από εκείνα που είναι κατειλημμένα;

Γ002
Μπορούμε να τοποθετήσουμε, λίγο πιό δύσκολα, 8 βασίλισσες. Ο βασιλιάς των γρίφων (υπάρχει βιβλίο "The Puzzle King" με σκακιστικούς γρίφους του, υπό Sid Pickard) Αμερικανός Sam Loyd δημοσίευσε στο American Chess Journal τον Φεβρουάριο 1877 την τοποθέτηση που βλέπετε στο Γ002, (λέγοντας ότι όποια κι αν είναι η λύση, με περιστροφή της ή ανάκλασή της, στο d1 πρέπει να υπάρχει οπωσδήποτε μία βασίλισσα).
Το πρόβλημα αυτό είναι παλιό, (σε ένα σχόλιο του αναγνώστη Kevin σημειώνεται ότι το πρότεινε πρώτος ο Max Bezzel, στην εφημερίδα Die Schachzeitung το 1848), δημοσιεύθηκε το έτος 1848 στο γερμανικό σκακιστικό έντυπο "Illustrierte Scachzeitung" (=εικονογραφημένη σκακιστική εφημερίδα) ως συνέχεια μιας ερωτήσεως από τον φιλόλογο καθηγητή Dr. A. Nauck, ο οποίος το πρότεινε και στον Karl Friedrich Gauss (1777-1855). Ο Nauck δημοσίευσε το 1850 μια λύση (συμμετρική με εκείνη του Λόιντ) ενώ ο μαθηματικός Gauss εντόπισε 12 βασικές τοποθετήσεις. (Δείτε εδώ).
Όπως σωστά σχολιάζει ο φίλος Υδάτινος, το πρόβλημα είναι πολύ δημοφιλές στους πρωτοετείς των σχολών πληροφορικής.


Γρίφος_003 : Πόσους, το πολύ, λευκούς ίππους μπορούμε να τοποθετήσουμε σε μια 8x8 σκακιέρα, ώστε να "απειλούνται" όλα τα τετράγωνα εκτός από εκείνα που είναι κατειλημμένα;

Γ003α


Γ003β

Γ003γ
Η απάντηση είναι πολύ εύκολη : 32. Βάζουμε 32 ίππους στα λευκά τετράγωνα της σκακιέρας και όλοι "απειλούν" τα μαύρα τετράγωνα. Εναλλακτικά, θα μπορούσαμε να τους έχουμε βάλει όλους στα μαύρα τετράγωνα. Άρα υπάρχουν δύο τοποθετήσεις.

Σε μια διαφορετική διατύπωση Γρίφος_3α : "Πόσους, το λιγότερο, λευκούς ίππους μπορούμε να τοποθετήσουμε σε μια 8x8 σκακιέρα, ώστε να "απειλούνται" όλα τα τετράγωνα εκτός από εκείνα που είναι κατειλημμένα;", βλέπουμε μια εύκολη απάντηση στο σχήμα Γ003α, όπου χρησιμοποιούνται 24 ίπποι και μια πιό οικονομική με 16 ίππους στο Γ003β.

Αλλάζοντας πάλι την διατύπωση Γρίφος_3β : "Πόσους, το λιγότερο, λευκούς ίππους μπορούμε να τοποθετήσουμε σε μια 8x8 σκακιέρα, ώστε να "απειλούνται" όλα τα τετράγωνα που δεν είναι κατειλημμένα;", (εννοώντας ότι θα μπορούσαν να απειλούνται και μερικά κατειλημμένα τετράγωνα), βρίσκουμε ότι η άριστη λύση (φαίνεται στο σχήμα Γ003γ) χρησιμοποιεί μόνο 12 ίππους!


Γρίφος_004 : Σε μια σκακιέρα βλέπουμε πολλά τετράγωνα, διαφόρων μεγεθών (1x1, 2x2, 3x3, ..., 8x8), με πλευρές παράλληλες με τις άκρες της σκακιέρας. Πόσα είναι;

Γ004
Στο σχήμα Γ004 βλέπουμε αριθμούς μέσα στα τετραγωνάκια της σκακιέρας. Ο αριθμός είναι το πλήθος διαφορετικών τετραγώνων που σχηματίζονται με αυτό το τετραγωνάκι ως πάνω-αριστερή-γωνία. Αθροίζοντας τα πλήθη (όπως φαίνεται και στο περιθώριο) έχουμε σύνολο = 1x8 + (2x7+1x7) + (3x6+2x6) + (4x5+3x5) + (5x4+4x4) + (6x3+5x3) + (7x2+6x2) + (8x1+7x1) = 8 + 21 + 30 + 35 + 36 + 33 + 26 + 15 = 204 τετράγωνα.

1 σχόλιο:

Υδάτινος είπε...

Τα πρώτα τρία ερωτήματα είναι αρκετά συνηθισμένα και όποιος έχει προγραμματίσει ποτέ υπολογιστή, θα έχει γράψει και κώδικα για να βρει το πλήθος των τοποθετήσεων.
Για το Γ004 :
Τετράγωνο 8x8 είναι μόνο ένα, η ίδια η σκακιέρα.
Για κάθε άλλο τετράγωνο nxn, υπάρχουν (8-n+1) στήλες ελεύθερες για να τοποθετήσουμε την "κάτω αριστερά" γωνία του και άλλες τόσες γραμμές.
Άρα (8-n+1)^2 δυνατές τοποθετήσεις.
Οπότε, το πλήθος δίνεται από το άθροισμα : (1^2) + (2^2) + (3^2) + ... + (8^2) = 204