IMC 2018/2/3

#1

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

Ένας βάτραχος κινείται στα σημεία του $\Omega$ με πηδήματα μήκους

. Για κάθε θετικό ακέραιο

να βρεθεί με πόσους διαφορετικούς τρόπους μπορεί ξεκινώντας από το (0,0,0)

να φτάσει στο (n,n,n)

σε ακριβώς

πηδήματα.

dement · #2

Οι κινήσεις του βατράχου κατά μήκος των αξόνων x,y

θα ακολουθήσουν υποχρεωτικά το μοτίβο (x,y) = (0,0), (1,0), (1,1), (2,1), (2,2), ..., (n,n)

Ανάμεσα σε αυτές τις

κινήσεις μπαίνουν οι

κινήσεις κατά μήκος του άξονα

. Αν δεν υπήρχαν περιορισμοί για το

, κατά συνέπεια, θα είχαμε $\displaystyle \binom{3n}{n}$ επιλογές.

Σε κάθε πορεία που ικανοποιεί τους περιορισμούς των x, y

αλλά όχι απαραίτητα του

, αντιστοιχίζουμε έναν αριθμό

("βαθμό απαγόρευσης") ο οποίος αντιστοιχεί στον αριθμό των

κινήσεων που καταλήγουν σε απαγορευμένη θέση (κάθε τέτοια

κίνηση μετράει διπλή αν καταλήγει σε θέση με x < z

, οπότε προφανώς και y < z

, και μονή αν καταλήγει μόνο σε θέση με y < z = x

). Μια τέτοια πορεία λέγεται

απαγορευμένη. Προφανώς $0 \leqslant k \leqslant 2n$ και μας ενδιαφέρουν οι

απαγορευμένες πορείες.

Στη συνέχεια χρησιμοποιούμε ένα επιχείρημα παρόμοιο με αυτό που διαιρεί τον διωνυμικό συντελεστή $\displaystyle \binom{2n}{n}$ με n+1

για να παραγάγει τον αριθμό Catalan C_n

ως τον αριθμό των λέξεων Dyck. Κατασκευάζουμε bijection μεταξύ των (k+1)-

απαγορευμένων και των

απαγορευμένων διαδρομών ως εξής: στην (k+1)-

απαγορευμένη διαδρομή εντοπίζουμε την πρώτη

κίνηση που πηγαίνει σε θέση με x=y=z

και εναλλάσσουμε το σύνολο των κινήσεων μετά από αυτήν με εκείνο πριν από αυτήν (αν χρειαστεί, μετονομάζουμε τις

και

κινήσεις ώστε να εναλλάσσονται). Το αποτέλεσμα είναι μία

απαγορευμένη διαδρομή. Για την αντίστροφη απεικόνιση, εντοπίζουμε την τελευταία

κίνηση από θέση με x=y=z

και, πάλι, εναλλάσσουμε το σύνολο των κινήσεων μετά από αυτήν με εκείνο πριν από αυτήν. Παραπέμπω στο https://en.wikipedia.org/wiki/Catalan_n ... hird_proof για περισσότερες πληροφορίες.

Έτσι, όλοι οι 2n+1

"βαθμοί απαγόρευσης" των $\displaystyle \binom{3n}{n}$ διαδρομών είναι ισοπληθείς και οι

απαγορευμένες διαδρομές είναι $\displaystyle \frac{1}{2n+1} \binom{3n}{n}$ το πλήθος.

#3

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

Ας γράψουμε R(m,k)

για το πλήθος των λέξεων

γραμμάτων στο αλφάβητο A,B

όπου ακριβώς

από τα γράμματα είναι

και σε κάθε αρχικό κομμάτι της λέξης υπάρχουν τουλάχιστον διπλάσια

από

.

Το ζητούμενο ισούται με R(3n,2n)

αφού σε κάθε κίνηση του βατράχου μπορούμε να αντιστοιχίσουμε το γράμμα

αν έχουμε αύξηση των

ή

και το γράμμα

αν έχουμε αύξηση του

. Η αντιστοιχία είναι ένα προς ένα επειδή οι αυξήσεις των 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=1

είναι προφανής. Έστω λοιπόν ότι m > 1

. Προφανώς R(m,k) = 0

αν

ή αν

. Ας υποθέσουμε λοιπόν ότι $2m/3 \leqslant k \leqslant m$ .

Υπάρχουν R(m-1,k-1)

τέτοιες λέξεις με τελευταίο γράμμα το

και

τέτοιες λέξεις με τελευταίο γράμμα το

.

Άρα:

$\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)

και

πιθανώς να ισούνται με

. Αυτό συμβαίνει μόνο όταν k=m

ή

. Στην πρώτη περίπτωση έχουμε 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}}$

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

IMC 2018/2/3

IMC 2018/2/3

Re: IMC 2018/2/3

Re: IMC 2018/2/3

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