Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Η φανταστική πόλη Sapi εκτείνεται σε ολόκληρο το καρτεσιανό επίπεδο. Οι δρόμοι της αντιστοιχούν στις ευθείες και , όπου τυχαίος ακέραιος. Έτσι, οι διασταυρώσεις της είναι ακριβώς τα σημεία με ακέραιες συντεταγμένες. Επιπλέον, η πόλη διασχίζεται από τον ποταμό Orna ο οποίος αντιστοιχεί στην ευθεία (βλ. σχήμα).
Η Αλέσσια ξεκινάει από τη διασταύρωση και κινείται πάντα είτε βόρεια είτε ανατολικά.
1. Να βρεθεί ο αριθμός των δυνατών διαδρομών από τις οποίες μπορεί να φτάσει στο σημείο χωρίς να διασχίσει το ποτάμι.
2. Έστω ότι η Αλέσσια, σε κάθε διασταύρωση, αποφασίζει να κινηθεί ανατολικά με πιθανότητα και βόρεια με πιθανότητα . Να αποδειχθεί ότι η πιθανότητα να διασχίσει τουλάχιστον μία φορά το ποτάμι σε μία διαδρομή με διασταυρώσεις είναι μικρότερη ή ίση με .
Η Αλέσσια ξεκινάει από τη διασταύρωση και κινείται πάντα είτε βόρεια είτε ανατολικά.
1. Να βρεθεί ο αριθμός των δυνατών διαδρομών από τις οποίες μπορεί να φτάσει στο σημείο χωρίς να διασχίσει το ποτάμι.
2. Έστω ότι η Αλέσσια, σε κάθε διασταύρωση, αποφασίζει να κινηθεί ανατολικά με πιθανότητα και βόρεια με πιθανότητα . Να αποδειχθεί ότι η πιθανότητα να διασχίσει τουλάχιστον μία φορά το ποτάμι σε μία διαδρομή με διασταυρώσεις είναι μικρότερη ή ίση με .
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Λέξεις Κλειδιά:
- Al.Koutsouridis
- Δημοσιεύσεις: 1797
- Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
- Τοποθεσία: Αθήνα
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Το πρώτο ερώτημα μπορεί να λυθεί με το λεγόμενο λήμμα της αντανάκλασης.
Αρχικά βρίσκουμε το σύνολο των διαδρομών από το σημείο στο ανεξαρτήτως αν περνάμε το ποτάμι ή όχι.
Οποιαδήποτε διαδρομή από το σημείο στο αποτελείται από κινήσεις ανατολικά και κινήσεις βόρεια. Οπότε το πλήθος τέτοιων διαδρομών ισούται με τον αριθμό των τρόπων να διαλέξουμε από αριθμό κινήσεων, κινήσεις βόρεια. Δηλαδή τρόποι.
Από αυτές θα πρέπει να αφαιρέσουμε όσες διασχίζουν το ποτάμι. Για να το βρούμε χρησιμοποιούμε το ακόλουθο λήμμα.
Λήμμα (αντανάκλασης). Το πλήθος των διαδρομών από το σημείο στο () που υπερβαίνουν την ευθεία ισούται με το πλήθος των διαδρομών από το σημείο στο .
Απόδειξη. Θα δημιουργήσουμε μια 1-1 αντιστοιχία μεταξύ των δυο παραπάνω συνόλων διαδρομών. Οποιαδήποτε διαδρομή που υπερβαίνει την ευθεία θα τέμνει και την ευθεία . Εξετάζουμε το πρώτο σημείο τομής με αυτή την ευθεία και πάιρνουμε την συμμετρική διαδρομή από αυτό το σημείο και ύστερα μέχρι το ως προς την ευθεία . Αυτή η συμμετρική διαδρομή καταλλήγει στο σημείο . Ομοίως και η αντίστροφή αντιστοιχία.
Στο πρόβλημά μας, από την στιγμή που το ποτάμι βρίσκεται πάνω στην ευθεία σημαίνει ότι το διασχίζουμε όταν υπερβαίνουμε την ευθεία . Άρα μπορούμε να εφαρμόσουμε το παραπάνω λήμμα και οι ζητούμενοι τρόποι είναι
Να σημειώσουμε ότι για ο παραπάνω τύπος δίνει τους αριθμούς Catalan.
Αρχικά βρίσκουμε το σύνολο των διαδρομών από το σημείο στο ανεξαρτήτως αν περνάμε το ποτάμι ή όχι.
Οποιαδήποτε διαδρομή από το σημείο στο αποτελείται από κινήσεις ανατολικά και κινήσεις βόρεια. Οπότε το πλήθος τέτοιων διαδρομών ισούται με τον αριθμό των τρόπων να διαλέξουμε από αριθμό κινήσεων, κινήσεις βόρεια. Δηλαδή τρόποι.
Από αυτές θα πρέπει να αφαιρέσουμε όσες διασχίζουν το ποτάμι. Για να το βρούμε χρησιμοποιούμε το ακόλουθο λήμμα.
Λήμμα (αντανάκλασης). Το πλήθος των διαδρομών από το σημείο στο () που υπερβαίνουν την ευθεία ισούται με το πλήθος των διαδρομών από το σημείο στο .
Απόδειξη. Θα δημιουργήσουμε μια 1-1 αντιστοιχία μεταξύ των δυο παραπάνω συνόλων διαδρομών. Οποιαδήποτε διαδρομή που υπερβαίνει την ευθεία θα τέμνει και την ευθεία . Εξετάζουμε το πρώτο σημείο τομής με αυτή την ευθεία και πάιρνουμε την συμμετρική διαδρομή από αυτό το σημείο και ύστερα μέχρι το ως προς την ευθεία . Αυτή η συμμετρική διαδρομή καταλλήγει στο σημείο . Ομοίως και η αντίστροφή αντιστοιχία.
Στο πρόβλημά μας, από την στιγμή που το ποτάμι βρίσκεται πάνω στην ευθεία σημαίνει ότι το διασχίζουμε όταν υπερβαίνουμε την ευθεία . Άρα μπορούμε να εφαρμόσουμε το παραπάνω λήμμα και οι ζητούμενοι τρόποι είναι
Να σημειώσουμε ότι για ο παραπάνω τύπος δίνει τους αριθμούς Catalan.
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Πολύ ωραία. Απομένει το δεύτερο ερώτημα.
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Το δενδροδιάγραμμα για μπλε σημείαdement έγραψε:Η φανταστική πόλη Sapi εκτείνεται σε ολόκληρο το καρτεσιανό επίπεδο. Οι δρόμοι της αντιστοιχούν στις ευθείες και , όπου τυχαίος ακέραιος. Έτσι, οι διασταυρώσεις της είναι ακριβώς τα σημεία με ακέραιες συντεταγμένες. Επιπλέον, η πόλη διασχίζεται από τον ποταμό Orna ο οποίος αντιστοιχεί στην ευθεία (βλ. σχήμα).
sapi.png
Η Αλέσσια ξεκινάει από τη διασταύρωση και κινείται πάντα είτε βόρεια είτε ανατολικά.
1. Να βρεθεί ο αριθμός των δυνατών διαδρομών από τις οποίες μπορεί να φτάσει στο σημείο χωρίς να διασχίσει το ποτάμι.
2. Έστω ότι η Αλέσσια, σε κάθε διασταύρωση, αποφασίζει να κινηθεί ανατολικά με πιθανότητα και βόρεια με πιθανότητα . Να αποδειχθεί ότι η πιθανότητα να διασχίσει τουλάχιστον μία φορά το ποτάμι σε μία διαδρομή με διασταυρώσεις είναι μικρότερη ή ίση με .
Για τα κόκκινα οι διακλαδώσεις προκύπτουν αν αφαιρέσουμε απο τις μπλε( που βρίσκονται στην ίδια κατακόρυφη) τον αριθμό των διακλαδώσεων του προηγούμενο βήματος (των μπλέ)
για τα κιτρινα 2 φορέσ αυτόν τον αριθμό ,για τα πράσινα 3 και πάει λέγοντας
- Συνημμένα
-
- Inkedsapi (2)_LI.jpg (617.4 KiB) Προβλήθηκε 2109 φορές
-
- λαλαλα.png (24.32 KiB) Προβλήθηκε 2123 φορές
- Al.Koutsouridis
- Δημοσιεύσεις: 1797
- Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
- Τοποθεσία: Αθήνα
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Διαγραφή ανάρτησης λόγω λάθους συλλογισμού.
τελευταία επεξεργασία από Al.Koutsouridis σε Κυρ Μαρ 12, 2017 3:16 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Αλέξανδρε (;), έχω την εντύπωση ότι το λήμμα της αντανάκλασης τώρα δεν προσφέρεται τόσο για την περίπτωσή μας. Δύο μονοπάτια που αντιστοιχίζονται από το λήμμα ταυτίζονται μέχρι το ποτάμι και στη συνέχεια ο βορράς γίνεται ανατολή και τούμπαλιν, μέχρι το επόμενο πέρασμα και πάει λέγοντας. Η ασυμμετρία που εισάγεται από τις διαφορετικές τιμές των χαλάει τη δουλειά...
Α, και η κοπέλα λέγεται Αλέσσια.
Α, και η κοπέλα λέγεται Αλέσσια.
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
- Al.Koutsouridis
- Δημοσιεύσεις: 1797
- Εγγραφή: Πέμ Ιαν 30, 2014 11:58 pm
- Τοποθεσία: Αθήνα
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Αλέσσια ωραίο όνομα, δε θα έπρεπε να κάνω λάθος, στο πρόβλημα συγχωρείται .dement έγραψε:Αλέξανδρε (;), έχω την εντύπωση ότι το λήμμα της αντανάκλασης τώρα δεν προσφέρεται τόσο για την περίπτωσή μας. Δύο μονοπάτια που αντιστοιχίζονται από το λήμμα ταυτίζονται μέχρι το ποτάμι και στη συνέχεια ο βορράς γίνεται ανατολή και τούμπαλιν, μέχρι το επόμενο πέρασμα και πάει λέγοντας. Η ασυμμετρία που εισάγεται από τις διαφορετικές τιμές των χαλάει τη δουλειά...
Α, και η κοπέλα λέγεται Αλέσσια.
Μια δεύτερη σκέψη που χρονικά ήταν η πρώτη που έκανα είναι να θεωρήσουμε το συμπληρωματικό ενδεχόμενο και να δείξουμε ότι (1).
Το είναι το ενδεχόμενο σε κινήσεις να μην διέσχισε το ποτάμι ούτε μια φορά. Παρατηρούμε ότι για τα σημεία πάνω από την θα πρέπει να αναγκαστηκά να το διασχίσει οπότε το ενδεχόμενο αυτό θα αποτελείτε από τις διαδρομές στα σημεία της ευθείας που βρίσκονται κάτω από την ευθεία και δεν διασχίζουν το ποτάμι.
Από το πρώτο ερώτημα για κάθε τέτοιο σημείο οι δυνατοί τρόποι για το προσεγγίσουμε είναι
(2) . Τα σημεία προς εξέταση είναι τα
όπου .
Εφαρμόζοντας την (2) για τα παραπάνω σημεία αντίστοιχα βρίσκουμε
τρόποι με πιθανότητα γιατί κινούμαστε κινήσεις ανατολικά και 0 κινήσεις βόρεια. Ομοίως για τα άλλα σημεία
....
Πολλαπλασιάζοντας και διαιρώντας τους όρους με το (-) με και αθροίζοντας τις παραπάνω πιθανότητες βρίσκουμε
(3)
Αν η αθροιστική συνάρτηση κατανομής της διωνυμικής κατανομής τότε η (1) με την βοήθεια της (3) μπορεί να γραφεί
εδώ προς το παρόν και πάλι έχω κολλήσει...πάλι κάποιες σκέψεις είναι είτε επαγωγικά, είτε αξιοποιώντας ίσως την μονοτόνία της ...
Ελπίζω να είναι σωστά τώρα τουλάχιστον.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Έστω η ζητούμενη πιθανότητα. Τότε , όπου είναι η πιθανότητα να διασχίσουμε το ποτάμι ξεκινώντας από το και κάνοντας κινήσεις. Για να το επιτύχουμε όμως αυτό πρέπει πρώτα να διασχίσουμε το υποθετικό ποτάμι με εξίσωση , και μετά ο πραγματικό ποτάμι με εξίσωση . Από συμμετρία, η πιθανότητα να διασχίσουμε το υποθετικό ποτάμι είναι το πολύ . (Στην πραγματικότητα είναι μικρότερη του αφού έχουμε μόνο κινήσεις.) Μόλις διασχίσουμε το υποθετικό ποτάμι, θα βρισκόμαστε σε ένα σημείο της μορφής . Τότε πρέπει να διασχίσουμε το κανονικό ποτάμι σε κινήσεις και η πιθανότητα να το πετύχουμε αυτό είναι πάλι το πολύ . Τα δύο τελευταία ενδεχόμενα είναι ανεξάρτητα οπότε . Άρα ή ισοδύναμα . Όμως αφού με πιθανότητα κινούμαστε πάντα ανατολικά. Άρα πρέπει .
Μπορεί να δειχθεί το εξής: Η πιθανότητα να διασχίσουμε το ποτάμι αν κάνουμε άπειρα βήματα με τον ίδιο τρόπο, ισούται με αν και ισούται με αν .
Μπορεί να δειχθεί το εξής: Η πιθανότητα να διασχίσουμε το ποτάμι αν κάνουμε άπειρα βήματα με τον ίδιο τρόπο, ισούται με αν και ισούται με αν .
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Έτσι το έκανα εγώ. Η πιθανότητα να διασχίσουμε για πρώτη φορά το ποτάμι από το σημείο είναι , όπου ο αντίστοιχος αριθμός Catalan. Αθροίζοντας για όλα τα παίρνουμε τη γεννήτρια συνάρτηση της ακολουθίας Catalan για και το άπειρο άθροισμα ισούται μεDemetres έγραψε: Μπορεί να δειχθεί το εξής: Η πιθανότητα να διασχίσουμε το ποτάμι αν κάνουμε άπειρα βήματα με τον ίδιο τρόπο, ισούται με αν και ισούται με αν .
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (3)
Για ποικιλία λοιπόν ας βάλω ακόμη μία απόδειξη:
Ισοδύναμα, ξεκινάμε από τον ακέραιο και σε κάθε βήμα είτε προσθέτουμε με πιθανότητα είτε αφαιρούμε με πιθανότητα . Μας ενδιαφέρει αν θα καταφέρουμε σε βήματα να φτάσουμε στο .
Θα γράψω για την πιθανότητα, αν ξεκινήσω από τον φυσικό , να καταλήξω στο αν ακολουθώ την πιο πάνω διαδικασία επ' άπειρον.
Ασφαλώς είναι . Επίσης είναι . Η χαρακτηριστική εξίσωση είναι η που έχει ρίζες τα και .
Άρα παίρνουμε για κάποιες σταθερές . Η περίπτωση δίνει . Καταλήγουμε λοιπόν στην .
Στην περίπτωση όπου τα πράγματα είναι απλά αφού έχουμε για κάθε .
Στην περίπτωση όπου τα πράγματα είναι εύκολα παίρνοντας το όριο όταν το τείνει στο άπειρο. Αυτό δίνει , άρα και άρα πάλι για κάθε .
Στην περίπτωση όπου η οποία είναι και η πιο ενδιαφέρουσα δεν φαίνεται να μπορούμε να πούμε κάτι περισσότερο για την τιμή του πέραν του ότι το οποίο προκύπτει αν πάρουμε το όριο στο άπειρο.
Εδώ βοηθάει η θεωρία των αλυσίδων Markov η οποία μας δίνει ότι τα είναι η μικρότερη μη αρνητική λύση του συστήματος εξισώσεων που γράψαμε πιο πάνω.
Με αυτό το επιπλέον δεδομένο παίρνουμε για κάθε .
Ισοδύναμα, ξεκινάμε από τον ακέραιο και σε κάθε βήμα είτε προσθέτουμε με πιθανότητα είτε αφαιρούμε με πιθανότητα . Μας ενδιαφέρει αν θα καταφέρουμε σε βήματα να φτάσουμε στο .
Θα γράψω για την πιθανότητα, αν ξεκινήσω από τον φυσικό , να καταλήξω στο αν ακολουθώ την πιο πάνω διαδικασία επ' άπειρον.
Ασφαλώς είναι . Επίσης είναι . Η χαρακτηριστική εξίσωση είναι η που έχει ρίζες τα και .
Άρα παίρνουμε για κάποιες σταθερές . Η περίπτωση δίνει . Καταλήγουμε λοιπόν στην .
Στην περίπτωση όπου τα πράγματα είναι απλά αφού έχουμε για κάθε .
Στην περίπτωση όπου τα πράγματα είναι εύκολα παίρνοντας το όριο όταν το τείνει στο άπειρο. Αυτό δίνει , άρα και άρα πάλι για κάθε .
Στην περίπτωση όπου η οποία είναι και η πιο ενδιαφέρουσα δεν φαίνεται να μπορούμε να πούμε κάτι περισσότερο για την τιμή του πέραν του ότι το οποίο προκύπτει αν πάρουμε το όριο στο άπειρο.
Εδώ βοηθάει η θεωρία των αλυσίδων Markov η οποία μας δίνει ότι τα είναι η μικρότερη μη αρνητική λύση του συστήματος εξισώσεων που γράψαμε πιο πάνω.
Με αυτό το επιπλέον δεδομένο παίρνουμε για κάθε .
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 3 επισκέπτες