Putnam 2015/A2

#1

Θεωρούμε την ακολουθία (a_n)

που ορίζεται ως a_0=1,a_1 = 2

και $a_n = 4a_{n-1}-a_{n-2}$ για $n \geqslant 2$ .

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

#2

Αν δεν κάνω λάθος η ακολουθία $\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 · #3

Demetres έγραψε:Θεωρούμε την ακολουθία που ορίζεται ως και $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ώρα υπολογίζοντας

όρους

έχουμε:
$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

με περιοδο

και αφού $15 \equiv 2015 mod 20$ το ζητούμενο δείχθηκε.

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

#4

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

Η χαρακτηριστική εξίσωση της αναδρομικής σχέσης $\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}}$

για κάθε φυσικό αριθμό

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

$\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]}$

για κάθε φυσικό αριθμό

. Θέτοντας $\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)}$

για κάθε φυσικό αριθμό

. Τώρα παρατηρούμε ότι:

$\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}}.}$

#5

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

Για ... παρηγοριά ας γράψω ότι πέραν του 181

βρήκα ότι και ο 373

είναι πρώτος διαιρέτης του $a_{2015}$ . Και ένας ακόμα μεγαλύτερος πρώτος διαιρέτης είναι ο 6811741

. Το αφήνω αλλά σημειώνω ότι 373

διαιρεί τον $a_{31}$ που διαιρεί τον $a_{2015}$ ενώ συμβαίνει το ανάλογο με τους 6811741

και $a_{13}$ .

#6

panagiotis99 έγραψε:
Demetres έγραψε:Θεωρούμε την ακολουθία που ορίζεται ως και $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ώρα υπολογίζοντας όρους έχουμε:
$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$

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

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

Θα μπορούσες να σταματήσεις στα $a_{20},a_{21}$ . Εκεί εμφανίζονται για πρώτη φορά ξανά τα 1,2

οπότε μετά σίγουρα έχουμε περιοδικότητα.

#7

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

Αφού κατέληξα στο $\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

και

. Οπότε η

ορίζεται ως 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}$ .

Putnam 2015/A2

Putnam 2015/A2

Re: Putnam 2015/A2

Re: Putnam 2015/A2

Re: Putnam 2015/A2

Re: Putnam 2015/A2

Re: Putnam 2015/A2

Re: Putnam 2015/A2

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