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

Συντονιστές: Demetres, silouan

Άβαταρ μέλους
Γιάννης Μπόρμπας
Δημοσιεύσεις: 194
Εγγραφή: Τρί Δεκ 13, 2016 10:41 pm
Τοποθεσία: Χανιά

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

Μη αναγνωσμένη δημοσίευση #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) Προβλήθηκε 574 φορές
.
Δυστυχώς δεν έχω μάθει να χειρίζομαι το Geogebra οπότε το σχήμα είναι σε Screenshot.



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

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

Μη αναγνωσμένη δημοσίευση #2 από Demetres » Τετ Ιαν 11, 2017 9:05 pm

Βάζουμε συντεταγμένες ώστε κάτω αριστερά να έχουμε συντεταγμένες (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.


Άβαταρ μέλους
Γιάννης Μπόρμπας
Δημοσιεύσεις: 194
Εγγραφή: Τρί Δεκ 13, 2016 10:41 pm
Τοποθεσία: Χανιά

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

Μη αναγνωσμένη δημοσίευση #3 από Γιάννης Μπόρμπας » Τετ Ιαν 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)



Επιστροφή σε “Συνδυαστική - Επίπεδο Αρχιμήδη (Seniors)”

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

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