Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

dement · #1

Η φανταστική πόλη Sapi εκτείνεται σε ολόκληρο το καρτεσιανό επίπεδο. Οι δρόμοι της αντιστοιχούν στις ευθείες x = n

και

, όπου

τυχαίος ακέραιος. Έτσι, οι διασταυρώσεις της είναι ακριβώς τα σημεία με ακέραιες συντεταγμένες. Επιπλέον, η πόλη διασχίζεται από τον ποταμό Orna ο οποίος αντιστοιχεί στην ευθεία $\displaystyle y = x + \frac{1}{2}$ (βλ. σχήμα).

: sapi.png (19.02 KiB) Προβλήθηκε 3112 φορές

Η Αλέσσια ξεκινάει από τη διασταύρωση (0,0)

και κινείται πάντα είτε βόρεια είτε ανατολικά.

1. Να βρεθεί ο αριθμός των δυνατών διαδρομών από τις οποίες μπορεί να φτάσει στο σημείο (a,b)

χωρίς να διασχίσει το ποτάμι.

2. Έστω ότι η Αλέσσια, σε κάθε διασταύρωση, αποφασίζει να κινηθεί ανατολικά με πιθανότητα

και βόρεια με πιθανότητα q = 1 - p

. Να αποδειχθεί ότι η πιθανότητα να διασχίσει τουλάχιστον μία φορά το ποτάμι σε μία διαδρομή με

διασταυρώσεις είναι μικρότερη ή ίση με $\displaystyle \frac{q}{p}$ .

Al.Koutsouridis · #2

Το πρώτο ερώτημα μπορεί να λυθεί με το λεγόμενο λήμμα της αντανάκλασης.

Αρχικά βρίσκουμε το σύνολο των διαδρομών από το σημείο (0,0)

στο

ανεξαρτήτως αν περνάμε το ποτάμι ή όχι.

Οποιαδήποτε διαδρομή από το σημείο (0,0)

στο

αποτελείται από

κινήσεις ανατολικά και

κινήσεις βόρεια. Οπότε το πλήθος τέτοιων διαδρομών ισούται με τον αριθμό των τρόπων να διαλέξουμε από a+b

αριθμό κινήσεων,

κινήσεις βόρεια. Δηλαδή $\binom{a+b}{b} = \binom{a+b}{a}$ τρόποι.

Από αυτές θα πρέπει να αφαιρέσουμε όσες διασχίζουν το ποτάμι. Για να το βρούμε χρησιμοποιούμε το ακόλουθο λήμμα.

Λήμμα (αντανάκλασης). Το πλήθος των διαδρομών από το σημείο (0,0)

στο

( $a\geq b$ ) που υπερβαίνουν την ευθεία y=x

ισούται με το πλήθος των διαδρομών από το σημείο (0,0)

στο

.

Απόδειξη. Θα δημιουργήσουμε μια 1-1 αντιστοιχία μεταξύ των δυο παραπάνω συνόλων διαδρομών. Οποιαδήποτε διαδρομή που υπερβαίνει την ευθεία y=x

θα τέμνει και την ευθεία y=x+1

. Εξετάζουμε το πρώτο σημείο τομής με αυτή την ευθεία και πάιρνουμε την συμμετρική διαδρομή από αυτό το σημείο και ύστερα μέχρι το (a,b)

ως προς την ευθεία y=x+1

. Αυτή η συμμετρική διαδρομή καταλλήγει στο σημείο (b-1,a+1)

. Ομοίως και η αντίστροφή αντιστοιχία.

: sns_2014_15_3.png (51.34 KiB) Προβλήθηκε 3007 φορές

Στο πρόβλημά μας, από την στιγμή που το ποτάμι βρίσκεται πάνω στην ευθεία $y=x+\dfrac{1}{2}$ σημαίνει ότι το διασχίζουμε όταν υπερβαίνουμε την ευθεία y=x

. Άρα μπορούμε να εφαρμόσουμε το παραπάνω λήμμα και οι ζητούμενοι τρόποι είναι

$\binom{a+b}{a}-\binom{a+b}{a+1} = \dfrac{(a+b)!}{(a+1)!b!}(a-b+1)$

Να σημειώσουμε ότι για a=b

ο παραπάνω τύπος δίνει τους αριθμούς Catalan.

dement · #3

Πολύ ωραία. Απομένει το δεύτερο ερώτημα.

mikemoke · #4

dement έγραψε:Η φανταστική πόλη Sapi εκτείνεται σε ολόκληρο το καρτεσιανό επίπεδο. Οι δρόμοι της αντιστοιχούν στις ευθείες και , όπου τυχαίος ακέραιος. Έτσι, οι διασταυρώσεις της είναι ακριβώς τα σημεία με ακέραιες συντεταγμένες. Επιπλέον, η πόλη διασχίζεται από τον ποταμό Orna ο οποίος αντιστοιχεί στην ευθεία $\displaystyle y = x + \frac{1}{2}$ (βλ. σχήμα).

sapi.png

Η Αλέσσια ξεκινάει από τη διασταύρωση και κινείται πάντα είτε βόρεια είτε ανατολικά.

1. Να βρεθεί ο αριθμός των δυνατών διαδρομών από τις οποίες μπορεί να φτάσει στο σημείο χωρίς να διασχίσει το ποτάμι.

2. Έστω ότι η Αλέσσια, σε κάθε διασταύρωση, αποφασίζει να κινηθεί ανατολικά με πιθανότητα και βόρεια με πιθανότητα . Να αποδειχθεί ότι η πιθανότητα να διασχίσει τουλάχιστον μία φορά το ποτάμι σε μία διαδρομή με διασταυρώσεις είναι μικρότερη ή ίση με $\displaystyle \frac{q}{p}$ .

Το δενδροδιάγραμμα για μπλε σημεία
Για τα κόκκινα οι διακλαδώσεις προκύπτουν αν αφαιρέσουμε απο τις μπλε( που βρίσκονται στην ίδια κατακόρυφη) τον αριθμό των διακλαδώσεων του προηγούμενο βήματος (των μπλέ)
για τα κιτρινα 2 φορέσ αυτόν τον αριθμό ,για τα πράσινα 3 και πάει λέγοντας

Al.Koutsouridis · #5

Διαγραφή ανάρτησης λόγω λάθους συλλογισμού.

dement · #6

Αλέξανδρε (;), έχω την εντύπωση ότι το λήμμα της αντανάκλασης τώρα δεν προσφέρεται τόσο για την περίπτωσή μας. Δύο μονοπάτια που αντιστοιχίζονται από το λήμμα ταυτίζονται μέχρι το ποτάμι και στη συνέχεια ο βορράς γίνεται ανατολή και τούμπαλιν, μέχρι το επόμενο πέρασμα και πάει λέγοντας. Η ασυμμετρία που εισάγεται από τις διαφορετικές τιμές των p, q

χαλάει τη δουλειά...

Α, και η κοπέλα λέγεται Αλέσσια.

Al.Koutsouridis · #7

dement έγραψε:Αλέξανδρε (;), έχω την εντύπωση ότι το λήμμα της αντανάκλασης τώρα δεν προσφέρεται τόσο για την περίπτωσή μας. Δύο μονοπάτια που αντιστοιχίζονται από το λήμμα ταυτίζονται μέχρι το ποτάμι και στη συνέχεια ο βορράς γίνεται ανατολή και τούμπαλιν, μέχρι το επόμενο πέρασμα και πάει λέγοντας. Η ασυμμετρία που εισάγεται από τις διαφορετικές τιμές των χαλάει τη δουλειά...

Α, και η κοπέλα λέγεται Αλέσσια.

Αλέσσια ωραίο όνομα, δε θα έπρεπε να κάνω λάθος, στο πρόβλημα συγχωρείται

.

Μια δεύτερη σκέψη που χρονικά ήταν η πρώτη που έκανα είναι να θεωρήσουμε το συμπληρωματικό ενδεχόμενο A{'}

και να δείξουμε ότι $P(A{'} ) \geq 1-\dfrac{q}{p}$ (1).

Το A{'}

είναι το ενδεχόμενο σε

κινήσεις να μην διέσχισε το ποτάμι ούτε μια φορά. Παρατηρούμε ότι για τα σημεία πάνω από την y=x

θα πρέπει να αναγκαστηκά να το διασχίσει οπότε το ενδεχόμενο αυτό θα αποτελείτε από τις διαδρομές στα σημεία της ευθείας y= -x+n

που βρίσκονται κάτω από την ευθεία y = x+1

και δεν διασχίζουν το ποτάμι.

Από το πρώτο ερώτημα για κάθε τέτοιο σημείο οι δυνατοί τρόποι για το προσεγγίσουμε είναι

$\binom{a+b}{a}-\binom{a+b}{a+1}$ (2) . Τα σημεία προς εξέταση είναι τα (n,0) , (n-1,1) , ... , (n-k,k)

όπου $k = \left \lfloor \dfrac{n}{2} \right \rfloor$ .

Εφαρμόζοντας την (2) για τα παραπάνω σημεία αντίστοιχα βρίσκουμε

$[ \binom{n}{n} -\binom{n}{n+1} ]$ τρόποι με πιθανότητα $p^{n}q^{0}$ γιατί κινούμαστε

κινήσεις ανατολικά και 0 κινήσεις βόρεια. Ομοίως για τα άλλα σημεία

$[ \binom{n}{n-1} -\binom{n}{n} ] p^{n-1}q^{1}$

$[ \binom{n}{n-2} -\binom{n}{n-1} ] p^{n-2}q^{2}$

....

$[ \binom{n}{n-k} -\binom{n}{n-k-1} ] p^{n-k-1}q^{k}$

Πολλαπλασιάζοντας και διαιρώντας τους όρους με το (-) με $\dfrac{p}{q}$ και αθροίζοντας τις παραπάνω πιθανότητες βρίσκουμε

$\sum_{i=n-k}^{n} \binom{n}{i} p^{i}q^{n-i} - \dfrac{q}{p} [ \sum_{i=n-k-1}^{n} \binom{n}{i} p^{i}q^{n-i} ]$ (3)

Αν

η αθροιστική συνάρτηση κατανομής της διωνυμικής κατανομής τότε η (1) με την βοήθεια της (3) μπορεί να γραφεί

$p (1-F(X \leq n-k-1)) - q(1-F(X \leq n-k) \geq p(1-\dfrac{q}{p}) \Leftrightarrow$

$(p-q) + (qF(X \leq n-k) -p F(X \leq n-k-1))) \geq (p-q)$

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

...

Ελπίζω να είναι σωστά τώρα τουλάχιστον.

#8

Έστω

η ζητούμενη πιθανότητα. Τότε r = q + pr'

, όπου

είναι η πιθανότητα να διασχίσουμε το ποτάμι ξεκινώντας από το (1,0)

και κάνοντας n-1

κινήσεις. Για να το επιτύχουμε όμως αυτό πρέπει πρώτα να διασχίσουμε το υποθετικό ποτάμι με εξίσωση y=x-1/2

, και μετά ο πραγματικό ποτάμι με εξίσωση y=x+1/2

. Από συμμετρία, η πιθανότητα να διασχίσουμε το υποθετικό ποτάμι είναι το πολύ

. (Στην πραγματικότητα είναι μικρότερη του

αφού έχουμε μόνο n-1

κινήσεις.) Μόλις διασχίσουμε το υποθετικό ποτάμι, θα βρισκόμαστε σε ένα σημείο της μορφής (m,m)

. Τότε πρέπει να διασχίσουμε το κανονικό ποτάμι σε n-2m

κινήσεις και η πιθανότητα να το πετύχουμε αυτό είναι πάλι το πολύ

. Τα δύο τελευταία ενδεχόμενα είναι ανεξάρτητα οπότε $r' \leqslant r^2$ . Άρα $r \leqslant q + pr^2$ ή ισοδύναμα $(1-r)(q-pr) \geqslant 0$ . Όμως $r \neq 1$ αφού με πιθανότητα p^n

κινούμαστε πάντα ανατολικά. Άρα πρέπει $r \leqslant q/p$ .

Μπορεί να δειχθεί το εξής: Η πιθανότητα να διασχίσουμε το ποτάμι αν κάνουμε άπειρα βήματα με τον ίδιο τρόπο, ισούται με

αν $q \geqslant p$ και ισούται με q/p

αν

.

dement · #9

Demetres έγραψε: Μπορεί να δειχθεί το εξής: Η πιθανότητα να διασχίσουμε το ποτάμι αν κάνουμε άπειρα βήματα με τον ίδιο τρόπο, ισούται με αν $q \geqslant p$ και ισούται με αν .

Έτσι το έκανα εγώ. Η πιθανότητα να διασχίσουμε για πρώτη φορά το ποτάμι από το σημείο (m,m)

είναι $q \cdot C_m \cdot (pq)^m$ , όπου C_m

ο αντίστοιχος αριθμός Catalan. Αθροίζοντας για όλα τα

παίρνουμε τη γεννήτρια συνάρτηση της ακολουθίας Catalan για x=pq

και το άπειρο άθροισμα ισούται με

$\displaystyle q \frac{1 - \sqrt{1-4pq}}{2pq} = \frac{\min(q,p)}{p}$

#10

Για ποικιλία λοιπόν ας βάλω ακόμη μία απόδειξη:

Ισοδύναμα, ξεκινάμε από τον ακέραιο

και σε κάθε βήμα είτε προσθέτουμε

με πιθανότητα

είτε αφαιρούμε

με πιθανότητα

. Μας ενδιαφέρει αν θα καταφέρουμε σε

βήματα να φτάσουμε στο

.

Θα γράψω p_m

για την πιθανότητα, αν ξεκινήσω από τον φυσικό

, να καταλήξω στο

αν ακολουθώ την πιο πάνω διαδικασία επ' άπειρον.

Ασφαλώς είναι p_0 = 1

. Επίσης είναι $p_m = pp_{m+1} + qp_{m-1}$ . Η χαρακτηριστική εξίσωση είναι η px^2-x+q = 0

που έχει ρίζες τα x=1

και

.

Άρα παίρνουμε p_m = A + B(q/p)^m

για κάποιες σταθερές A,B

. Η περίπτωση m=0

δίνει

. Καταλήγουμε λοιπόν στην p_m = (q/p)^m + A(1-(q/p)^m)

.

Στην περίπτωση όπου q = p

τα πράγματα είναι απλά αφού έχουμε p_m = 1

για κάθε

.
Στην περίπτωση όπου q > p

τα πράγματα είναι εύκολα παίρνοντας το όριο όταν το

τείνει στο άπειρο. Αυτό δίνει B=0

, άρα

και άρα πάλι p_m = 1

για κάθε

.

Στην περίπτωση όπου q < p

η οποία είναι και η πιο ενδιαφέρουσα δεν φαίνεται να μπορούμε να πούμε κάτι περισσότερο για την τιμή του

πέραν του ότι $A \geqslant 0$ το οποίο προκύπτει αν πάρουμε το όριο στο άπειρο.

Εδώ βοηθάει η θεωρία των αλυσίδων Markov η οποία μας δίνει ότι τα p_m

είναι η μικρότερη μη αρνητική λύση του συστήματος εξισώσεων που γράψαμε πιο πάνω.

Με αυτό το επιπλέον δεδομένο παίρνουμε p_m = (q/p)^m

για κάθε

.

Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)

Μέλη σε σύνδεση