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

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

Ας δούμε πρώτα πότε αποτυγχάνουμε σίγουρα. Ένας λόγος που μπορεί να αποτύχουμε είναι αν τα αγόρια είναι περισσότερα από τα κορίτσια. Ένας άλλος λόγος είναι αν υπάρχει κάποιο αγόρι το οποίο δεν δέχεται να παντρευτεί κανένα από τα κορίτσια. Αποτυγχάνουμε επίσης αν υπάρχουν δύο αγόρια τα οποία θέλουν το ίδιο κορίτσι (και κανένα άλλο). Γενικά αν $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$ πράξεις τις οποίες μπορεί να κάνει αρκετά γρήγορα και ένας απλός προσωπικός υπολογιστής.

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

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

Παράθεμα: Το θεώρημα του γάμου (ΙΙ) « Αποδείξεις από το βιβλίο
Ο/Η Αντώνης Κυριακόπουλος λέει:

28 Νοεμβρίου, 2010 στο 20:56

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

Απάντηση
Ο/Η Δημήτρης λέει:

28 Νοεμβρίου, 2010 στο 22:02

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

Απάντηση