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

Φεβρουαρίου 28, 2010

Κομπολόι

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 5:36 μμ

N χάντρες είναι περασμένες στη σειρά σε μια κλωστή. Διαλέγουμε τυχαία ένα ζευγάρι γειτονικές χάντρες και κόβουμε την κλωστή δεξιά και αριστερά τους, απομονώνοντάς τις από τις υπόλοιπες. Συνεχίζουμε να το κάνουμε ώσπου να μείνουν από την κλωστή μόνο κομμάτια με δύο το πολύ χάντρες. Στο τέλος της διαδικασίας λέμε ότι μια χάντρα είναι απομονωμένη αν έχουμε κόψει την κλωστή και δεξιά και αριστερά της. Αν E_N είναι το αναμενόμενο πλήθος των απομονωμένων χαντρών, ποιό είναι το όριο

\displaystyle lim_{N\to\infty}\frac{E_N}{N};

Advertisements

2 Σχόλια »

  1. Έστω ότι οι χάντρες είναι περασμένες στη σειρά έχοντας ‘ονόματα’ 1,2,\ldots , N.
    Έστω X_{N,i}η τυχαία μεταβλητή που παίρνει την τιμή 1,
    αν η i χάντρα είναι απομονωμένη και την τιμή 0 διαφορετικά.
    Τότε E_N = \sum_{i=1}^{N} \mathbb{P}[X_{N,i}=1] := \sum_{i=1}^{N} P_{N,i} .
    Παρατηρείστε ότι P_{N,2} = P_{N,N-1} = 0 .
    Φανταζόμαστε ότι κάποιος ΄άλλος΄ έχει ‘ονομάσει’ τις χάντρες N, N-1, \ldots , 1
    (π.χ. βλέπει τις χάντρες από την πίσω μεριά)
    και ένας τρίτος εκτελεί το πείραμα για λογαριασμό μας.
    Τότε η χάντρα i της δικής μας διάταξης θα είναι απομονωμένη αν και μόνο αν η χάντρα
    N-i+1 του »άλλου» είναι απομωνομένη.
    Αυτό δέιχνει ότι P_{N,i} = P_{N,N-i+1} και άρα P_{N,1} = P_{N,N} := P_N .
    Επίσης -έχοντας τις χάντρες αριθμημένες 1,2,\ldots , N– μπορούμε, αντί να εκτελέσουμε
    το πείραμα απ’ευθείας σε όλες τις χάντρες, να εκτελέσουμε συγχρόνως δύο πειράματα στις
    σειρές 1,2,\ldots , i και i, i+1 , \ldots N. Τότε η χάντρα i θα είναι απομονωμένη αν και μόνο αν
    η χάντρα i είναι απομονωμένη στα δύο επιμέρους πειράματα.
    Αυτό δείχνει ότι P_{N,i} = P_i \cdot P_{N-i+1}.
    Οπότε ο υπολογισμός του E_N ανάγεται στον υπολογισμό της πιθανότητας
    μία εκ των ακραίων χαντρών (π.χ. η 1) να είναι απομονωμένη.
    Οπότε, αν η αρχική επιλογή είναι (i,i+1) εχουμε
    \displaystyle P_N = \sum_{i=1}^{N-1} \mathbb{P}[\text{1 isolated} | (i,i+1)  ] \cdot \mathbb{P}[(i,i+1)] = \frac{1}{N-1} \sum_{i=1}^{N-2} P_i
    άρα (N-1)    P_N =  \sum_{i=1}^{N-2} P_i όπως και (N-2) P_{N-1} =  \sum_{i=1}^{N-3} P_i.
    Αφαιρούμε τις άνω σχέσεις και έχουμε
    P_N =  P_{N-1}  - \frac{1}{N-1} (P_{N-1} - P_{N-2})  . Γνωρίζοντας ότι P_1 = 1 , P_2 = 0 υπολογίζουμε
    P_3 = 1/2 , P_4 = \frac{1}{2} - \frac{1}{2\cdot 3} , P_5 = \frac{1}{2}-\frac{1}{2\cdot 3}+\frac{1}{2\cdot 3 \cdot 4}
    και επαγωγικά P_N = \sum_{i=2}^{N-1} \frac{(-1)^i}{i!} = \sum_{i=0}^{N-1}\frac{(-1)^i}{i!} , N\geq 2,
    που δίδει ότι P_{N,i} = \sum_{k=0}^{i-1} \frac{(-1)^k}{k!} \sum_{m=0}^{N-i} \frac{(-1)^m}{m!} , i=3,...,N-2
    και άρα \lim \frac{E_N}{N} = e^{-2} .

    Μου αρέσει!

    Σχόλιο από henk&christos — Μαΐου 29, 2011 @ 1:14 πμ

  2. Πολύ ωραία λύση!

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Μαΐου 29, 2011 @ 7:24 μμ


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: