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

Γιάννης Μπόρμπας · #1

Τετράγωνο

πλευράς

όπου

θετικός ακέραιος διαιρείται σε n^2

μοναδιαία τετράγωνα όπως στο σχήμα. (Περίπτωση για n=3

) Στην συνέχεια φέρνουμε την διαγώνιο του κάθε μοναδιαίου τετραγώνου που είναι παράλληλη με την

. Μία αράχνη ξεκινάει από το

θέλοντας να φτάσει στο

μέσω των ευθυγράμμων τμημάτων υπό τις εξής προϋποθέσεις:
1)Πρέπει να κινείται προς τα πάνω ή προς τα δεξιά
2)Μπορεί να διασχίσει ένα διαγώνιο ευθύγραμμο τμήμα από πάνω-αριστερά προς κάτω-δεξιά μήκους $\sqrt{2}$ αν στην αμέσως προηγούμενη κίνηση κινήθηκε προς τα πάνω.
Έστω P(n)

το πλήθος των διαδρομών που μπορεί να διασχίσει η αράχνη για να φτάσει στο

από το

. Να βρεθούν όλοι οι πρώτοι αριθμοί

που είναι τέτοιοι ώστε p|P(p)

: Σχήμα; Screenshot_1.png (15.01 KiB) Προβλήθηκε 1643 φορές

.
Δυστυχώς δεν έχω μάθει να χειρίζομαι το Geogebra οπότε το σχήμα είναι σε Screenshot.

#2

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

περιττό. Επίσης $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

.

Γιάννης Μπόρμπας · #3

Demetres έγραψε:Βάζουμε συντεταγμένες ώστε κάτω αριστερά να έχουμε συντεταγμένες και πάνω δεξιά .

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

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

για κάθε $n \in \{0,1,\ldots,p\}$

για κάθε $m \in \{1,\ldots,p\}$ το οποίο επαγωγικά δίνει για κάθε $m \in \{0,1,\ldots,p-1\}$ .

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

$\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}$ για περιττό. Επίσης $A(2,1) = 12 \equiv 0 \equiv 2 \bmod 2$ .

Τέλος παρατηρούμε ότι για κάθε $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$ .

Άρα αν και μόνο αν .

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

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

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

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

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

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