Σελίδα 1 από 1

Δυνατές διαδρομές και πρώτοι

Δημοσιεύτηκε: Τετ Ιαν 11, 2017 3:25 pm
από Γιάννης Μπόρμπας
Τετράγωνο ABCD πλευράς n όπου n θετικός ακέραιος διαιρείται σε n^2 μοναδιαία τετράγωνα όπως στο σχήμα. (Περίπτωση για n=3) Στην συνέχεια φέρνουμε την διαγώνιο του κάθε μοναδιαίου τετραγώνου που είναι παράλληλη με την BD. Μία αράχνη ξεκινάει από το A θέλοντας να φτάσει στο C μέσω των ευθυγράμμων τμημάτων υπό τις εξής προϋποθέσεις:
1)Πρέπει να κινείται προς τα πάνω ή προς τα δεξιά
2)Μπορεί να διασχίσει ένα διαγώνιο ευθύγραμμο τμήμα από πάνω-αριστερά προς κάτω-δεξιά μήκους \sqrt{2} αν στην αμέσως προηγούμενη κίνηση κινήθηκε προς τα πάνω.
Έστω P(n) το πλήθος των διαδρομών που μπορεί να διασχίσει η αράχνη για να φτάσει στο C από το A. Να βρεθούν όλοι οι πρώτοι αριθμοί p που είναι τέτοιοι ώστε p|P(p)
Screenshot_1.png
Σχήμα
Screenshot_1.png (15.01 KiB) Προβλήθηκε 256 φορές
.
Δυστυχώς δεν έχω μάθει να χειρίζομαι το Geogebra οπότε το σχήμα είναι σε Screenshot.

Re: Δυνατές διαδρομές και πρώτοι

Δημοσιεύτηκε: Τετ Ιαν 11, 2017 9:05 pm
από Demetres
Βάζουμε συντεταγμένες ώστε κάτω αριστερά να έχουμε συντεταγμένες (0,0) και πάνω δεξιά (p,p).

Γράφουμε A(m,n) για το πλήθος των δυνατών διαδρομών ώστε να φτάσουμε στο σημείο (m,n).

Παρατηρούμε ότι:

A(0,n) = 1 για κάθε n \in \{0,1,\ldots,p\}

A(m,0) = 2A(m-1,0) για κάθε m \in \{1,\ldots,p\} το οποίο επαγωγικά δίνει A(m,0) = 2^m για κάθε m \in \{0,1,\ldots,p-1\}.

A(m,n) = 2A(m-1,n) + A(m,n-1) για κάθε m \in \{1,2,\ldots,p\} και n \in \{1,2,\ldots,p-1\}. (Προσοχή. Αυτό δεν ισχύει για n=p.) Γράφοντας τους πρώτους λίγους όρους δεν αργούμε να μαντέψουμε ότι

\displaystyle{ A(m,n) = 2^m\binom{m+n}{n}}

για m \in \{0,1,\ldots,p\} και n \in \{0,1,\ldots,p-1\}. Η απόδειξη είναι με απλή επαγωγή.

Επομένως \displaystyle{ A(m,p-1) \equiv 0 \bmod p} για κάθε m \in \{1,2,\ldots,p-1\}.

Επιπλέον \displaystyle{ A(p,p-1) = 2^p \binom{2p-1}{p-1} = 2^p \frac{(p+1)(p+2) \cdots (2p-1)}{(p-1)!} \equiv 2 \bmod p} για p περιττό. Επίσης A(2,1) = 12 \equiv 0 \equiv 2 \bmod 2.

Τέλος παρατηρούμε ότι A(m,p) = A(m-1,p) + A(m,p-1) για κάθε m \in \{1,2,\ldots,p-1\}. Επαγωγικά καταλήγουμε στο A(m,p) \equiv 1 \bmod p για κάθε m \in \{0,1,\ldots,p-1\}

Εν τέλει, έχουμε A(p,p) \equiv 3 \bmod p.

Άρα p|A(p,p) αν και μόνο αν p=3.

Re: Δυνατές διαδρομές και πρώτοι

Δημοσιεύτηκε: Τετ Ιαν 11, 2017 10:01 pm
από Γιάννης Μπόρμπας
Demetres έγραψε:Βάζουμε συντεταγμένες ώστε κάτω αριστερά να έχουμε συντεταγμένες (0,0) και πάνω δεξιά (p,p).

Γράφουμε A(m,n) για το πλήθος των δυνατών διαδρομών ώστε να φτάσουμε στο σημείο (m,n).

Παρατηρούμε ότι:

A(0,n) = 1 για κάθε n \in \{0,1,\ldots,p\}

A(m,0) = 2A(m-1,0) για κάθε m \in \{1,\ldots,p\} το οποίο επαγωγικά δίνει A(m,0) = 2^m για κάθε m \in \{0,1,\ldots,p-1\}.

A(m,n) = 2A(m-1,n) + A(m,n-1) για κάθε m \in \{1,2,\ldots,p\} και n \in \{1,2,\ldots,p-1\}. (Προσοχή. Αυτό δεν ισχύει για n=p.) Γράφοντας τους πρώτους λίγους όρους δεν αργούμε να μαντέψουμε ότι

\displaystyle{ A(m,n) = 2^m\binom{m+n}{n}}

για m \in \{0,1,\ldots,p\} και n \in \{0,1,\ldots,p-1\}. Η απόδειξη είναι με απλή επαγωγή.

Επομένως \displaystyle{ A(m,p-1) \equiv 0 \bmod p} για κάθε m \in \{1,2,\ldots,p-1\}.

Επιπλέον \displaystyle{ A(p,p-1) = 2^p \binom{2p-1}{p-1} = 2^p \frac{(p+1)(p+2) \cdots (2p-1)}{(p-1)!} \equiv 2 \bmod p} για p περιττό. Επίσης A(2,1) = 12 \equiv 0 \equiv 2 \bmod 2.

Τέλος παρατηρούμε ότι A(m,p) = A(m-1,p) + A(m,p-1) για κάθε m \in \{1,2,\ldots,p-1\}. Επαγωγικά καταλήγουμε στο A(m,p) \equiv 1 \bmod p για κάθε m \in \{0,1,\ldots,p-1\}

Εν τέλει, έχουμε A(p,p) \equiv 3 \bmod p.

Άρα p|A(p,p) αν και μόνο αν p=3.

:10sta10: Επίσης ισχύει ότι \sum_{k=0}^{n}A(k,n-1)=P(n)