ΠΡΟΒΛΗΜΑ 8 ΒΑΣΙΛΙΣΣΩΝ

[AΝΔΡΕΑΣ ΒΑΡΒΕΡΑΚΗΣ]

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

[Ορέστης Λιγνός]

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

Καλησπέρα κ. Ανδρέα! Όμορφη...

Ένα παράδειγμα που δείχνει μια τέτοια τοποθέτηση βασιλισσών είναι το εξής (με συμβολίζω τις βασίλισσες):



Για το δεύτερο σκέλος του προβλήματος, συμβολίζω με το κελί που βρίσκεται στην γραμμή και στήλη. Το γεγονός ότι καμία βασίλισσα δεν απειλεί κάποια άλλη σημαίνει ότι κάθε δύο από τις βασίλισσες βρίσκονται σε διαφορετική γραμμή, στήλη, και διαγώνιο. Είναι σαφές ότι υπάρχουν ειδών διαγώνιες, αυτές για τις οποίες το παραμένει σταθερό για κάθε κελί που ανήκει στην διαγώνιο (για παράδειγμα η διαγώνιος που συνδέει το κελί με το κελί . Αυτές τις διαγώνιους τις ονομάζω διαγώνιους τύπου 1) και αυτές στις οποίες το είναι σταθερό για κάθε κελί που ανήκει στην διαγώνιο (για παράδειγμα η διαγώνιος που συνδέει το κελί με το κελί . Αυτές τις διαγώνιους τις ονομάζω διαγώνιους τύπου 2).

Θεωρούμε ότι το κελί είναι λευκό. Είναι προφανές ότι ένα κελί είναι λευκό αν, και μόνο αν, ισχύει .

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

Επιπλέον, για τις βασίλισσες σε λευκά κελιά ισχύει ότι , ενώ για τις βασίλισσες σε μαύρα κελιά ισχύει ότι , άρα προκύπτει ότι



δηλαδή και επίσης , αφού .

Τώρα, για να δείξουμε ότι αρκεί να δείξουμε ότι (χωρίς βλάβη της γενικότητας) . Αυτό το δείχνουμε στους δύο επόμενους Ισχυρισμούς:

Ισχυρισμός 1: .
Απόδειξη: Είναι σαφές ότι μία διαγώνιος αποτελείται από μόνο μαύρα ή μόνο λευκά κελιά. Θεωρούμε όλες τις διαγώνιους τύπου 1 για τις οποίες όλα τους τα κελιά είναι λευκά. Υπάρχουν τέτοιες διαγώνιες και προφανώς καλύπτουν όλα τα λευκά κελιά. Αν , τότε θα υπήρχε μία διαγώνιος με τουλάχιστον δύο βασίλισσες, που από υπόθεση είναι άτοπο

Ισχυρισμός 2: .
Απόδειξη: Έστω πως . Θεωρούμε ξανά τις διαγώνιους του προηγούμενου Ισχυρισμού. Αν οι διαγώνιες αποτελούμενες από τα κελιά και δεν περιέχουν καμία βασίλισσα, τότε συνολικά έχουμε (από μία βασίλισσα σε κάθε μία από τις εναπομείνασες διαγώνιους), άτοπο. Άρα μία από αυτές τις δύο διαγώνιους περιέχει βασίλισσα, ή και οι δύο.

Περίπτωση 1: Μόνο μία από αυτές τις διαγώνιους περιέχει βασίλισσα, έστω η , και έστω ότι η βασίλισσα βρίσκεται στο κελί . Τότε μένουν βασίλισσες και διαγώνιες, άρα κάθε διαγώνιος περιέχει ακριβώς μία βασίλισσα. Από την υπόθεση συνάγουμε ότι η διαγώνιος των κελιών περιέχει βασίλισσα στο . Τότε, η διαγώνιος των κελιών περιέχει βασίλισσα είτε στο είτε στο . Συνεχίζοντας με τον ίδιο τρόπο προκύπτει σε κάθε περίπτωση ότι η διαγώνιος των κελιών δεν μπορεί να περιέχει βασίλισσα, άτοπο.

Περίπτωση 2: Και οι δύο διαγώνιες περιέχουν βασίλισσα. Τότε, από τη συνθήκη προκύπτει ότι τα κελιά και περιέχουν τις βασίλισσες. Θεωρούμε τις εξής ομάδες κελιών:

Ομάδα 1:
Ομάδα 2:
Ομάδα 3:
Ομάδα 4:

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

[AΝΔΡΕΑΣ ΒΑΡΒΕΡΑΚΗΣ]

Σε ευχαριστώ Ορέστη για την ενασχόληση και φυσικά για την εξαιρετική αντιμετώπιση.
Το πρόβλημα ξεκίνησε από ένα θέμα των Πανενωσιακών Ολυμπιάδων όπου ζητούσε να αποδείξουμε ότι ο αριθμός των βασιλισσών σε μαύρα (η άσπρα) τετράγωνα είναι άρτιος, όπως άλλωστε απέδειξες στο πρώτο μέρος της λύσης σου.
Θα καταθέσω αργότερα την δική μου προτεινόμενη λύση.
Καλή επιτυχία στον Αρχιμήδη και εννοείται στην !

[AΝΔΡΕΑΣ ΒΑΡΒΕΡΑΚΗΣ]

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

untitled.jpg (15.69 KiB) Προβλήθηκε 2751 φορές

[gbaloglou]

Ανδρέα δεν βλέπω πως αυτή η υπέροχη κατά τα άλλα ειδική διάταξη επιλύει το γενικό πρόβλημα. Μπορούμε για παράδειγμα να έχουμε 5 βασίλισσες σε μαύρα τετράγωνα, , που αφήνουν χώρο για 2 ακόμη, αλλά όχι 3, βασίλισσες στα λευκά τετράγωνα και .

[AΝΔΡΕΑΣ ΒΑΡΒΕΡΑΚΗΣ]

Ανδρέα δεν βλέπω πως αυτή η υπέροχη κατά τα άλλα ειδική διάταξη επιλύει το γενικό πρόβλημα. Μπορούμε για παράδειγμα να έχουμε 5 βασίλισσες σε μαύρα τετράγωνα, , που αφήνουν χώρο για 2 ακόμη, αλλά όχι 3, βασίλισσες στα λευκά τετράγωνα και .

Έχεις δίκιο Γιώργο, σε ευχαριστώ.
Είχα την αμφιβολία αλλά νόμιζα ότι το κάλυψα. Υπάρχει ενδεχόμενο αν αφαιρέσουμε μία από τις τέσσερις βασίλισσές στο εσωτερικό του μικρού τετραγώνου, να ελευθερωθούν δύο εξωτερικά τετράγωνα όπως στο παράδειγμα σου τα (1,1) και (8,2). Επομένως είναι απαραίτητο να αποδείξουμε και την αρτιότητα.
Οπότε συμπληρώνουμε: Υπάρχουν τέσσερις βασίλισσες στις περιττές γραμμές και τέσσερις στις άρτιες στήλες. Καθώς όμως αυτές οι γραμμές και στήλες έχουν κοινά μόνο λευκά τετράγωνα, όσες βασίλισσες υπάρχουν στα μαύρα των περιττών γραμμών, άλλες τόσες υπάρχουν και στα μαύρα των άρτιων στηλών. Επομένως ο συνολικός αριθμός των κατειλημμένων μαύρων τετραγώνων είναι άρτιος.
Μένει να αποκλείσουμε την περίπτωση των 6.
Θα το ξανατσεκάρω αργότερα.

[AΝΔΡΕΑΣ ΒΑΡΒΕΡΑΚΗΣ]

Βλέπω να υπάρχει κενό προς το παρόν για να αποκλείσω την περίπτωση των 6.
Οπότε άκυρη η λύση μου.

[gbaloglou]

Βλέπω να υπάρχει κενό προς το παρόν για να αποκλείσω την περίπτωση των 6.
Οπότε άκυρη η λύση μου.

Ανδρέα 'απλώς' χρειάζεται το εξής, ανεξαρτήτου ενδιαφέροντος, λήμμα: "5 μη αλληλοαπειλούμενες βασίλισσες σε μαύρα τετράγωνα απειλούν όλα τα υπόλοιπα μαύρα τετράγωνα της σκακιέρας". Δεν βλέπω κάποια γρήγορη απόδειξη προς το παρόν.

[gbaloglou]

Βλέπω να υπάρχει κενό προς το παρόν για να αποκλείσω την περίπτωση των 6.
Οπότε άκυρη η λύση μου.

Ανδρέα 'απλώς' χρειάζεται το εξής, ανεξαρτήτου ενδιαφέροντος, λήμμα: "5 μη αλληλοαπειλούμενες βασίλισσες σε μαύρα τετράγωνα απειλούν όλα τα υπόλοιπα μαύρα τετράγωνα της σκακιέρας". Δεν βλέπω κάποια γρήγορη απόδειξη προς το παρόν.

Δίνω εδώ (και στην αμέσως επόμενη δημοσίευση) μία 'απαριθμητική' απόδειξη: χωρίζοντας την σκακιέρα σε 'κέντρο' (4 κεντρικά τετράγωνα συν τα 12 τετράγωνα γύρω τους) και 'περιφέρεια' (τα υπόλοιπα 48 τετράγωνα, 28 περιμετρικά τετράγωνα συν τα 20 τετράγωνα πλησίον τους), παρατηρούμε ότι στο κέντρο μπορούμε να έχουμε δύο το πολύ βασίλισσες (με κόκκινο κύκλο στο πρώτο συνημμένο)^ αποφεύγοντας τις 'συμμετρικές επαναλήψεις' που ελλοχεύουν, καταλήγουμε σε 6 βασικές περιπτώσεις που απεικονίζονται στο πρώτο συνημμένο, ενώ στο δεύτερο συνημμένο εξετάζεται η πρώτη βασική περίπτωση (καμία βασίλισσα στις δύο λωρίδες του κέντρου, με πράσινο κύκλο οι βασίλισσες της τρίτης λωρίδας, αφήνεται στον αναγνώστη να διαπιστώσει ότι τοποθετώντας επιπλέον βασίλισσες στην περιμετρική τέταρτη λωρίδα δεν ξεπερνούμε σε καμιά περίπτωση τις πέντε συνολικά).

[Πιστεύω ότι δεν μου έχει ξεφύγει καμία περίπτωση (Υπό τον όρο -- προσθέτω 6 ώρες αργότερα -- να 'προκριθούν στον τελικό', να θεωρηθούν υποψήφιες δηλαδή για προσθήκη βασιλισσών στην περιμετρική τέταρτη λωρίδα, ΚΑΙ οι 'κόκκινες' σκακιέρες του πρώτου συνημμένου, να εξεταστούν δηλαδή και οι περιπτώσεις όπου μένει κενή η τρίτη λωρίδα!) Τονίζω και πάλι ότι προσπάθησα να αποφύγω τις συμμετρικές επαναλήψεις -- όπου "συμμετρία" μπορεί να σημαίνει όχι μόνο στροφή μα και ανάκλαση (με τις 'μαύρες' βασίλισσες να γίνονται 'λευκές') -- αν και δεν αποκλείεται να παρεισέφρυσε τελικά κάποια πλεονάζουσα περίπτωση ]

central-two-squares.png (146.71 KiB) Προβλήθηκε 2460 φορές

[gbaloglou]

Συνεχίζω, στο πνεύμα της αμέσως προηγούμενης δημοσίευσης, με τις υπόλοιπες 5 περιπτώσεις: με κόκκινο και πάλι οι βασίλισσες του κέντρου (μία ή δύο), και με πράσινο οι βασίλισσες (το πολύ δύο) της τρίτης λωρίδας^ αφήνεται και πάλι στον αναγνώστη να διαπιστώσει ότι, με την προσθήκη επιπλέον βασιλισσών στην περιμετρική τέταρτη λωρίδα, ο συνολικός αριθμός βασιλισσών δεν ξεπερνά σε καμιά περίπτωση τις πέντε.

44-5-queens.png (103.05 KiB) Προβλήθηκε 2458 φορές

46-5-queens.png (126 KiB) Προβλήθηκε 2458 φορές

33-46-5-queens.png (100.96 KiB) Προβλήθηκε 2458 φορές

46-53-5-queens.png (47.61 KiB) Προβλήθηκε 2458 φορές

[gbaloglou]

Οι παραπάνω 'βασικές' περιπτώσεις (που οδηγούν σε τοποθέτηση έως 5 μη αλληλοαπειλούμενων βασιλισσών σε μαύρα τετράγωνα μέσω τοποθέτησης μαύρων βασιλισσών στην περίμετρο) ... θα μπορούσαν άραγε να μας οδηγήσουν σε όλες τις δυνατές τοποθετήσεις 8 μη αλληλοαπειλούμενων βασιλισσών (4 μαύρων και 4 λευκών); Όχι άμεσα, είναι πολλές οι περιπτώσεις (4 μαύρων βασιλισσών), μπορούμε όμως να κάνουμε κάτι άλλο (προς το παρόν τουλάχιστον): να εξετάσουμε δηλαδή, για κάθε μία από τις δώδεκα συνολικά λύσεις του προβλήματος των 8 βασιλισσών, ποια από τις 'βασικές' μας περιπτώσεις οδηγεί σ' αυτήν! Αυτό ακριβώς κάνω στο συνημμένο, που θα πρέπει να αντιπαρατεθεί, θέση προς θέση, με τις δώδεκα λύσεις όπως παρουσιάζονται εδώ, λαμβάνοντας πάντα υπ' όψιν την ταύτιση συμμετρικών λύσεων και περιπτώσεων. (Συχνά η συμμετρία που χρειάζεται είναι ανάκλαση ως προς την διαγώνιο.)

8-queens-12-basic-solutions.png (419.26 KiB) Προβλήθηκε 2351 φορές

[gbaloglou]

Βλέπω να υπάρχει κενό προς το παρόν για να αποκλείσω την περίπτωση των 6.
Οπότε άκυρη η λύση μου.

Ανδρέα 'απλώς' χρειάζεται το εξής, ανεξαρτήτου ενδιαφέροντος, λήμμα: "5 μη αλληλοαπειλούμενες βασίλισσες σε μαύρα τετράγωνα απειλούν όλα τα υπόλοιπα μαύρα τετράγωνα της σκακιέρας". Δεν βλέπω κάποια γρήγορη απόδειξη προς το παρόν.

Μία γρήγορη λύση: αν έχουμε 6 'μαύρες' βασίλισσες, τότε σε ένα από τα δύο τρίγωνα 'τριών μαύρων διαγωνίων' (και 12 μαύρων τετραγώνων) στα οποία χωρίζει η κεντρική μαύρη ΝΔ-ΒΑ διαγώνιος την σκακιέρα θα πρέπει να υπάρχουν 3 βασίλισσες (είτε υπάρχει είτε όχι βασίλισσα στην κεντρική διαγώνιο)^ εύκολα βλέπουμε ότι υπάρχουν έξι συνολικά περιπτώσεις γι' αυτό το τρίγωνο, στις πέντε από τις οποίες δεν υπάρχει χώρος για βασίλισσα στην τελευταία (ελάχιστη) διαγώνιο, ενώ στην έκτη (κέντρο κάτω στο συνημμένο) μένουν έξι συνολικά θέσεις στην υπόλοιπη σκακιέρα (συμμετρικό τρίγωνο συν κεντρική διαγώνιος) όπου όμως δεν χωρούν τρεις μη αλληλοαπειλούμενες βασίλισσες (βλέπε πορτοκαλί θέσεις στο συνημμένο).

no-6-queens.png (177.45 KiB) Προβλήθηκε 2295 φορές

[gbaloglou]

Επισυνάπτω ένα παράδειγμα (όχι δικό μου) με 6 μαύρες βασίλισσες και 4 λευκές βασίλισσες σε 10x10 σκακιέρα, και ένα παράδειγμα με 8 μαύρες βασίλισσες σε 12x12 σκακιέρα: το πρώτο παράδειγμα δείχνει ότι δεν γενικεύεται η 'ισότητα' λευκών και μαύρων βασιλισσών του αρχικού προβλήματος, το δεύτερο εξασθενεί την πιθανότητα γενίκευσης σε (4n)x(4n) σκακιέρα -- αν είναι τόσο εύκολο να βρούμε 8 μη αλληλοαπειλούμενες μαύρες βασίλισσες, είναι αρκετά αναμενόμενο να βρούμε και 4 λευκές βασίλισσες ώστε να έχουμε 12 συνολικά μη αλληλοαπειλούμενες βασίλισσες.

Lexicographically-optimal-solution-for-n-10.png (12.78 KiB) Προβλήθηκε 2235 φορές

[gbaloglou]

Επισυνάπτω ένα παράδειγμα (όχι δικό μου) με 6 μαύρες βασίλισσες και 4 λευκές βασίλισσες σε 10x10 σκακιέρα, και ένα παράδειγμα με 8 μαύρες βασίλισσες σε 12x12 σκακιέρα: το πρώτο παράδειγμα δείχνει ότι δεν γενικεύεται η 'ισότητα' λευκών και μαύρων βασιλισσών του αρχικού προβλήματος, το δεύτερο εξασθενεί την πιθανότητα γενίκευσης σε (4n)x(4n) σκακιέρα -- αν είναι τόσο εύκολο να βρούμε 8 μη αλληλοαπειλούμενες μαύρες βασίλισσες, είναι αρκετά αναμενόμενο να βρούμε και 4 λευκές βασίλισσες ώστε να έχουμε 12 συνολικά μη αλληλοαπειλούμενες βασίλισσες.

Πράγματι -- ιδού μία απλούστατη και συμμετρικότατη λύση με 8 μαύρες βασίλισσες και 4 λευκές βασίλισσες σε 12 x 12 σκακιέρα:

8-4-queens.png (22.29 KiB) Προβλήθηκε 2138 φορές

[gbaloglou]

Προτείνω τις εξής δύο ΕΙΚΑΣΙΕΣ (πιθανώς ήδη γνωστές, ακόμη και ως θεωρήματα):

(Ι) Ο μέγιστος αριθμός μη αλληλοαπειλούμενων μαύρων βασιλισσών σε σκακιέρα είναι μικρότερος ή ίσος του .

(II) Αν είναι οι αριθμοί μαύρων και λευκών μη αλληλοαπειλούμενων βασιλισσών σε σκακιέρα με , τότε .

[gbaloglou]

Προτείνω τις εξής δύο ΕΙΚΑΣΙΕΣ (πιθανώς ήδη γνωστές, ακόμη και ως θεωρήματα):

(Ι) Ο μέγιστος αριθμός μη αλληλοαπειλούμενων μαύρων βασιλισσών σε σκακιέρα είναι μικρότερος ή ίσος του .

(II) Αν είναι οι αριθμοί μαύρων και λευκών μη αλληλοαπειλούμενων βασιλισσών σε σκακιέρα με , τότε .

Τουλάχιστον η πρώτη εικασία (Ι) δεν αληθεύει, όπως αποδείχτηκε εδώ -- επισυνάπτω το ελάχιστο αντιπαράδειγμα () του Daniel Mathias:

7-10.png (16.42 KiB) Προβλήθηκε 2004 φορές

[gbaloglou]

Προτείνω τις εξής δύο ΕΙΚΑΣΙΕΣ (πιθανώς ήδη γνωστές, ακόμη και ως θεωρήματα):

(Ι) Ο μέγιστος αριθμός μη αλληλοαπειλούμενων μαύρων βασιλισσών σε σκακιέρα είναι μικρότερος ή ίσος του .

(II) Αν είναι οι αριθμοί μαύρων και λευκών μη αλληλοαπειλούμενων βασιλισσών σε σκακιέρα με , τότε .

Το άλλο παράδειγμα του Daniel Mathias (εδώ) καταρρίπτει -- συμμετρικότατα, για -- και την δεύτερη εικασία (ΙΙ):

3-11.png (21.58 KiB) Προβλήθηκε 1998 φορές

[gbaloglou]

Υπεραισιόδοξη η εικασία μου τελικά, και υπέρ το δέον επηρεασμένη από την περίπτωση , όπου η μελέτη κάποιων από τις 79 (!) περιπτώσεις στις οποίες 'βαθμιαία' κατέληξα -- στο πνεύμα της μη ύπαρξης μαύρων βασιλισσών στην σκακιέρα (βλ. δημοσίευση #12) -- με άφησε με την εντύπωση ότι δεν μπορούμε να έχουμε μαύρες βασίλισσες στην σκακιέρα: παραθέτω ένα τέτοιο (αντι)παράδειγμα στο συνημμένο ... και λήγει εδώ το ζήτημα

9-12.png (7 KiB) Προβλήθηκε 1965 φορές

[gbaloglou]

Προτείνω τις εξής δύο ΕΙΚΑΣΙΕΣ (πιθανώς ήδη γνωστές, ακόμη και ως θεωρήματα):

(Ι) Ο μέγιστος αριθμός μη αλληλοαπειλούμενων μαύρων βασιλισσών σε σκακιέρα είναι μικρότερος ή ίσος του .

(II) Αν είναι οι αριθμοί μαύρων και λευκών μη αλληλοαπειλούμενων βασιλισσών σε σκακιέρα με , τότε .

Με βάση τα συζητούμενα στην OEIS, οι παραπάνω εικασίες αναδιατυπώνονται:

(Ι) Ο μέγιστος αριθμός μη αλληλοαπειλούμενων μαύρων βασιλισσών σε σκακιέρα είναι μικρότερος του .

(II) Αν είναι οι αριθμοί μαύρων και λευκών μη αλληλοαπειλούμενων βασιλισσών σε σκακιέρα με , τότε .

[Δεδομένου του τι υπάρχει 'εκεί έξω' -- ένας από τους συμμετέχοντες έχει γράψει βιβλίο 800 σελίδων για παρεμφερή προβλήματα! -- είναι απρόσμενο να μην έχει ήδη μελετηθεί, και συνεπώς να έχει γίνει δεκτό, το πρόβλημα που έθεσα ]