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

Έχουμε μια ομάδα αγοριών τα οποία θέλουμε να τα παντρέψουμε με κάποια κορίτσια. Αυτό θα γίνει με τον εξής τρόπο: Κάθε αγόρι ετοιμάζει μια λίστα με όλα τα κορίτσια τα οποία θα δεχόταν να παντρευτεί. Σκοπός μας είναι να καταφέρουμε να παντρέψουμε κάθε αγόρι με κάποιο κορίτσι από την λίστα του. Κάτω από ποιες συνθήκες μπορούμε να το πετύχουμε αυτό; (Το πρόβλημα αφορά μια ανδροκρατούμενη κοινωνία όπου τα κορίτσια δεν έχουν λόγο. Όσες θέλουν μπορούν να σκεφτούν το αντίστοιχο πρόβλημα μιας γυναικοκρατούμενης κοινωνίας.)

Ας δούμε πρώτα πότε αποτυγχάνουμε σίγουρα. Ένας λόγος που μπορεί να αποτύχουμε είναι αν τα αγόρια είναι περισσότερα από τα κορίτσια. Ένας άλλος λόγος είναι αν υπάρχει κάποιο αγόρι το οποίο δεν δέχεται να παντρευτεί κανένα από τα κορίτσια. Αποτυγχάνουμε επίσης αν υπάρχουν δύο αγόρια τα οποία θέλουν το ίδιο κορίτσι (και κανένα άλλο). Γενικά αν A είναι ένα σύνολο αγοριών και N(A) είναι το σύνολο όλων των κοριτσιών που βρίσκονται σε κάποια από τις λίστες των αγοριών του συνόλου A τότε για να μην αποτύχουμε πρέπει οπωσδήποτε να έχουμε |N(A)| \geqslant |A|. Αυτή η συνθήκη περιλαμβάνει όλους τους λόγους αποτυχίας που έχουμε αναφέρει μέχρι στιγμής. Αν π.χ. το A περιλαμβάνει ακριβώς ένα αγόρι τότε το N(A) είναι η λίστα όλων των κοριτσιών που βρίσκονται στην λίστα αυτού του αγοριού και η συνθήκη |N(A)| \geqslant |A| μας λέει ότι αυτή η λίστα πρέπει να περιλαμβάνει τουλάχιστον ένα κορίτσι.

Το θεώρημα του γάμου (ή θεώρημα του Hall) λέει το αντίστροφο. Αν για κάθε σύνολο αγοριών A ισχύει ότι |N(A)| \geqslant |A| τότε μπορούμε να παντρέψουμε κάθε αγόρι με ένα κορίτσι της αρεσκείας του.

Με άλλα λόγια: Η προφανής αναγκαία συνθήκη είναι και ικανή.

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

Απόδειξη 1: Αυτή η απόδειξη είναι των Halmos και Vaughan. Θα αποδείξουμε το θεώρημα με επαγωγή στον αριθμό n των αγοριών. Για n=1 το θεώρημα είναι προφανές. Έστω λοιπόν ότι έχουμε n αγόρια και ότι το θεώρημα ισχύει για κάθε k < n.

Υποθέτουμε πρώτα ότι για κάθε σύνολο αγοριών A με 0 < |A| < n ισχύει η ισχυρότερη συνθήκη |N(A)| \geqslant |A| + 1. Παίρνουμε ένα οποιοδήποτε αγόρι και το παντρεύουμε με οποιοδήποτε κορίτσι της αρεσκείας του. Κοιτάμε όσα αγόρια απομένουν και αφαιρούμε από την λίστα τους το κορίτσι που ήδη παντρέψαμε. Τώρα έχουμε n-1 αγόρια και η αρχική συνθήκη εξακολουθεί να ικανοποιείται. Άρα επαγωγικά μπορούμε να παντρέψουμε αυτά τα αγόρια.

Μένει να ελέγξουμε την περίπτωση όπου υπάρχει σύνολο αγοριών A με 0 < |A| < n για το οποίο ισχύει ότι |N(A)| = |A|. Επειδή |A| < n και για κάθε υποσύνολο B του A ισχύει |B| \leqslant N(B), μπορούμε να παντρέψουμε όλα τα αγόρια του συνόλου A με κορίτσια της αρεσκείας τους. Μένει να παντρέψουμε τα υπόλοιπα n - |A| αγόρια. Για κάθε υποσύνολο C αυτών των αγοριών έχουμε |N(A \cup C)| \geqslant |A \cup C| = |A| + |C| και άρα |C| \leqslant |N(A \cup C)| - |A|. Η τελευταία ανισότητα μας λέει ότι ακόμη και όταν αφαιρέσουμε τα |A| κορίτσια που ήδη παντρέψαμε από τις λίστες των υπόλοιπων αγοριών οι λίστες θα εξακολουθούν να είναι αρκετά μεγάλες ώστε να ικανοποιείται η αρχική συνθήκη. Άρα επαγωγικά μπορούμε να παντρέψουμε και τα υπόλοιπα αγόρια με κορίτσια της αρεσκείας τους. \square

Παρόλο που η πιο πάνω απόδειξη είναι εξαιρετικά όμορφη και σίγουρα είναι «από το βιβλίο», υπάρχει ένα μικρό πρόβλημα όσον αφορά τις πρακτικές εφαρμογές: Έστω ότι έχουμε 100 αγόρια και μας φέρει το κάθε αγόρι την λίστα του. Σκοπός μας τώρα είναι είτε να βρούμε πως να τους παντρέψουμε είτε να τους αποδείξουμε ότι αυτό δεν γίνεται. Βρίσκοντας π.χ. 53 αγόρια που έχουν συνολικά 52 κορίτσια στις λίστες τους. Ένας τρόπος για να βρούμε αν γίνεται ο γάμος ή όχι είναι να κοιτάξουμε όλα τα υποσύνολα αγοριών για να δούμε αν πράγματι ικανοποιείται η συνθήκη. Πόσα όμως υποσύνολα αγοριών υπάρχουν; Ακριβώς 2^{100}. (Αποφασίζουμε για κάθε αγόρι ξεχωριστά αν θα είναι ή όχι στην λίστα.) Ο αριθμός 2^{100} είναιι τεράστιος. Επειδή 2^{10} = 1024 > 10^3 έχουμε 2^{100} > 10^{30}, ένας αριθμός με τουλάχιστον τριάντα μηδενικά. Οι ταχύτεροι υπολογιστές κάνουν αυτην την στιγμή περίπου 10^{15} πράξεις το δευτερόλεπτο. Ένας τέτοιος υπερυπολογιστής θα ήθελε 10^{15} δευτερόλεπτα για να ελέγξει όλα τα υποσύνολα. Με άλλα λόγια θα ήθελε τουλάχιστον τριάντα εκατομμύρια χρόνια για να τελειώσει τον έλεγχο! Άντε χαριστικά αν φτιάξουμε ένα υπερυπολογιστή με δεκαπλάσια ταχύτητα να χρειαστεί «μόνο» τρία εκατομμύρια χρόνια.

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

Απόδειξη 2: Έστω ότι έχουμε ήδη αρραβωνιάσει κάποια αγόρια με κάποια κορίτσια. Παίρνουμε ένα αγόρι x_0 που δεν είναι αρραβωνιασμένο. Υπάρχει τουλάχιστον ένα κορίτσι y_1 στην λίστα του x_0. Αν το y_1 δεν είναι αρραβωνιασμένο, τότε τους αρραβωνιάζουμε. Ας υποθέσουμε πως είναι αρραβωνιασμένο με το αγόρι x_1. Οι λίστες των x_0 και x_1 έχουν συνολικά τουλάχιστον δύο κορίτσια. Έστω λοιπόν y_2 ένα κορίτσι διαφορετικό από το y_1 που να ανήκει σε τουλάχιστον μία από τις δύο λίστες. Αν το y_2 δεν είναι αρραβωνιασμένο τότε είτε θα ανήκει στην λίστα του x_0 και τους αρραβωνιάζουμε είτε θα ανήκει στην λίστα του x_1 (αλλά όχι του x_0) και σε αυτήν την περίπτωση σπάμε τον αρραβώνα του x_1 με την y_1 και αρραβωνιάζουμε τον x_0 με την y_1 και τον x_1 με την y_2. Γενικά αν ισχύει η συνθήκη τότε μπορούμε να βρούμε αγόρια x_0,x_1,\ldots,x_k και κορίτσια y_1,\ldots,y_k ώστε
– Ο x_0 δεν είναι αρραβωνιασμένος.
– Η y_i είναι αρραβωνιασμένη με τον x_i για κάθε 1 \leqslant i \leqslant k-1
– H y_i ανήκει στην λίστα κάποιου εκ των x_0,x_1,\ldots,x_{i-1} για κάθε 1 \leqslant i \leqslant k.
– H y_k δεν είναι αρραβωνιασμένη.
Τότε κάνουμε το εξής: Βρίσκουμε ένα από τα αγόρια x_0,\ldots,x_{k-1} που να έχει στην λίστα την y_k. Έστω το x_{i_1}. Σπάμε τον αρραβώνα του x_{i_1} με την y_{i_1} και τον αρραβωνιάζουμε με την y_k. Μετά βρίσκουμε ένα από τα αγόρια x_0,\ldots,x_{i_1-1} που να έχει στην λίστα την y_{i_1}. Έστω το x_{i_2}. Σπάμε τον αρραβώνα του x_{i_2} με την y_{i_2} και τον αρραβωνιάζουμε με την y_{i_1} κ.τ.λ. Επειδή k > i_1 > i_2 > \ldots αυτή η διαδικασία θα σταματήσει μετά από r βήματα (για κάποιο r) στο i_r = 0. Σε αυτήν την περίπτωση αρραβωνιάζουμε τον x_0 με την y_{i_{r-1}}. Έτσι έχουμε σπάσει r-1 αρραβώνες αλλά έχουμε κάνει r καινούργιος αρραβώνες. Αυξήσαμε λοιπόν τον αριθμό των αρραβώνων κατά ένα. Επαναλαμβάνουμε μέχρι να έχουμε n αρραβώνες. \square

Μπορεί να ελεγχθεί ότι αν έχουμε n αγόρια τότε ο αλγόριθμος βρίσκει τα ζητούμενα ζευγάρια κάνοντας το πολύ 100n^3 πράξεις. (Το 100 εδώ είναι κάπως αυθαίρετο και με λίγη προσοχή μπορεί να μειωθεί αρκετά. Το σημαντικό εδώ είναι το n^3.) Για 100 αγόρια ο αλγόριθμος θέλει 10^8 πράξεις τις οποίες μπορεί να κάνει αρκετά γρήγορα και ένας απλός προσωπικός υπολογιστής.

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

Advertisements

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

Course Leader in Mathematics at UCLan Cyprus.
This entry was posted in 05C70 - Factorization, matching, partitioning, covering and packing and tagged . Bookmark the permalink.

3 Responses to Το θεώρημα του γάμου

  1. Παράθεμα: Το θεώρημα του γάμου (ΙΙ) « Αποδείξεις από το βιβλίο

  2. Ο/Η Αντώνης Κυριακόπουλος λέει:

    Δημήτρη.
    Είναι πολύ ωραία αυτά που γράφεις εδώ.
    Βρίσκω την ευκαιρία, μια και δεν έχω άλλο τρόπο να επικοινωνήσω μαζί σου, να σε ρωτήσω πού είσαι και με τι ασχολείσαι. Επειδή οι παρεμβάσεις σου μου αρέσουν, θα ήθελα, αν βέβαια θέλεις και εσύ, να μου στείλεις το e-mail σου.

  3. Ο/Η Δημήτρης λέει:

    Αντώνη, ευχαριστώ πολύ. Έχει αρκετό καιρό που δεν ανανέωσα το ιστολόγιο (αν και έχω κάποια άρθρα μισοέτοιμα) λόγω έλλειψης χρόνου. Ίσως από το 2011 να ξαναρχίσω να ανεβάζω άρθρα. Θα σου στείλω e-mail για τα υπόλοιπα.

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s