IMC 2018/2/3
Συντονιστής: Demetres
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
IMC 2018/2/3
Έστω .
Ένας βάτραχος κινείται στα σημεία του με πηδήματα μήκους . Για κάθε θετικό ακέραιο να βρεθεί με πόσους διαφορετικούς τρόπους μπορεί ξεκινώντας από το να φτάσει στο σε ακριβώς πηδήματα.
Ένας βάτραχος κινείται στα σημεία του με πηδήματα μήκους . Για κάθε θετικό ακέραιο να βρεθεί με πόσους διαφορετικούς τρόπους μπορεί ξεκινώντας από το να φτάσει στο σε ακριβώς πηδήματα.
Λέξεις Κλειδιά:
Re: IMC 2018/2/3
Οι κινήσεις του βατράχου κατά μήκος των αξόνων θα ακολουθήσουν υποχρεωτικά το μοτίβο
Ανάμεσα σε αυτές τις κινήσεις μπαίνουν οι κινήσεις κατά μήκος του άξονα . Αν δεν υπήρχαν περιορισμοί για το , κατά συνέπεια, θα είχαμε επιλογές.
Σε κάθε πορεία που ικανοποιεί τους περιορισμούς των αλλά όχι απαραίτητα του , αντιστοιχίζουμε έναν αριθμό ("βαθμό απαγόρευσης") ο οποίος αντιστοιχεί στον αριθμό των κινήσεων που καταλήγουν σε απαγορευμένη θέση (κάθε τέτοια κίνηση μετράει διπλή αν καταλήγει σε θέση με , οπότε προφανώς και , και μονή αν καταλήγει μόνο σε θέση με ). Μια τέτοια πορεία λέγεται απαγορευμένη. Προφανώς και μας ενδιαφέρουν οι απαγορευμένες πορείες.
Στη συνέχεια χρησιμοποιούμε ένα επιχείρημα παρόμοιο με αυτό που διαιρεί τον διωνυμικό συντελεστή με για να παραγάγει τον αριθμό Catalan ως τον αριθμό των λέξεων Dyck. Κατασκευάζουμε bijection μεταξύ των απαγορευμένων και των απαγορευμένων διαδρομών ως εξής: στην απαγορευμένη διαδρομή εντοπίζουμε την πρώτη κίνηση που πηγαίνει σε θέση με και εναλλάσσουμε το σύνολο των κινήσεων μετά από αυτήν με εκείνο πριν από αυτήν (αν χρειαστεί, μετονομάζουμε τις και κινήσεις ώστε να εναλλάσσονται). Το αποτέλεσμα είναι μία απαγορευμένη διαδρομή. Για την αντίστροφη απεικόνιση, εντοπίζουμε την τελευταία κίνηση από θέση με και, πάλι, εναλλάσσουμε το σύνολο των κινήσεων μετά από αυτήν με εκείνο πριν από αυτήν. Παραπέμπω στο https://en.wikipedia.org/wiki/Catalan_n ... hird_proof για περισσότερες πληροφορίες.
Έτσι, όλοι οι "βαθμοί απαγόρευσης" των διαδρομών είναι ισοπληθείς και οι απαγορευμένες διαδρομές είναι το πλήθος.
Ανάμεσα σε αυτές τις κινήσεις μπαίνουν οι κινήσεις κατά μήκος του άξονα . Αν δεν υπήρχαν περιορισμοί για το , κατά συνέπεια, θα είχαμε επιλογές.
Σε κάθε πορεία που ικανοποιεί τους περιορισμούς των αλλά όχι απαραίτητα του , αντιστοιχίζουμε έναν αριθμό ("βαθμό απαγόρευσης") ο οποίος αντιστοιχεί στον αριθμό των κινήσεων που καταλήγουν σε απαγορευμένη θέση (κάθε τέτοια κίνηση μετράει διπλή αν καταλήγει σε θέση με , οπότε προφανώς και , και μονή αν καταλήγει μόνο σε θέση με ). Μια τέτοια πορεία λέγεται απαγορευμένη. Προφανώς και μας ενδιαφέρουν οι απαγορευμένες πορείες.
Στη συνέχεια χρησιμοποιούμε ένα επιχείρημα παρόμοιο με αυτό που διαιρεί τον διωνυμικό συντελεστή με για να παραγάγει τον αριθμό Catalan ως τον αριθμό των λέξεων Dyck. Κατασκευάζουμε bijection μεταξύ των απαγορευμένων και των απαγορευμένων διαδρομών ως εξής: στην απαγορευμένη διαδρομή εντοπίζουμε την πρώτη κίνηση που πηγαίνει σε θέση με και εναλλάσσουμε το σύνολο των κινήσεων μετά από αυτήν με εκείνο πριν από αυτήν (αν χρειαστεί, μετονομάζουμε τις και κινήσεις ώστε να εναλλάσσονται). Το αποτέλεσμα είναι μία απαγορευμένη διαδρομή. Για την αντίστροφη απεικόνιση, εντοπίζουμε την τελευταία κίνηση από θέση με και, πάλι, εναλλάσσουμε το σύνολο των κινήσεων μετά από αυτήν με εκείνο πριν από αυτήν. Παραπέμπω στο https://en.wikipedia.org/wiki/Catalan_n ... hird_proof για περισσότερες πληροφορίες.
Έτσι, όλοι οι "βαθμοί απαγόρευσης" των διαδρομών είναι ισοπληθείς και οι απαγορευμένες διαδρομές είναι το πλήθος.
Δημήτρης Σκουτέρης
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: IMC 2018/2/3
Διαφορετικά:
Ας γράψουμε για το πλήθος των λέξεων γραμμάτων στο αλφάβητο όπου ακριβώς από τα γράμματα είναι και σε κάθε αρχικό κομμάτι της λέξης υπάρχουν τουλάχιστον διπλάσια από .
Το ζητούμενο ισούται με αφού σε κάθε κίνηση του βατράχου μπορούμε να αντιστοιχίσουμε το γράμμα αν έχουμε αύξηση των ή και το γράμμα αν έχουμε αύξηση του . Η αντιστοιχία είναι ένα προς ένα επειδή οι αυξήσεις των εναλλάσσονται.
Ισχυρίζομαι ότι αν . (Και σε διαφορετική περίπτωση.) Αυτό θα δώσει
Θα το αποδείξουμε με επαγωγή στο . Η περίπτωση είναι προφανής. Έστω λοιπόν ότι . Προφανώς αν ή αν . Ας υποθέσουμε λοιπόν ότι .
Υπάρχουν τέτοιες λέξεις με τελευταίο γράμμα το και τέτοιες λέξεις με τελευταίο γράμμα το .
Άρα:
και το επαγωγικό βήμα (σχεδόν) ολοκληρώθηκε.
Πρέπει όμως να ελέγξουμε και τις περιπτώσεις όπου τα και πιθανώς να ισούνται με . Αυτό συμβαίνει μόνο όταν ή . Στην πρώτη περίπτωση έχουμε και στην δεύτερη .
Στην πρώτη περίπτωση είναι . Στην δεύτερη είναι
Και στις δύο περιπτώσεις το επαγωγικό βήμα ολοκληρώνεται.
Ας γράψουμε για το πλήθος των λέξεων γραμμάτων στο αλφάβητο όπου ακριβώς από τα γράμματα είναι και σε κάθε αρχικό κομμάτι της λέξης υπάρχουν τουλάχιστον διπλάσια από .
Το ζητούμενο ισούται με αφού σε κάθε κίνηση του βατράχου μπορούμε να αντιστοιχίσουμε το γράμμα αν έχουμε αύξηση των ή και το γράμμα αν έχουμε αύξηση του . Η αντιστοιχία είναι ένα προς ένα επειδή οι αυξήσεις των εναλλάσσονται.
Ισχυρίζομαι ότι αν . (Και σε διαφορετική περίπτωση.) Αυτό θα δώσει
Θα το αποδείξουμε με επαγωγή στο . Η περίπτωση είναι προφανής. Έστω λοιπόν ότι . Προφανώς αν ή αν . Ας υποθέσουμε λοιπόν ότι .
Υπάρχουν τέτοιες λέξεις με τελευταίο γράμμα το και τέτοιες λέξεις με τελευταίο γράμμα το .
Άρα:
και το επαγωγικό βήμα (σχεδόν) ολοκληρώθηκε.
Πρέπει όμως να ελέγξουμε και τις περιπτώσεις όπου τα και πιθανώς να ισούνται με . Αυτό συμβαίνει μόνο όταν ή . Στην πρώτη περίπτωση έχουμε και στην δεύτερη .
Στην πρώτη περίπτωση είναι . Στην δεύτερη είναι
Και στις δύο περιπτώσεις το επαγωγικό βήμα ολοκληρώνεται.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης