Το θεώρημα του γάμου (ΙΙ)

Ας δούμε και μερικές εφαρμογές του θεωρήματος του γάμου.

A) Συμπλήρωση λατινικών τετραγώνων

Ένα λατινικό τετράγωνο είναι ένας n \times n πίνακας του οποίου κάθε γραμμή και κάθε στήλη περιέχει τα στοιχεία \{1,2,\ldots,n\} ακριβώς από μία φορά. Για παράδειγμα ο πίνακας

Έστω ότι έχουμε ένα n \times n πίνακα με συμπληρωμένα κάποια στοιχεία του (με στοιχεία από το σύνολο \{1,2,\ldots,n\}) ώστε σε κάθε γραμμή και σε κάθε στήλη να περιέχει το κάθε στοιχείο του \{1,2,\ldots,n\} το πολύ μία φορά. Θα ονομάζουμε ένα τέτοιο πίνακα «μερικώς συμπληρωμένο λατινικό τετράγωνο».

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

Έστω ότι έχουμε ένα μερικώς συμπληρωμένο λατινικό τετράγωνο με συμπληρωμένες τις πρώτες k γραμμές. Μπορεί να συμπληρωθεί πλήρως για να γίνει λατινικό τετράγωνο; Για παράδειγμα αν έχουμε συμπληρωμένη μία ακριβώς γραμμή η απάντηση είναι ναι διότι μπορούμε να τον συμπληρώσουμε κυκλικά όπως στο πιο κάτω παράδειγμα.

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

Θεώρημα: Κάθε μερικώς συμπληρωμένο n \times n λατινικό τετράγωνο με συμπληρωμένες τις πρώτες k γραμμές, όπου k < n, μπορεί να επεκταθεί σε ένα μερικώς συμπληρωμένο λατινικό τετράγωνο με συμπληρωμένες τις πρώτες k+1 γραμμές

Εφαρμόζοντας αυτό το θεώρημα n-k φορές βλέπουμε ότι κάθε μερικώς συμπληρωμένο n \times n λατινικό τετράγωνο με συμπληρωμένες τις πρώτες k γραμμές μπορεί να συμπληρωθεί πλήρως για να γίνει λατινικό τετράγωνο.

Απόδειξη: Θα χρησιμοποιήσουμε το θεώρημα του γάμου. Κάθε τετραγωνάκι της k+1 γραμμής ετοιμάζει μια λίστα με τα n-k στοιχεία του \{1,2,\ldots,n\} τα οποία επιτρέπεται να χρησιμοποιήσει. Θέλουμε για κάθε τετραγωνάκι να επιλέξουμε ένα τέτοιο στοιχείο ώστε όλα να είναι διαφορετικά μεταξύ τους. Αρκεί λοιπόν να δείξουμε ότι για κάθε r τετραγωνάκια έχουμε συνολικά τουλάχιστον r στοιχεία από το σύνολο \{1,2,\ldots,n\} τα οποία επιτρέπεται να χρησιμοποιηθούν σε κάποιο από αυτά. Ας υποθέσουμε πως επιτρέπεται να χρησιμοποιηθούν ακριβώς s στοιχεία. Θέλουμε να δείξουμε ότι s \geqslant r. Θα μετρήσουμε όλα τα ζεύγη (a,i) όπου a είναι ένα από τα r τετραγωνάκια και i είναι ένα στοιχείο που επιτρέπεται να τοποθετηθεί στο τετραγωνάκι a. Αφού σε κάθε τετραγωνάκι επιτρέπεται να τοποθετηθούν ακριβώς n-k από τα στοιχεία ο αριθμός των ζευγών είναι ακριβώς r(n-k). Από την άλλη, κάθε στοιχείο που επιτρέπεται να χρησιμοποιηθεί επιτρέπεται να χρησιμοποιηθεί το πολύ σε n-k από τα τετραγωνάκια, αφού βρίσκεται από μία φορά σε κάθε μία από τις πρώτες k γραμμές και άρα βρίσκεται σε ακριβώς k από της στήλες. Άρα ο αριθμός των ζευγών είναι το πολύ s(n-k). Άρα r(n-k) \leqslant s(n-k). \square

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

B) Μια εφαρμογή στην θεωρία παιγνίων

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

Ας το γενικεύσουμε λίγο αυτό το παιγνίδι. Αντί για ένα τρία επί τρία πίνακα, τώρα έχουμε ένα σύνολο X από σημεία και ένα σύνολο L από «ευθείες». Κάθε ευθεία είναι ένα υποσύνολο του X. Οι δυο παίκτες τώρα, διαλέγουν εναλλάξ σημεία από το X και νικητής είναι αυτός που θα διαλέξει πρώτος όλα τα σημεία κάποιας ευθείας. Αν όλα τα σημεία διαλεχθούν χωρίς κάποιος να επιλέξει όλα τα σημεία κάποιας ευθείας τότε το παιγνίδι είναι ισόπαλο.

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

Θεώρημα: Αν κάθε ευθεία αποτελείται από n σημεία και κάθε σημείο ανήκει στο πολύ n/2 ευθείες, τότε κάθε παίκτης έχει στρατηγική ισοπαλίας.

Απόδειξη: Ισχυριζόμαστε ότι για κάθε ευθεία \ell \in L, μπορούμε να επιλέξουμε δύο διαφορετικά σημεία x_{\ell},y_{\ell} που να ανήκουν στην ευθεία ώστε κάθε σημείο να επιλεγεί το πολύ μία φορά. (Δηλαδή αν \ell,\ell' είναι διαφορετικές ευθείες, τότε \{x_{\ell},y_{\ell} \} \cap \{x_{\ell'},y_{\ell'} \} = \emptyset.)

Αν αποδειχθεί ο ισχυρισμός τότε έχουμε μια αρκετά εύκολη στρατηγική ισοπαλίας: Όποτε ο αντίπαλός μας επιλέγει κάποιο σημείο της μορφής x_{\ell}, εμείς επιλέγουμε το y_{\ell}, και αντίστροφα. Άρα ο αντίπαλός μας δεν μπορεί να επιλέξει όλα τα σημεία κάποιας ευθείας.

Για να αποδείξουμε τον ισχυρισμό θα χρησιμοποιήσουμε ένα πόρισμα του θεωρηματος του γάμου, που για ευνόητους λόγους ονομάζεται θεώρημα της διγαμίας.

Θεώρημα διγαμίας: Αν για κάθε σύνολο A αγοριών υπάρχουν τουλάχιστον 2|A| κορίτσια τα οποία αρέσουν σε τουλάχιστον ένα από τα αγόρια του συνόλου A, τότε μπορούμε να παντρέψουμε κάθε αγόρι με δύο κορίτσια της αρεσκείας του ώστε κάθε κορίτσι να παντρευτεί το πολύ ένα αγόρι.

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

Πίσω στον ισχυρισμό μας λοιπόν: Αρκεί από το θεώρημα της διγαμίας να δείξουμε ότι κάθε k ευθείες περιέχουν συνολικά τουλάχιστον 2k σημεία. Χρησιμοποιούμε και πάλι το κόλπο της διπλής απαρίθμησης και μετράμε όλα τα ζεύγη (\ell,x), όπου \ell είναι μια από τις k ευθείες και x είναι ένα σημείο που ανήκει στην \ell. Αφού κάθε ευθεία έχει ακριβώς n σημεία τότε υπάρχουν ακριβώς kn τέτοια ζεύγη. Από την άλλη κάθε σημείο ανήκει το πολύ σε n/2 από τις ευθείες, άρα πρέπει να υπάρχουν τουλάχιστον 2k σημεία που να ανήκουν σε κάποια από τις ευθείες. \square

Γ) Μια εφαρμογή στην θεωρία ομάδων

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

Δίνεται μια πεπερασμένη ομάδα G και μια υποομάδα H με δείκτη k. Υπάρχουν δηλαδή k αριστερά και k δεξιά σύμπλοκα της H στην G τα οποία γενικά μπορεί να διαφέρουν. Ισχύει όμως το εξής: Υπάρχουν στοιχεία g_1,\ldots,g_k της G ώστε τα g_1H,\ldots,g_kH είναι όλα τα αριστερά σύμπλοκα και Hg_1,\ldots,Hg_k είναι όλα τα δεξιά σύμπλοκα. Η απόδειξη αφήνεται ως άσκηση.

Advertisements

About Δημήτρης Χριστοφίδης

Course Leader in Mathematics at UCLan Cyprus.
This entry was posted in 05B15 - Orthogonal arrays, Latin squares, Room squares, 05C70 - Factorization, matching, partitioning, covering and packing, 20F99 - None of the above, but in this section, 91A24 - Positional games, 91A46 - Combinatorial games and tagged . Bookmark the permalink.

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

Φωτογραφία Google+

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

Σύνδεση με %s