Putnam 2015/A2

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

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

Putnam 2015/A2

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Δεκ 07, 2015 6:29 pm

Θεωρούμε την ακολουθία (a_n) που ορίζεται ως a_0=1,a_1 = 2 και a_n = 4a_{n-1}-a_{n-2} για n \geqslant 2.

Να βρεθεί ένας περιττός πρώτος διαιρέτης του a_{2015}.


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

Re: Putnam 2015/A2

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Δεκ 07, 2015 6:57 pm

Αν δεν κάνω λάθος η ακολουθία \bmod 7 είναι 1,2,0,5,6,5,0,2 και μετά επαναλαμβάνεται. Οπότε 7|a_{n} για κάθε n \equiv 3,7 \bmod 8. Άρα είναι και 7|a_{2015}.

Μάλλον όχι η ζητούμενη λύση.

Επεξεργασία: Άκυρο αφού η ακολουθία ξεκινάει από το a_0 και όχι από το a_1.


panagiotis99
Δημοσιεύσεις: 133
Εγγραφή: Δευ Φεβ 04, 2013 8:24 pm
Τοποθεσία: Αθηνα

Re: Putnam 2015/A2

#3

Μη αναγνωσμένη δημοσίευση από panagiotis99 » Δευ Δεκ 07, 2015 11:12 pm

Demetres έγραψε:Θεωρούμε την ακολουθία (a_n) που ορίζεται ως a_0=1,a_1 = 2 και a_n = 4a_{n-1}-a_{n-2} για n \geqslant 2.

Να βρεθεί ένας περιττός πρώτος διαιρέτης του a_{2015}.

Kαλησπέρα Κύριε Δημήτρη, μπορεί να έχω κάνει λάθος άλλα μου φάνηκε κάπως εύκολη για Putnam.

Eύκολα μπορούμε να υπολογίσμουμε τον όρο a_{5}=362=2*181

Aρκεί να δέιξω ότι 181 \mid a_{2015}
Tώρα υπολογίζοντας 40 όρους mod 181 έχουμε:
a_{0}\equiv 1
a_{1}\equiv 2
a_{2}\equiv 7
a_{3}\equiv 26
a_{4}\equiv 97
a_{5}\equiv 0
a_{6}\equiv -97
a_{7}\equiv -26
a_{8}\equiv -7
a_{9}\equiv -2
a_{10}\equiv -1
a_{11}\equiv -2
a_{12}\equiv-7
a_{13}\equiv -26
a_{14}\equiv -97
a_{15}\equiv 0
a_{16}\equiv 97
a_{17}\equiv 26
a_{18}\equiv 7
a_{19}\equiv 2

a_{20}\equiv 1
a_{21}\equiv 2
a_{22}\equiv 7
a_{23}\equiv 26
a_{24}\equiv 97
a_{25}\equiv 0
a_{26}\equiv -97
a_{27}\equiv -26
a_{28}\equiv -7
a_{29}\equiv -2
a_{30}\equiv -1
a_{31}\equiv -2
a_{32}\equiv-7
a_{33}\equiv -26
a_{34}\equiv -97
a_{35}\equiv 0
a_{36}\equiv 97
a_{37}\equiv 26
a_{38}\equiv 7
a_{39}\equiv 2

Παρατηρούμε ότι η ακολουθία είναι περιοδική mod 181 με περιοδο 20 και αφού 15 \equiv 2015 mod 20 το ζητούμενο δείχθηκε.

Αρκετές πράξεις έγιναν με κομπιουτεράκι :oops: :oops:


Άβαταρ μέλους
emouroukos
Γενικός Συντονιστής
Δημοσιεύσεις: 1389
Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
Τοποθεσία: Αγρίνιο

Re: Putnam 2015/A2

#4

Μη αναγνωσμένη δημοσίευση από emouroukos » Τρί Δεκ 08, 2015 12:25 am

Μια άλλη προσέγγιση:

Η χαρακτηριστική εξίσωση της αναδρομικής σχέσης \displaystyle{{a_n} = 4{a_{n - 1}} - {a_{n - 2}}} είναι η \displaystyle{{t^2} - 4t + 1 = 0,} με ρίζες \displaystyle{{t_1} = 2 + \sqrt 3 } και \displaystyle{{t_2} = 2 - \sqrt 3 .} Άρα, υπάρχουν σταθερές \displaystyle{{c_1}} και \displaystyle{{c_2}} τέτοιες, ώστε

\displaystyle{{a_n} = {c_1}{\left( {2 + \sqrt 3 } \right)^n} + {c_2}{\left( {2 - \sqrt 3 } \right)^n}}

για κάθε φυσικό αριθμό n. Από τις αρχικές συνθήκες βρίσκουμε ότι:

\displaystyle{\left\{ {\begin{array}{*{20}{c}} 
{{a_0} = 1}\\ 
{{a_1} = 2} 
\end{array}} \right\} \Leftrightarrow \left\{ {\begin{array}{*{20}{c}} 
{{c_1} + {c_2} = 1}\\ 
{{c_1}\left( {2 + \sqrt 3 } \right) + {c_2}\left( {2 - \sqrt 3 } \right) = 2} 
\end{array}} \right\} \Leftrightarrow \left\{ {\begin{array}{*{20}{c}} 
{{c_1} + {c_2} = 1}\\ 
{{c_1} = {c_2}} 
\end{array}} \right\} \Leftrightarrow {c_1} = {c_2} = \frac{1}{2},}

οπότε

\displaystyle{{a_n} = \frac{1}{2}\left[ {{{\left( {2 + \sqrt 3 } \right)}^n} + {{\left( {2 - \sqrt 3 } \right)}^n}} \right]}

για κάθε φυσικό αριθμό n. Θέτοντας \displaystyle{{x = 2 + \sqrt 3 },} έχουμε ότι \displaystyle{{\frac{1}{x} = 2 - \sqrt 3 },} οπότε

\displaystyle{{a_n} = \frac{1}{2}\left( {{x^n} + \frac{1}{{{x^n}}}} \right)}

για κάθε φυσικό αριθμό n. Τώρα παρατηρούμε ότι:

\displaystyle{{a_{2015}} = \frac{1}{2}\left( {{x^{2015}} + \frac{1}{{{x^{2015}}}}} \right) = \frac{1}{2}\left( {{{\left( {{x^5}} \right)}^{403}} + {{\left( {\frac{1}{{{x^5}}}} \right)}^{403}}} \right) = }

\displaystyle{ = \frac{1}{2}\left( {{x^5} + \frac{1}{{{x^5}}}} \right)}\displaystyle{\left( {{x^{402 \cdot 5}} - {x^{401 \cdot 5}}\frac{1}{{{x^5}}} + {x^{400 \cdot 5}}\frac{1}{{{x^{2 \cdot 5}}}} -  \cdots  - {x^{201 \cdot 5}}\frac{1}{{{x^{201 \cdot 5}}}} +  \cdots  + {x^{2 \cdot 5}}\frac{1}{{{x^{400 \cdot 5}}}} - {x^5}\frac{1}{{{x^{401 \cdot 5}}}} + \frac{1}{{{x^{402 \cdot 5}}}}} \right) = }

\displaystyle{ = {a_5}\left( {2{a_{2010}} - 2{a_{2000}} + 2{a_{1990}} -  \cdots  + 2{a_{10}} - 1} \right),}

οπότε ο \displaystyle{{a_5} = 362 = 2 \cdot 181} διαιρεί τον \displaystyle{{a_{2015}}} και άρα ο αριθμός 181 είναι ένας περιττός πρώτος διαιρέτης του \displaystyle{{a_{2015}}.}


Βαγγέλης Μουρούκος

Erro ergo sum.
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11143
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Putnam 2015/A2

#5

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τρί Δεκ 08, 2015 12:34 am

Με πρόλαβε ο Βαγγέλης. Έβαλε την λύση του όσο έγραφα.

Για ... παρηγοριά ας γράψω ότι πέραν του 181 βρήκα ότι και ο 373 είναι πρώτος διαιρέτης του a_{2015}. Και ένας ακόμα μεγαλύτερος πρώτος διαιρέτης είναι ο 6811741. Το αφήνω αλλά σημειώνω ότι 373 διαιρεί τον a_{31} που διαιρεί τον a_{2015} ενώ συμβαίνει το ανάλογο με τους 6811741 και a_{13}.


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

Re: Putnam 2015/A2

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Δεκ 08, 2015 11:16 am

panagiotis99 έγραψε:
Demetres έγραψε:Θεωρούμε την ακολουθία (a_n) που ορίζεται ως a_0=1,a_1 = 2 και a_n = 4a_{n-1}-a_{n-2} για n \geqslant 2.

Να βρεθεί ένας περιττός πρώτος διαιρέτης του a_{2015}.

Kαλησπέρα Κύριε Δημήτρη, μπορεί να έχω κάνει λάθος άλλα μου φάνηκε κάπως εύκολη για Putnam.

Eύκολα μπορούμε να υπολογίσμουμε τον όρο a_{5}=362=2*181

Aρκεί να δέιξω ότι 181 \mid a_{2015}
Tώρα υπολογίζοντας 40 όρους mod 181 έχουμε:
a_{0}\equiv 1
a_{1}\equiv 2
a_{2}\equiv 7
a_{3}\equiv 26
a_{4}\equiv 97
a_{5}\equiv 0
a_{6}\equiv -97
a_{7}\equiv -26
a_{8}\equiv -7
a_{9}\equiv -2
a_{10}\equiv -1
a_{11}\equiv -2
a_{12}\equiv-7
a_{13}\equiv -26
a_{14}\equiv -97
a_{15}\equiv 0
a_{16}\equiv 97
a_{17}\equiv 26
a_{18}\equiv 7
a_{19}\equiv 2

a_{20}\equiv 1
a_{21}\equiv 2
a_{22}\equiv 7
a_{23}\equiv 26
a_{24}\equiv 97
a_{25}\equiv 0
a_{26}\equiv -97
a_{27}\equiv -26
a_{28}\equiv -7
a_{29}\equiv -2
a_{30}\equiv -1
a_{31}\equiv -2
a_{32}\equiv-7
a_{33}\equiv -26
a_{34}\equiv -97
a_{35}\equiv 0
a_{36}\equiv 97
a_{37}\equiv 26
a_{38}\equiv 7
a_{39}\equiv 2

Παρατηρούμε ότι η ακολουθία είναι περιοδική mod 181 με περιοδο 20 και αφού 15 \equiv 2015 mod 20 το ζητούμενο δείχθηκε.

Αρκετές πράξεις έγιναν με κομπιουτεράκι :oops: :oops:
Θα μπορούσες να σταματήσεις στα a_{20},a_{21}. Εκεί εμφανίζονται για πρώτη φορά ξανά τα 1,2 οπότε μετά σίγουρα έχουμε περιοδικότητα.


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

Re: Putnam 2015/A2

#7

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Δεκ 08, 2015 11:23 am

Η λύση μου είναι παρόμοια με του Βαγγέλη αλλά με διαφορετικό τελείωμα.

Αφού κατέληξα στο \displaystyle{ a_n = \frac{1}{2}\left(x^n + \frac{1}{x^n} \right)} μετά είπα \displaystyle{ b_n = a_{5n} = \frac{1}{2}(r^n + s^n)} όπου r=x^5 και s = 1/x^5. Οπότε η b_n ορίζεται ως b_0=1,b_1=362 και b_{n+2} = (r+s)b_{n+1} - rs b_n. Έχουμε όμως rs = 1 και

\displaystyle{r+s = (2+\sqrt{3})^5 + (2-\sqrt{3})^5 = 2\left(2^5 + \binom{5}{2}(\sqrt{3})^2 \cdot 2^3 + \binom{5}{4}(\sqrt{3})^4 \cdot 2\right) = 2(32 + 240 + 90) = 2 \cdot 362.}

Οπότε \bmod 362 η ακολουθία είναι 1,0,-1,0 και μετά επαναλαμβάνεται. Άρα 362|a_{2015} και άρα 181|a_{2015}.


Απάντηση

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

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

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