5.24 Ο νόμος των μεγάλων αριθμών, πιθανοθεωρητικές μέθοδοι στη συνδυαστική - Πέ, 1/11/2001

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

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

Theorem 1   Έστω $n$ σημεία στο επίπεδο που συνδέονται ανά δύο με ένα ευθύγραμμο τμήμα. Μπορούμε τότε να χρωματίσουμε τα ευθύγραμμα τμήματα (τις ακμές) με χρώματα κόκκινο ή μπλέ έτσι ώστε το πλήθος των μονοχρωματικών τριγώνων που σχηματίζονται να είναι το πολύ ${1\over 4}{n \choose 3}$.

Είδαμε επίσης, σε κάποια λεπτομέρεια, πώς μπορεί κανείς να πάρει την υπαρξιακή αυτή απόδειξη που δώσαμε και να την μετατρέψει σε ένα "αποτελεσματικό" αλγόριθμο.