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

Μαΐου 13, 2008

– Εμπιστεύεστε την τύχη σας;

Ο Paul Erdős (ουγγρικά: Erdős Pál) υπήρξε από τους πρωτεργάτες και ο κυριότερος προπαγανδιστής της λεγόμενης «πιθανοθεωρητικής μεθόδου» (probabilistic method) στα μαθηματικά και ιδιαίτερα σε αυτό που σήμερα ονομάζεται «διακριτά μαθηματικά» (θεωρία αριθμών, συνδυαστική, θεωρητική επιστήμη υπολογιστών). Η πρωσοποποίηση της ιδιορρυθμίας, ο Erdős έζησε μια ζωή γεμάτη μαθηματικά και μόνο, τα οποία σημάδεψε με δεκάδες σημαντικά αποτελέσματα και εκατοντάδες συνεργασίες σε όλο τον κόσμο.

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

Υποθέστε ότι έχετε ένα πλήρες γράφημα με n κορυφές (n σημεία δηλ. που όλα ενώνονται με όλα τα άλλα, με πλήθος ακμών {n \choose 2}) και ότι κάθε ακμή του μπορεί να βαφεί κόκκινη ή μπλε. Δείξτε ότι μπορείτε να επιλέξετε τα χρώματα των ακμών έτσι ώστε το πλήθος των μονοχρωματικών τριγώνων που σχηματίζονται να είναι το πολύ \frac{1}{4} {n \choose 3}.

Advertisements

7 Σχόλια »

  1. Υπόδειξη:

    Χρωματίστε κάθε κορυφή κόκκινη ή μπλέ ρίχνοντας ένα νόμισμα. Δείξτε ότι ο χρωματισμός που προκύπτει έτσι έχει την ιδιότητα που ζητάμε με θετική πιθανότητα.

    Γενικό σχόλιο:

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαΐου 18, 2008 @ 2:09 μμ

  2. Μόνο που η απάντηση είναι \frac{1}{4}\binom{n}{3}.

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Απρίλιος 27, 2009 @ 12:17 πμ

  3. Σωστό, ευχαριστώ για τη διόρθωση. Το \frac{1}{4}{n \choose 3} είναι το 1/4 του αριθμού όλων των τριγώνων που υπάρχουν.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 27, 2009 @ 7:48 πμ

  4. Να βάλω μια λύση σε αυτό. (Τα προβλήματα «Ικανοποίηση» και «Μονόδρομοι» (για μεγάλα ν) μπορούν να λυθούν με παρόμοιο τρόπο.)

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

    Έστω Χ ο αριθμός που ενδιαφερόμαστε, το πλήθος δηλαδή των μονοχρωματικών τριγώνων. Θα αρκούσε να δείξουμε ότι \mathbb{P}(X \leqslant \frac{1}{4}\binom{n}{3}) > 0. Όπως λέει και η υπόδειξη όμως, αυτή η πιθανότητα δύσκολα υπολογίζεται.

    Μπορούμε όμως πολύ εύκολα να υπολογίσουμε την μέση τιμή του Χ. Όντως υπάρχουν \binom{n}{3} τρίγωνα και η πιθανότητα κάθε τρίγωνο να είναι μονοχρωματικό είναι 1/4. (1/8 μπλε και 1/8 κόκκινο) Άρα \mathbb{E}(X) = \frac{1}{4}\binom{n}{3}. Λίγο πιο αναλυτικά: Έχουμε X = \sum\limits_{a \in A} I_a, όπου Α είναι το σύνολο όλων των τριγώνων, και για κάθε τρίγωνο α, I_a ισούται με 1 αν το α είναι μονοχρωματικό και 0 αν δεν είναι. Επειδή η μέση τιμή του αθροίσματος είναι το άθροισμα των μέσων τιμών έχουμε \mathbb{E}(X )= \sum\limits_{a \in A} \mathbb{E}(I_a) = \sum\limits_{a \in A} \mathbb{P}(a monochromatic) = \sum\limits_{a \in A} \frac{1}{4} = \frac{1}{4}\binom{n}{3}.

    Άρα κατα μέσο όρο υπάρχουν ακριβώς \frac{1}{4}\binom{n}{3} μονοχρωματικά τρίγωνα. Άρα σίγουρα πρέπει να υπάρχει χρωματισμός με το πολύ τόσα μονοχρωματικά τρίγωνα.

    (Υπάρχει επίσης χρωματισμός με λιγότερα από \frac{1}{4}\binom{n}{3} μονοχρωματικά τρίγωνα. Γιατί;)

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Απρίλιος 27, 2009 @ 11:53 πμ

  5. Σωστά.

    Κι αν θέλουμε και να βρούμε ένα τέτοιο χρωματισμό;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 27, 2009 @ 11:56 πμ

  6. Ελέγχουμε όλους τους 2^{\binom{n}{2}} χρωματισμούς και κάποτε θα τελειώσουμε. Για ν=20, έχουμε να ελέγξουμε μόνο 2^{190} > 10^57 χρωματισμούς. Δεδομένου ότι ο πιο γρήγορος υπολογιστής στον κόσμο κάνει περίπου 10^15 πράξεις το δευτερόλεπτο, θα του πάρει μόλις 10^34 χρονάκια να τελειώσει…

    Υπάρχει όμως τρόπος βασισμένος στην πιο πάνω απόδειξη για να τελειώσουμε πιο γρήγορα.

    Υπόδειξη: Χρωματίζουμε τις πλευρές μια προς μια. Κάθε φορά διαλέγουμε το κατάλληλο χρώμα ώστε…

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Απρίλιος 27, 2009 @ 1:27 μμ

  7. Να προσθέσω ότι μπορούμε να αποφύγουμε τα πιο πάνω και να δώσουμε άμεση κατασκευή. Στο πρόβλημα «Ικανοποίηση» όμως νομίζω πως δεν είναι γνωστό πως μπορούν να αποφευχθούν τέτοιες μεθόδοι.

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Απρίλιος 27, 2009 @ 8:58 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Blog στο WordPress.com.

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