IMC 2018/2/3

Συντονιστής: Demetres

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

IMC 2018/2/3

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 26, 2018 11:44 am

Έστω \Omega =\{ (x,y,z)\in \mathbb{Z}^3:y+1\geqslant x\geqslant y\geqslant z\geqslant 0\}.

Ένας βάτραχος κινείται στα σημεία του \Omega με πηδήματα μήκους 1. Για κάθε θετικό ακέραιο n να βρεθεί με πόσους διαφορετικούς τρόπους μπορεί ξεκινώντας από το (0,0,0) να φτάσει στο (n,n,n) σε ακριβώς 3n πηδήματα.



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

Re: IMC 2018/2/3

#2

Μη αναγνωσμένη δημοσίευση από dement » Τρί Αύγ 07, 2018 12:42 pm

Οι κινήσεις του βατράχου κατά μήκος των αξόνων x,y θα ακολουθήσουν υποχρεωτικά το μοτίβο (x,y) = (0,0), (1,0), (1,1), (2,1), (2,2), ..., (n,n)
Ανάμεσα σε αυτές τις 2n κινήσεις μπαίνουν οι n κινήσεις κατά μήκος του άξονα z. Αν δεν υπήρχαν περιορισμοί για το z, κατά συνέπεια, θα είχαμε \displaystyle \binom{3n}{n} επιλογές.

Σε κάθε πορεία που ικανοποιεί τους περιορισμούς των x, y αλλά όχι απαραίτητα του z, αντιστοιχίζουμε έναν αριθμό k ("βαθμό απαγόρευσης") ο οποίος αντιστοιχεί στον αριθμό των z-κινήσεων που καταλήγουν σε απαγορευμένη θέση (κάθε τέτοια z-κίνηση μετράει διπλή αν καταλήγει σε θέση με x < z, οπότε προφανώς και y < z, και μονή αν καταλήγει μόνο σε θέση με y < z = x). Μια τέτοια πορεία λέγεται k-απαγορευμένη. Προφανώς 0 \leqslant k \leqslant 2n και μας ενδιαφέρουν οι 0-απαγορευμένες πορείες.

Στη συνέχεια χρησιμοποιούμε ένα επιχείρημα παρόμοιο με αυτό που διαιρεί τον διωνυμικό συντελεστή \displaystyle \binom{2n}{n} με n+1 για να παραγάγει τον αριθμό Catalan C_n ως τον αριθμό των λέξεων Dyck. Κατασκευάζουμε bijection μεταξύ των (k+1)-απαγορευμένων και των k-απαγορευμένων διαδρομών ως εξής: στην (k+1)-απαγορευμένη διαδρομή εντοπίζουμε την πρώτη y-κίνηση που πηγαίνει σε θέση με x=y=z και εναλλάσσουμε το σύνολο των κινήσεων μετά από αυτήν με εκείνο πριν από αυτήν (αν χρειαστεί, μετονομάζουμε τις x- και y-κινήσεις ώστε να εναλλάσσονται). Το αποτέλεσμα είναι μία k-απαγορευμένη διαδρομή. Για την αντίστροφη απεικόνιση, εντοπίζουμε την τελευταία x-κίνηση από θέση με x=y=z και, πάλι, εναλλάσσουμε το σύνολο των κινήσεων μετά από αυτήν με εκείνο πριν από αυτήν. Παραπέμπω στο https://en.wikipedia.org/wiki/Catalan_n ... hird_proof για περισσότερες πληροφορίες.

Έτσι, όλοι οι 2n+1 "βαθμοί απαγόρευσης" των \displaystyle \binom{3n}{n} διαδρομών είναι ισοπληθείς και οι 0-απαγορευμένες διαδρομές είναι \displaystyle \frac{1}{2n+1} \binom{3n}{n} το πλήθος.


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

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

Re: IMC 2018/2/3

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Αύγ 08, 2018 12:29 am

Διαφορετικά:

Ας γράψουμε R(m,k) για το πλήθος των λέξεων m γραμμάτων στο αλφάβητο A,B όπου ακριβώς k από τα γράμματα είναι A και σε κάθε αρχικό κομμάτι της λέξης υπάρχουν τουλάχιστον διπλάσια A από B.

Το ζητούμενο ισούται με R(3n,2n) αφού σε κάθε κίνηση του βατράχου μπορούμε να αντιστοιχίσουμε το γράμμα A αν έχουμε αύξηση των x ή y και το γράμμα B αν έχουμε αύξηση του z. Η αντιστοιχία είναι ένα προς ένα επειδή οι αυξήσεις των x,y εναλλάσσονται.

Ισχυρίζομαι ότι \displaystyle  R(m,k) = \frac{3k-2m+1}{k+1}\binom{m}{k} = 3\binom{m}{k} - 2\binom{m+1}{k+1} αν 2m/3 \leqslant k \leqslant m. (Και R(m,k) = 0 σε διαφορετική περίπτωση.) Αυτό θα δώσει \displaystyle  R(3n,2n) = \frac{1}{2n+1}\binom{3n}{2n}.

Θα το αποδείξουμε με επαγωγή στο m. Η περίπτωση m=1 είναι προφανής. Έστω λοιπόν ότι m > 1. Προφανώς R(m,k) = 0 αν m < k ή αν 2m/3 > k. Ας υποθέσουμε λοιπόν ότι 2m/3 \leqslant k \leqslant m.

Υπάρχουν R(m-1,k-1) τέτοιες λέξεις με τελευταίο γράμμα το A και R(m-1,k) τέτοιες λέξεις με τελευταίο γράμμα το B.

Άρα:

\displaystyle  \begin{aligned} 
R(m,k) &= R(m-1,k-1) + R(m-1,k) \\ 
&= 3\binom{m-1}{k-1} - 2\binom{m}{k} + 3\binom{m-1}{k} - 2\binom{m}{k+1} \\ 
&= 3\binom{m}{k} - 2\binom{m+1}{k+1} 
\end{aligned}

και το επαγωγικό βήμα (σχεδόν) ολοκληρώθηκε.

Πρέπει όμως να ελέγξουμε και τις περιπτώσεις όπου τα R(m-1,k-1) και R(m-1,k) πιθανώς να ισούνται με 0. Αυτό συμβαίνει μόνο όταν k=m ή 2m=3k. Στην πρώτη περίπτωση έχουμε R(m-1,k)=0 και στην δεύτερη R(m-1,k-1)=0.

Στην πρώτη περίπτωση είναι R(m,k) = R(m,m) = R(m-1,m-1) = 1. Στην δεύτερη είναι

\displaystyle  \displaystyle{R(m,k) = R(m-1,k) = \frac{3k-2(m-1)+1}{k+1}\binom{m-1}{k} = \frac{3}{k+1} \binom{m-1}{k} = \frac{3}{k+1}\frac{m-k}{m} \binom{m}{k} = \frac{1}{k+1}\binom{m}{k}}

Και στις δύο περιπτώσεις το επαγωγικό βήμα ολοκληρώνεται.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

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