Προβλήματα Μαθηματικών

Μαΐου 4, 2008

Ομαδικός Γάμος

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 6:14 μμ

Έχουμε ένα σύνολο A από n άνδρες κι ένα σύνολο \Gamma από n γυναίκες. Κάθε άνδρας αποδέχεται ως σύζυγό του ακριβώς r από τις γυναίκες και κάθε γυναίκα αποδέχεται ως σύζυγό της ακριβώς r από τους άνδρες (r\ge 1 είναι ο ίδιος αριθμός για κάθε άτομο). Τα σύνολα των αποδεκτών συζύγων για κάθε άτομο είναι κατά τα άλλα τυχαία.

Θεωρούμε ότι κάθε αποδοχή είναι αμοιβαία: όταν λέμε ότι ο Χ αποδέχεται την Υ ως σύζυγό του θεωρούμε ότι και η Υ δέχεται τον Χ ως σύζυγό της (έχουν «μιλήσει» πριν).

Δείξτε ότι υπάρχει μια 1-1 και επί απεικόνιση

w:A\to \Gamma,

τέτοια ώστε για κάθε x \in A η γυναίκα w(x) είναι μια αποδεκτή σύζυγος για τον x και ο x είναι ένας αποδεκτός σύζυγος για την w(x).

Advertisements

4 Σχόλια »

  1. Έστω K ένα υποσύνολο του A που περιέχει k άντρες.
    Έστω επίσης M το σύνολο των γυναικών στο οποίο μια γυναίκα ανήκει αν και μόνο αν υπάρχει άντρας του K που τη θεωρεί αποδεκτή και m το πλήθος των γυναικών αυτών.
    Αριθμούμε τους άντρες του K με τους αριθμούς 1,2,\cdots,k και τις γυναίκες του M με τους αριθμούς 1,2,\cdots,m. Θεωρούμε έναν πίνακα k\times m ο οποίος στη θέση (i,j) έχει μονάδα αν ο i άντρας θεωρεί αποδεκτή την j γυναίκα και μηδέν διαφορετικά. Κάθε γραμμή του πίνακα έχει r μονάδες, αφού περιέχονται στο M όλες οι γυναίκες που θεωρούν αποδεκτές οι άντρες του K,οπότε όλος ο πίνακας περιέχει ακριβώς k\cdot r μονάδες.
    Αν x_j το πλήθος των μονάδων της j στήλης τότε ισχύουν
    x_1+...+x_m=k\cdot r (όλες οι μονάδες) και
    x_1+...+x_m\le m\cdot r ,επειδή κάθε γυναίκα θεωρεί αποδεκτούς r άντρες από το A άρα το πολύ r άντρες από το K.
    Από τις δύο αυτές σχέσεις βγάζουμε ότι k\le m.
    Συνεπώς ικανοποιούνται οι συνθήκες του θεωρήματος του γάμου και εφαρμόζοντάς το προκύπτει το ζητούμενο.

    Μου αρέσει!

    Σχόλιο από steliosdes — Μαΐου 4, 2008 @ 9:51 μμ

  2. Πολύ ωραία.

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

    Φαινομενικά θα έπρεπε τώρα να είναι ευκολότερο να τους παντρέψουμε όλους.

    Δείξτε όμως ότι το συμπέρασμα μπορεί να μην ισχύει με αυτή την υπόθεση.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 4, 2008 @ 10:08 μμ

  3. Έστω n=3, r=1 και a1,a2,a3 οι άντρες και g1,g2,g3 οι γυναίκες.
    Αν οι a1, a2 θεωρούν αποδεκτή μόνο τη g1 και ο a3 τις θεωρεί όλες αποδεκτές τότε εύκολα βλέπουμε ότι δε μπορούμε να τους παντρέψουμε και να είναι όλοι ικανοποιημένοι, γιατί αναγκαστικά κάποιος από τους a1,a2 θα μείνει παραπονεμένος.

    Μου αρέσει!

    Σχόλιο από steliosdes — Μαΐου 4, 2008 @ 10:41 μμ

  4. Σωστό.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 4, 2008 @ 10:56 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: