2008 bmo shortlist x3

tasosty · #1

1.
Η ακολουθία x_1,x_2,...x_n,...

ακεραίων αριθμών δίνεται με

x_1=1

και $x_{n+1}=x_n+x_{\lceil\frac{n}{2}\rceil}$

NΔΟ 4 $\nmid$ $x_i \forall i=1,2,...,n,...$

2.
Να λύσετε στους πρώτους αριθμούς την εξίσωση
$xyz+1=2^{y^2+1}$

3.
Έστω { ${a_n}$ } η ακολουθία με a_1=0

και $a_{n+1}=a_n+2$ για περιττό n και $a_{n+1}=2a_n$ για άρτιο n
NΔΟ για κάθε πρώτο p>3 o αριθμός $\frac{2^{2p}-1}{3}$ διαιρεί τον a_n

για άπειρες τιμές του n

Zarifis · #2

tasosty έγραψε: 2.
Να λύσετε στους πρώτους αριθμούς την εξίσωση
$xyz+1=2^{y^2+1}$

$xyz +1\equiv 0 mod2 \Rightarrow 2 \nmid xyz$
$1\equiv2*(2^{y})^y mod(y)$ Από Μικρό θεώρημα Fermat αφού $y= prime{\color{red} (1)}$ και (2,y)=1

άρα: $1\equiv2*2^{y} mod(y)$ Ομοίως $1\equiv4 mod(y) \Rightarrow y\mid 3 \Rightarrow_{\color{red} (1)} y=3$
$3xz+1=1024 \Rightarrow xy=341 =11*31\Rightarrow (x,y,z)=(11,3,31),(31,3,11)$

sokratis lyras · #3

tasosty έγραψε:
2.
Να λύσετε στους πρώτους αριθμούς την εξίσωση
$xyz+1=2^{y^2+1}$

Αρχικά,κανείς από τους x,y,z

δεν είναι

.Επίσης παρατηρούμε ότι $RHS\equiv 1\bmod 3$ .Άρα τουλάχιστον ένας από τους x,y,z

θα ισούαι με

.

Για

παίρνουμε

΄(ή το αντίστροφο).
Για x=3

έχουμε έύκολα άτοπο(όπως και για z=3

).
**Ευχαριστώ Τάσο

#4

tasosty έγραψε:1.
Η ακολουθία ακεραίων αριθμών δίνεται με

και $x_{n+1}=x_n+x_{\lceil\frac{n}{2}\rceil}$

NΔΟ 4 $\nmid$ $x_i \forall i=1,2,...,n,...$

Έστω

το υπόλοιπο της διαίρεσης του x_n

με το 4. Ισχυρίζομαι ότι αν γράψουμε το

στην δυαδική του μορφή τότε
(α) Αν τελειώνει μη περιττό αριθμό μηδενικών, τότε y_n = 2

.
(β) Αν τελειώνει με άρτιο αριθμό μηδενικών τότε
(β1) Αν περιέχει περιττό αριθμό άσσων τότε y_n=1

.
(β2) Αν περιέχει άρτιο αριθμό άσσων τότε y_n=3

.

Το ζητούμενο είναι άμεσο από το πιο πάνω.

Θα το αποδείξουμε με επαγωγή. Ο ισχυρισμός είναι προφανής για n=1,2

. Υποθέτουμε ότι ο ισχυρισμός ισχύει για κάθε $n \leqslant 2k$ και θα δείξουμε ότι ισχύει για n=2k+1

και

.

Για

έχουμε $y_{2κ+1} \equiv y_{2k} + y_k \bmod 4$ . Παρατηρούμε ότι ο

έχει ένα περισσότερο μηδενικό από τον

στην δυαδική του γραφή και ότι έχουν και οι δύο τον ίδιο αριθμό άσσων. Άρα ακριβώς ένας από τους $y_k,y_{2k}$ θα ισούται με 2 και ο άλλος θα ισούται είτε με 1 είτε με 3 ανάλογα αν ο αριθμός των άσσων είναι περιττός ή άρτιος. Άρα ο $y_{2k+1}$ θα ισούται είτε με 3 είτε με 1 ανάλογα αν ο αριθμός των άσσων στην δυαδική μορφή του

είναι περιττός ή άρτιος. Επειδή όμως ο 2k+1

δεν τελειώνει σε μηδέν και έχει ένα περισσότερο άσσο στην δυαδική του μορφή από τους k,2k

ο ισχυρισμός μας ισχύει για n=2k+1

.

Για

έχουμε $y_{2k+2} \equiv y_{2k+1} + y_{k+1} \bmod 4$ . Έστω ότι ο k+1

τελειώνει σε

μηδενικά και έχει

άσσους. Αν ο

είναι περιττός τότε $y_{k+1}=2$ . Επίσης ο 2k+2

έχει

άσσους και τελειώνει σε άρτιο αριθμό μηδενικών ενώ ο 2k+1

έχει

άσσους και επίσης τελειώνει σε άρτιο αριθμό μηδενικών. Επειδή ο ένας από τους s+r,s

είναι άρτιος και ο άλλος περιττός ο ισχυρισμός μας στην περίπτωση που ο

είναι περιττός ισχύει για n=2k+2

. Τέλος αν ο

είναι άρτιος τότε ο $y_{k+1}$ ισούται με 1 ή 3 και ακριβώς το ίδιο ισχύει για τον $y_{2k+1}$ αφού έχει $s+r \equiv s \bmod 2$ άσσους και τελειώνει με άρτιο αριθμό μηδενικών. Επειδή ο 2k+2

τελειώνει σε r+1

άσσους που είναι περιττός, τότε $y_{2k+2} = 2$ και άρα ο ισχυρισμός μας πάλι ισχύει.

2008 bmo shortlist x3

2008 bmo shortlist x3

Re: 2008 bmo shortlist x3

Re: 2008 bmo shortlist x3

Re: 2008 bmo shortlist x3

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