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

Ιουλίου 20, 2015

Επί

Filed under: Λυμένα Προβλήματα — Themis Mitsis @ 11:46 μμ

Έστω A και B δυο πεπερασμένα σύνολα με το B να έχει το πολύ τόσα στοιχεία όσα και το A. Διαλέγουμε στην τύχη μια συνάρτηση από το A στο B. Ποια η πιθανότητα να είναι επί;

Advertisements

10 Σχόλια »

  1. Θα μπορούσαμε να σταθεροποιήσουμε τον πληθάριθμο του συνόλου Β (οπότε το Α εξ’ορισμού έχει τουλάχιστον |Β| στοιχεία), και αναλογιζόμαστε το λόγο: (Όλες οι απεικονίσεις που καθιστούν την f επί) προς (Όλες οι δυνατές απεικονίσεις με το |Β| να κυμαίνεται από 1…n, και το |Α| ανάλογα). Να πάρουμε το άθροισμα αυτού του λόγου για n=1 ως άπειρο.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουλίου 21, 2015 @ 2:58 μμ

  2. Το όριο για n τείνει στο άπειρο όχι το άθροισμα (το οποίο βγαίνει παραπάνω από 1). Αυτή είναι μια διαισθητική προσέγγιση.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουλίου 21, 2015 @ 3:10 μμ

  3. Στο 1) Εννοούσα να θέσουμε ένα άνω φράγμα για τον πληθάριθμο του Β, οπότε το Α έχει τουλάχιστον |Β| στοιχεία, αντί για σταθεροποιήσουμε όπως έγραψα. Επίσης παίρνουμε το όριο διότι ο πληθάριθμος και των δύο συνόλων δεν είναι φραγμένος.

    Αρέσει σε 1 άτομο

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουλίου 21, 2015 @ 4:07 μμ

  4. Αυτό που έχω κατά νου είναι αμιγώς πεπερασμένο. Οι πληθάριθμοι των δύο συνόλων είναι σταθεροποιημένοι. Βάζουμε όλες τις απεικονίσεις σε ένα δοχείο και τραβάμε μια στην τύχη. Ποια η πιθανότητα να είναι επί; Ή απάντηση είναι συνάρτηση των δύο πληθάριθμων.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Ιουλίου 21, 2015 @ 11:17 μμ

  5. Έστω ν ο πληθάριθμος του Α και μ ο πληθάριθμος του Β, με 1≤μ≤ν.
    Καθένα από τα ν στοιχείο του Α μπορεί να απεικονίζεται σε ένα από τα μ στοιχεία του Β. Τα συνολικά ενδεχόμενα είναι Ν = μ^ν.
    Μια απεικόνιση από το Α στο Β θα είναι επί, εφόσον καθένα από τα μ στοιχεία του Β αποτελεί εικόνα ενός τουλάχιστον στοιχείου του Α. Εδώ, για τον υπολογισμό του πλήθους των απεικονίσεων επί, θα μπορούσαμε να χρησιμοποιήσουμε την αρχή εγκλεισμού – αποκλεισμού (inclusion-exclusion principle). Με αυτή την προσέγγιση, τα ευνοϊκά ενδεχόμενα είναι:
    Ε = μ^ν – C(μ,1)*(μ-1)^ν + C(μ,2)*(μ-2)^ν – ….. +/- C(μ,μ-1)*1^ν
    Η ζητούμενη πιθανότητα είναι p = Ε/Ν.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — Ιουλίου 22, 2015 @ 1:09 μμ

  6. Φανταστείτε ότι τα στοιχεία του Α είναι σκοπευτές οι οποίοι πυροβολούν, στη τύχη, έναν από τους στρατιώτες του συνόλου Β.
    Ποιά η πιθανότητα να μην υπάρχει επιζήσας/σα στο Β μετά το πέρας των πυροβολισμών;

    Μου αρέσει!

    Σχόλιο από Christos Pelekis — Ιουλίου 22, 2015 @ 1:27 μμ

  7. Καλώς τον φίλο Χρήστο! Ωραία η μεταφορά!

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — Ιουλίου 22, 2015 @ 1:34 μμ

  8. Είναι άξια μνείας πάντως η προτίμησή σου στα happy end θέματα (δηλητηριάσεις, φονικά)

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — Ιουλίου 22, 2015 @ 1:41 μμ

  9. Χρήστο συνδυάζεται το πρόβλημα αυτό με ταιριάσματα (matchings) και το θεώρημα Hall;

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουλίου 22, 2015 @ 8:40 μμ

  10. Νομίζω πως η απάντηση στο ερώτημά σου είναι ναι!

    Μπορεί να διατυπώσει κανεις το θεώρημα του Hall «πυροβολώντας»..

    Έστω G=(X\cup Y, E) διμερές γράφημα τέτοιο ώστε η περιοχή οποιουδήποτε υποσυνόλου του Χ
    έχει τουλαχιστον τόσα στοιχεία όσα και το εν λόγω υποσύνολο.
    Φανταστείτε ότι σε κάθε ακμή του γραφήματος αντιστοιχεί ένα όπλο και ότι εκτελούμε το εξής πείραμα:
    Για κάθε ακμή e=(x,y), x\in X, y\in Y, στρίβουμε ένα τίμιο νόμισμα και αν το αποτέλεσμα είναι κορώνα, τότε
    το όπλο το παίρνει ο/η x και πυροβολεί τον/την y. Αν είναι γράμματα, το όπλο πάει στον y ο οποίος πυροβολεί τον x.
    Οι ρίψεις είναι ανεξάρτητες για κάθε ακμή.

    Έστω Α το ενδεχόμενο «κάθε κορυφή του Χ δέχεται ακριβώς μία σφαίρα».
    Το θεώρημα του Hall λέει ότι η πιθανότητα του Α είναι γνησίως θετική.

    Μου αρέσει!

    Σχόλιο από Christos Pelekis — Ιουλίου 23, 2015 @ 12:43 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

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

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