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

dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1365
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

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

#1

Μη αναγνωσμένη δημοσίευση από dement » Δευ Φεβ 27, 2017 4:02 pm

Η φανταστική πόλη Sapi εκτείνεται σε ολόκληρο το καρτεσιανό επίπεδο. Οι δρόμοι της αντιστοιχούν στις ευθείες x = n και y = n, όπου n τυχαίος ακέραιος. Έτσι, οι διασταυρώσεις της είναι ακριβώς τα σημεία με ακέραιες συντεταγμένες. Επιπλέον, η πόλη διασχίζεται από τον ποταμό Orna ο οποίος αντιστοιχεί στην ευθεία \displaystyle y = x + \frac{1}{2} (βλ. σχήμα).
sapi.png
sapi.png (19.02 KiB) Προβλήθηκε 1216 φορές
Η Αλέσσια ξεκινάει από τη διασταύρωση (0,0) και κινείται πάντα είτε βόρεια είτε ανατολικά.

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

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


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.

Λέξεις Κλειδιά:
Άβαταρ μέλους
Al.Koutsouridis
Δημοσιεύσεις: 698
Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
Τοποθεσία: Αθήνα

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

#2

Μη αναγνωσμένη δημοσίευση από Al.Koutsouridis » Παρ Μαρ 10, 2017 10:38 pm

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

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

Οποιαδήποτε διαδρομή από το σημείο (0,0) στο (a,b) αποτελείται από a κινήσεις ανατολικά και b κινήσεις βόρεια. Οπότε το πλήθος τέτοιων διαδρομών ισούται με τον αριθμό των τρόπων να διαλέξουμε από a+b αριθμό κινήσεων, b κινήσεις βόρεια. Δηλαδή \binom{a+b}{b} = \binom{a+b}{a} τρόποι.

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

Λήμμα (αντανάκλασης). Το πλήθος των διαδρομών από το σημείο (0,0) στο (a,b) (a\geq b) που υπερβαίνουν την ευθεία y=x ισούται με το πλήθος των διαδρομών από το σημείο (0,0) στο (b-1,a+1).

Απόδειξη. Θα δημιουργήσουμε μια 1-1 αντιστοιχία μεταξύ των δυο παραπάνω συνόλων διαδρομών. Οποιαδήποτε διαδρομή που υπερβαίνει την ευθεία y=x θα τέμνει και την ευθεία y=x+1. Εξετάζουμε το πρώτο σημείο τομής με αυτή την ευθεία και πάιρνουμε την συμμετρική διαδρομή από αυτό το σημείο και ύστερα μέχρι το (a,b) ως προς την ευθεία y=x+1. Αυτή η συμμετρική διαδρομή καταλλήγει στο σημείο (b-1,a+1). Ομοίως και η αντίστροφή αντιστοιχία.
sns_2014_15_3.png
sns_2014_15_3.png (51.34 KiB) Προβλήθηκε 1111 φορές
Στο πρόβλημά μας, από την στιγμή που το ποτάμι βρίσκεται πάνω στην ευθεία 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
Διευθύνον Μέλος
Δημοσιεύσεις: 1365
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

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

#3

Μη αναγνωσμένη δημοσίευση από dement » Παρ Μαρ 10, 2017 11:09 pm

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


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
mikemoke
Δημοσιεύσεις: 187
Εγγραφή: Σάβ Δεκ 17, 2016 12:58 am

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

#4

Μη αναγνωσμένη δημοσίευση από mikemoke » Παρ Μαρ 10, 2017 11:56 pm

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

sapi.png

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

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

2. Έστω ότι η Αλέσσια, σε κάθε διασταύρωση, αποφασίζει να κινηθεί ανατολικά με πιθανότητα p και βόρεια με πιθανότητα q = 1 - p. Να αποδειχθεί ότι η πιθανότητα να διασχίσει τουλάχιστον μία φορά το ποτάμι σε μία διαδρομή με n διασταυρώσεις είναι μικρότερη ή ίση με \displaystyle \frac{q}{p}.
Το δενδροδιάγραμμα για μπλε σημεία
Για τα κόκκινα οι διακλαδώσεις προκύπτουν αν αφαιρέσουμε απο τις μπλε( που βρίσκονται στην ίδια κατακόρυφη) τον αριθμό των διακλαδώσεων του προηγούμενο βήματος (των μπλέ)
για τα κιτρινα 2 φορέσ αυτόν τον αριθμό ,για τα πράσινα 3 και πάει λέγοντας
Συνημμένα
Inkedsapi (2)_LI.jpg
Inkedsapi (2)_LI.jpg (617.4 KiB) Προβλήθηκε 1061 φορές
λαλαλα.png
λαλαλα.png (24.32 KiB) Προβλήθηκε 1075 φορές


Άβαταρ μέλους
Al.Koutsouridis
Δημοσιεύσεις: 698
Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
Τοποθεσία: Αθήνα

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

#5

Μη αναγνωσμένη δημοσίευση από Al.Koutsouridis » Κυρ Μαρ 12, 2017 1:12 pm

Διαγραφή ανάρτησης λόγω λάθους συλλογισμού.
τελευταία επεξεργασία από Al.Koutsouridis σε Κυρ Μαρ 12, 2017 3:16 pm, έχει επεξεργασθεί 1 φορά συνολικά.


dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1365
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

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

#6

Μη αναγνωσμένη δημοσίευση από dement » Κυρ Μαρ 12, 2017 2:16 pm

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

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


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Άβαταρ μέλους
Al.Koutsouridis
Δημοσιεύσεις: 698
Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
Τοποθεσία: Αθήνα

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

#7

Μη αναγνωσμένη δημοσίευση από Al.Koutsouridis » Κυρ Μαρ 12, 2017 3:15 pm

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

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

Μια δεύτερη σκέψη που χρονικά ήταν η πρώτη που έκανα είναι να θεωρήσουμε το συμπληρωματικό ενδεχόμενο A{'} και να δείξουμε ότι P(A{'} ) \geq 1-\dfrac{q}{p} (1).

Το A{'} είναι το ενδεχόμενο σε n κινήσεις να μην διέσχισε το ποτάμι ούτε μια φορά. Παρατηρούμε ότι για τα σημεία πάνω από την 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} γιατί κινούμαστε n κινήσεις ανατολικά και 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)

Αν F η αθροιστική συνάρτηση κατανομής της διωνυμικής κατανομής τότε η (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)

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

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


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7790
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#8

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Μαρ 12, 2017 5:01 pm

Έστω r η ζητούμενη πιθανότητα. Τότε r = q + pr', όπου r' είναι η πιθανότητα να διασχίσουμε το ποτάμι ξεκινώντας από το (1,0) και κάνοντας n-1 κινήσεις. Για να το επιτύχουμε όμως αυτό πρέπει πρώτα να διασχίσουμε το υποθετικό ποτάμι με εξίσωση y=x-1/2, και μετά ο πραγματικό ποτάμι με εξίσωση y=x+1/2. Από συμμετρία, η πιθανότητα να διασχίσουμε το υποθετικό ποτάμι είναι το πολύ r. (Στην πραγματικότητα είναι μικρότερη του r αφού έχουμε μόνο n-1 κινήσεις.) Μόλις διασχίσουμε το υποθετικό ποτάμι, θα βρισκόμαστε σε ένα σημείο της μορφής (m,m). Τότε πρέπει να διασχίσουμε το κανονικό ποτάμι σε n-2m κινήσεις και η πιθανότητα να το πετύχουμε αυτό είναι πάλι το πολύ r. Τα δύο τελευταία ενδεχόμενα είναι ανεξάρτητα οπότε r' \leqslant r^2. Άρα r \leqslant q + pr^2 ή ισοδύναμα (1-r)(q-pr) \geqslant 0. Όμως r \neq 1 αφού με πιθανότητα p^n κινούμαστε πάντα ανατολικά. Άρα πρέπει r \leqslant q/p.

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


dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1365
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

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

#9

Μη αναγνωσμένη δημοσίευση από dement » Κυρ Μαρ 12, 2017 5:25 pm

Demetres έγραψε: Μπορεί να δειχθεί το εξής: Η πιθανότητα να διασχίσουμε το ποτάμι αν κάνουμε άπειρα βήματα με τον ίδιο τρόπο, ισούται με 1 αν q \geqslant p και ισούται με q/p αν q < p.
Έτσι το έκανα εγώ. Η πιθανότητα να διασχίσουμε για πρώτη φορά το ποτάμι από το σημείο (m,m) είναι q \cdot C_m \cdot (pq)^m, όπου C_m ο αντίστοιχος αριθμός Catalan. Αθροίζοντας για όλα τα m παίρνουμε τη γεννήτρια συνάρτηση της ακολουθίας Catalan για x=pq και το άπειρο άθροισμα ισούται με

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


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7790
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#10

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Μαρ 12, 2017 6:00 pm

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

Ισοδύναμα, ξεκινάμε από τον ακέραιο 1 και σε κάθε βήμα είτε προσθέτουμε 1 με πιθανότητα p είτε αφαιρούμε 1 με πιθανότητα q. Μας ενδιαφέρει αν θα καταφέρουμε σε n βήματα να φτάσουμε στο 0.

Θα γράψω p_m για την πιθανότητα, αν ξεκινήσω από τον φυσικό m, να καταλήξω στο 0 αν ακολουθώ την πιο πάνω διαδικασία επ' άπειρον.

Ασφαλώς είναι p_0 = 1. Επίσης είναι p_m = pp_{m+1} + qp_{m-1}. Η χαρακτηριστική εξίσωση είναι η px^2-x+q = 0 που έχει ρίζες τα x=1 και x = q/p.

Άρα παίρνουμε p_m = A + B(q/p)^m για κάποιες σταθερές A,B. Η περίπτωση m=0 δίνει A+B = 1. Καταλήγουμε λοιπόν στην p_m = (q/p)^m + A(1-(q/p)^m).

Στην περίπτωση όπου q = p τα πράγματα είναι απλά αφού έχουμε p_m = 1 για κάθε m.
Στην περίπτωση όπου q > p τα πράγματα είναι εύκολα παίρνοντας το όριο όταν το m τείνει στο άπειρο. Αυτό δίνει B=0, άρα A=1 και άρα πάλι p_m = 1 για κάθε m.

Στην περίπτωση όπου q < p η οποία είναι και η πιο ενδιαφέρουσα δεν φαίνεται να μπορούμε να πούμε κάτι περισσότερο για την τιμή του A πέραν του ότι A \geqslant 0 το οποίο προκύπτει αν πάρουμε το όριο στο άπειρο.

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

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


Απάντηση

Επιστροφή σε “Διάφορα άλλα θέματα εξετάσεων”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 3 επισκέπτες