Σελίδα 7 από 11

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Δευ Ιούλ 11, 2011 11:32 pm
από Nick1990
socrates έγραψε:60.

Το άθροισμα των διαιρετών ενός θετικού ακεραίου n, συμπεριλαμβανομένου και του n, ισούται με 2n+1.
Να δείξετε ότι ο n είναι τέλειο τετράγωνο περιττού.

Οι αριθμοί αυτοί λέγονται Quasiperfect και δεν είναι γνωστό αν υπάρχουν...

Έστω p_0=2 και p_1,...,p_k οι πρώτοι που διαιρούν τον n, και a_i \geq 0, i=0,..,k οι αντίστοιχοι εκθέτες των p_i, i=0,...,k στην παραγοντοποίηση του n σε πρώτους.
Ισοδύναμα έχουμε:
\prod_{i=0}^{k}{\frac{{p_i}^{a_i+1} - 1}{p_i - 1}} = 2^{a_0+1}\prod_{i=1}^{k}{{p_i}^{a_i}} + 1 (*)
και θέλουμε νδο a_0=0 και a_i άρτιος για i=1,2,...k
Αν κάποιος από τους a_i, i \geq 1 ήταν περιττός, τότε θα ήταν \frac{{p_i}^{a_i+1} - 1}{p_i - 1} = {p_i}^{a_i} + ... + p_i + 1 = a_i + 1 (mod2) = 0(mod2) που έιναι άτοπο αφού τότε το αριστερό μέλος της (*) θα ήταν άρτιος ενώ το δεξί περιττός.
Μένει νδο a_0=0. Πράγματι η (*) ισοδύναμα γράφεται:
(2^{a_0+1} - 1)(\prod_{i=0}^{k}{\frac{{p_i}^{a_i+1} - 1}{p_i - 1}} - \prod_{i=1}^{k}{{p_i}^{a_i}}) = \prod_{i=1}^{k}{{p_i}^{a_i}} + 1 = d^2 + 1 όταν d=\prod_{i=1}^{k}{{p_i}^{\frac{a_i}{2}}} \in N,
και αν a_0 > 0 και 2^{a_0+1} - 1 = s τότε s|d^2+1 και s = 3(mod4) που είναι άτοπο αφού από γνωστό θεώρημα (δείτε και τη λύση του Δημήτρη λίγο πιο πάνω) όλοι οι περιττοί διαιρέτες του d^2+1 αφήνουν υπόλοιπο 1 με το 4

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Τετ Ιούλ 20, 2011 5:31 pm
από Demetres
socrates έγραψε:

45.
Να λυθούν στους φυσικούς αριθμούς οι εξισώσεις:
i) a!+b!+c! =a!b!
ii) a!b! =a!+b!+2^{c}
(i) Χωρίς βλάβη της γενικότητας έχουμε a \leqslant b. Αν a = 0 ή a=1, τότε 1 + b! + c! = b! άτοπο. Επίσης, αν a = 2, τότε c! = b! - 2 το οποίο δεν έχει λύσει. Πράγματι αν είχε τότε θα είχαμε b > c και άρα b! \geqslant (b-1)! + 4 > c! + 2 για b \geqslant 3. (Για b < 3 είναι απλός έλεγχος.) Άρα a \geqslant 3. Αλλά τότε c! = (a! - 1)b! - a! \geqslant 5b! - a! > b!. Αν b > a τότε θα είχαμε (a+1)!|(a!b! - b! - c!) και άρα (a+1)!|a!, άτοπο. Άρα πρέπει b=a και άρα c! = (a! - 2)a!. Η εξίσωση έχει την προφανή λύση a=3,c=4. Ισχυρίζομαι ότι δεν έχει άλλα. Πράγματι αν είχε άλλη τότε θα είχαμε (a+1)(a+2) \cdots c = a! - 2. Όμως a! - 2 \equiv 1 \bmod 3 και άρα πρέπει c = a+1 ή c = a+2 αλλιώς θα είχαμε (a+1)(a+2) \cdots c \equiv 0 \bmod 3 και άρα θα είχαμε a! = a+3 ή a! = a^2 + 3a + 4. Όμως a! \geqslant a(a-1)(a-2)! \geqslant 6a^2 - 6a > a^2 + 3a + 4 για a \geqslant 5, άτοπο. Επίσης για a=4 δεν έχουμε λύση και άρα ο ισχυρισμός είναι ορθός.

Επομένως η μοναδική λύση είναι η (3,3,4)

(ii) Αυτό είναι πιο εύκολο. Χωρίς βλάβη της γενικότητας έχουμε a \leqslant b και άρα a! | a! + b! - a!b!, δηλαδή a! | 2^c. Αυτό όμως μπορεί να ισχύει μόνο αν a \leqslant 2. Για a=0,1 η εξίσωση είναι αδύνατη ενώ για a=2 έχουμε b! = 2^c +2. Για b \geqslant 4 το αριστερό μέλος ισούται με 0 \bmod 4 ενώ το δεξί με 2 \bmod 4 αφού (για b \geqslant 4) πρέπει c \geqslant 2. Για b < 4 λύση έχουμε μόνο αν b = 3 και άρα c=2. Επομένως οι μοναδικές λύσεις είναι οι (2,3,2) και (3,2,2).

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Τετ Ιούλ 20, 2011 6:11 pm
από Demetres
nickthegreek έγραψε:
22

Να βρεθούν όλες οι συναρτήσεις f:Z \rightarrow Z τέτοιες ώστε f(0)=1 και

f(f(n))=f(f(n+2)+2)=n,\forall n \in Z
Ισχυρίζομαι ότι η μοναδική συνάρτηση που ικανοποιεί τις συνθήκες είναι η f(n) = 1 - n. Είναι εύκολο να ελέγξουμε ότι η f ικανοποιεί τις συνθήκες. Θα δείξουμε επαγωγικά ότι δεν υπάρχει άλλη τέτοια συνάρτηση.

Ποιο συγκεκριμένα αν f:\mathbb{Z} \rightarrow \mathbb{Z} ικανοποιεί f(0)=1 και f(f(n))=f(f(n+2)+2)=n,\forall n \in \mathbb{Z} τότε ισχυρίζομαι ότι για κάθε n \in \mathbb{N}_0 ισχύει ότι f(n) = 1-n και f(1-n) = n.

Πράγματι για n=0, το f(0) = 1 είναι δεδομένο ενώ το f(1) = 0 έπεται από το f(1) = f(f(0)) = 0. Η περίπτωση n=1 είναι ακριβώς η ίδια με την περίπτωση n=0. Έστω k \geqslant 1. Υποθέτουμε ότι έχουμε αποδείξει την πρόταση για όλα τα n \leqslant k. Τότε \displaystyle{ f(k+1) = f((k-1) + 2) = f(f(1 - (k-1)) + 2) = f(f(2-k) + 2) = -k} και f(1 - (k+1)) = f(-k) = f(f(k+1)) = k+1. Επομένως η πρόταση ισχύει και για n = k+1 και άρα από την αρχή της μαθηματικής επαγωγής ισχύει για όλα τα n.


Έχουν μείνει οι 13,19,26,58,63,65.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Πέμ Ιούλ 21, 2011 2:16 pm
από Nick1990
socrates έγραψε:65.
Να προσδιορίσετε όλους τους θετικούς ακέραιους n τέτοιους ώστε

\bullet \  n^{2}=(a+1)^{3}-a^{3} , για κάποιο ακέραιο a και

\bullet ο αριθμός 2n+119 είναι τέλειο τετράγωνο ακεραίου.
Ας το δούμε κι αυτό:

Ισοδύναμα η πρώτη σχέση δίνει:
(2n)^2 - 3(2a+1)^2 = 1
Ενώ η δεύτερη:
2n = k^2 - 119
Άρα
(k^2 - 119)^2 = 3(2a+1)^2 + 1 \Leftrightarrow (k^2 - 120)(k^2 - 118) = 3(2a+1)^2
Εύκολα όμως ο k πρέπει να είναι περιττός, οπότε είναι εύκολο να δούμε ότι οι αριθμοί στις παρενθέσεις του πρώτου μέλους της παραπάνω πρέπει να είναι σχετικά πρώτοι.
Ο 3 ως πρώτος πρέπει να διαιρεί μια εκ των δύο παρενθέσεων στο 1ο μέλος, οπότε η θα διαιρεί την πρώτη παρένθεση και θα έχουμε:
(\frac{k^2 - 120}{3}, k^2-118) = 1, (\frac{k^2 - 120}{3}) \times (k^2-118) = (2a+1)^2
η θα διαιρεί τη δεύτερη παρένθεση και θα έχουμε:
(\frac{k^2 - 118}{3}, k^2-120) = 1, (\frac{k^2 - 118}{3}) \times (k^2-120) = (2a+1)^2
Όμως δύο σχετικά πρώτοι αριθμοί έχουν γινόμενο τέλειο τετράγωνο αν και μονο αν είναι και οι δύο τέλεια τετράγωνα, άρα η πρώτη περίπτωση δίνει:
k^2-118 = (2s+1)^2, s \in N \Rightarrow (k - 2s - 1)(k + 2s + 1) = 118 = 2 \times 59
που είναι αδύνατη αφού το 1ο μέλος διαιρείτε με 4, ενώ η δεύτερη περίπτωση δίνει:
k^2-120 = (2s+1)^2, s \in N \Rightarrow (k - 2s - 1)(k + 2s + 1) = 120 = 3 \times 5 \times 8
που λύνεται κατα τα γνωστά και δίνει τις λύσεις:
(k, 2s+1) \in \{(13,7), (11,1), (31,29), (17,13)\}
Ελέγχοντας την άλλη σχέση που πρέπει να ικανοποιείται (k^2 - 118 = 3(2d+1)^2, d \in N) βλέπουμε ότι η μόνη λύση που μας κάνει είναι η (11,1)
Για k=11 στην αρχική βρήσκουμε n=1 και μετά εύκολα a=0 η a=-1, οπότε προκείπτει λύση.
Άρα το πρόβλημα έχει μοναδική λύση:
(k,n) = (11,1) με a=0 ή a=-1.



ΥΓ: Η σχέση (2n)^2 - 3(2a+1)^2 = 1 που είναι η πρώτη που βρήκαμε, είναι εξίσωση Pell και στην αρχή πίστευα ότι αυτό θα οδηγήσει στη λύση, όμως τελικά μάλλον το πρόβλημα δεν μπορεί να λυθεί έτσι. Αν κάποιος έχει λύση που χρησημοποιεί το ότι η παραπάνω εξίσωση είναι εξίσωση Pell, αν μπορεί ας την ανεβάσει για λόγους πληρότητας.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Πέμ Ιούλ 21, 2011 6:54 pm
από Demetres
Nick1990 έγραψε: ΥΓ: Η σχέση (2n)^2 - 3(2a+1)^2 = 1 που είναι η πρώτη που βρήκαμε, είναι εξίσωση Pell και στην αρχή πίστευα ότι αυτό θα οδηγήσει στη λύση, όμως τελικά μάλλον το πρόβλημα δεν μπορεί να λυθεί έτσι. Αν κάποιος έχει λύση που χρησημοποιεί το ότι η παραπάνω εξίσωση είναι εξίσωση Pell, αν μπορεί ας την ανεβάσει για λόγους πληρότητας.
Ενδιαφέρον. Δεν έχω λύση μέχρι στιγμής. Αν (x_k) η ακολουθία που ορίζεται ως x_{k+2} = 14x_{k+1} - x_k με x_0 = x_1 = 2 μπορώ να δείξω μέσω της Pell ότι το 2n πρέπει να είναι όρος της ακολουθίας. (Και αντιστρόφως για κάθε όρο x_k της ακολουθίας υπάρχει a_k ώστε x_k^2 - 3(2a_k +1)^2 = 1.)

Μένει λοιπόν να δειχθεί ότι αν το x_k + 119 είναι τέλειο τετράγωνο τότε k=0 ή k=1. Με μερικές μικρές ισοτιμίες που έλεγξα δεν βλέπω κάτι. Το έγραψα μήπως μπορεί κάποιος να το συνεχίσει. Αν δοθεί λύση στο τελευταίο θα βάλω και την απόδειξη του πιο πάνω ισχυρισμού για να έχουμε και μια ολοκληρωμένη δεύτερη λύση.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Πέμ Ιούλ 21, 2011 7:53 pm
από Nick1990
Demetres έγραψε:
Nick1990 έγραψε: ΥΓ: Η σχέση (2n)^2 - 3(2a+1)^2 = 1 που είναι η πρώτη που βρήκαμε, είναι εξίσωση Pell και στην αρχή πίστευα ότι αυτό θα οδηγήσει στη λύση, όμως τελικά μάλλον το πρόβλημα δεν μπορεί να λυθεί έτσι. Αν κάποιος έχει λύση που χρησημοποιεί το ότι η παραπάνω εξίσωση είναι εξίσωση Pell, αν μπορεί ας την ανεβάσει για λόγους πληρότητας.
Ενδιαφέρον. Δεν έχω λύση μέχρι στιγμής. Αν (x_k) η ακολουθία που ορίζεται ως x_{k+2} = 14x_{k+1} - x_k με x_0 = x_1 = 2 μπορώ να δείξω μέσω της Pell ότι το 2n πρέπει να είναι όρος της ακολουθίας. (Και αντιστρόφως για κάθε όρο x_k της ακολουθίας υπάρχει a_k ώστε x_k^2 - 3(2a_k +1)^2 = 1.)

Μένει λοιπόν να δειχθεί ότι αν το x_k + 119 είναι τέλειο τετράγωνο τότε k=0 ή k=1. Με μερικές μικρές ισοτιμίες που έλεγξα δεν βλέπω κάτι. Το έγραψα μήπως μπορεί κάποιος να το συνεχίσει. Αν δοθεί λύση στο τελευταίο θα βάλω και την απόδειξη του πιο πάνω ισχυρισμού για να έχουμε και μια ολοκληρωμένη δεύτερη λύση.

Δημήτρη κι εγώ έτσι το σκέφτηκα αρχικά. Όμως είδα ότι δεν μπορούσα να το τελειώσω έτσι και τελικά βρήκα λύση αξιοποιόντας διαφορετικά τη συγκεκριμένη σχέση.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Κυρ Ιούλ 31, 2011 5:49 pm
από socrates
Επίσης,
matha έγραψε: C-S 3) και \displaystyle{xyz\geq 10+6\sqrt{3}}, τότε

\displaystyle{\frac{y}{x+y^3+z^2}+\frac{z}{y+z^3+x^2}+\frac{x}{z+x^3+y^2}\leq \frac{1}{2}}

Crux, Problem 3466
viewtopic.php?f=111&t=13252
socrates έγραψε:65.
Να προσδιορίσετε όλους τους θετικούς ακέραιους n τέτοιους ώστε

\bullet \  n^{2}=(a+1)^{3}-a^{3} , για κάποιο ακέραιο a και

\bullet ο αριθμός 2n+119 είναι τέλειο τετράγωνο ακεραίου.
http://www.artofproblemsolving.com/Foru ... 7&t=420591
http://www.artofproblemsolving.com/Foru ... 6&t=412951


67.
Αν \tau(n) το πλήθος και \sigma(n) το άθροισμα των διαιρετών του θετικού ακεραίου n,

να δείξετε ότι \displaystyle \sqrt{n}\leq \frac{\sigma(n)}{\tau(n)}\leq \frac{n+1}{2}.

Πότε ισχύει καθεμιά ισότητα;

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Δευ Αύγ 01, 2011 12:41 pm
από stavros11
socrates έγραψε:67.
Αν \tau(n) το πλήθος και \sigma(n) το άθροισμα των διαιρετών του θετικού ακεραίου n,

να δείξετε ότι \displaystyle \sqrt{n}\leq \frac{\sigma(n)}{\tau(n)}\leq \frac{n+1}{2}.

Πότε ισχύει καθεμιά ισότητα;
Μία προσπάθεια:

Αρχίζουμε με την αριστερή
Για \displaystyle{\tau (n)=1}, πρέπει \displaystyle{n=1} και τότε ισχύει ισότητα.
Για \displaystyle{\tau (n)>1}:

Όταν ο \displaystyle{n} δεν είναι τέλειο τετράγωνο ακεραίου, ο \displaystyle{\tau (n)} είναι άρτιος:
Έστω \displaystyle{1=d_0<d_1<d_2<...<d_{\tau (n)}=n} οι διαιρέτες του \displaystyle{n}.
Για κάθε \displaystyle{i \in \mathbb{N}} ισχύει \displaystyle{d_{i}d_{\tau (n) -i}=n}

Από AM-GM έχουμε:
\displaystyle{\frac{\sigma (n)}{\tau (n)}=\frac{1}{\tau (n)}\sum_{i=0}^{\tau (n)}{d_i}\geq \sqrt[\tau (n)]{\prod_{i=0}^{\tau (n)}{d_i}}=\sqrt[\tau (n)]{\prod_{i=0}^{\tau (n)/2}{d_{i}d_{\tau (n)-i}}}=\sqrt[\tau (n)]{n^{\frac{\tau (n)}{2}}}=\sqrt{n}}

Για να ισχύει ισότητα στην AM-GM πρέπει οι διαιρέτες να είναι ίσοι, που είναι άτοπο. Άρα ισότητα ισχύει μόνο για \displaystyle{n=1}.

Στην περίπτωση που ο \displaystyle{n} είναι τέλειο τετράγωνο ακεραίου, έστω \displaystyle{n=d_j^2}, ακολουθούμε τον ίδιο τρόπο, δηλαδή από AM-GM:
\displaystyle{\frac{\sigma (n)}{\tau (n)}=\frac{1}{\tau (n)}\sum_{i=0}^{\tau (n)}{d_i}\geq \sqrt[\tau (n)]{\prod_{i=0}^{\tau (n)}{d_i}}=\sqrt[\tau (n)]{n^{\frac{\tau (n)-1}{2}}d_j}=\sqrt[\tau (n)]{n^{\frac{\tau (n)-1}{2}}n^{\frac{1}{2}}}=\sqrt[\tau (n)]{n^{\frac{\tau (n)}{2}}}=\sqrt{n}}

Για την δεξιά:
Για \displaystyle{n=1} ισχύει ισότητα.
Για \displaystyle{n>1}:
Και πάλι στην περίπτωση που ο \displaystyle{n} δεν είναι τέλειο τετράγωνο ακεραίου, άρα \displaystyle{\tau (n)} άρτιος:

\displaystyle{\frac{\sigma (n)}{\tau (n)}\leq \frac{n+1}{2}\Leftrightarrow (n+1)\tau (n)\geq 2\sigma (n)\Leftrightarrow (n+1)\frac{\tau (n)}{\sigma (n)}\geq 2\Leftrightarrow \frac{n\tau (n)}{\sigma (n)}+\frac{\tau (n)}{\sigma (n)}\geq 2 \; \; (1)}

Όμοια με την απόδειξη της αριστερής θεωρούμε \displaystyle{1=d_0<d_1<d_2<...<d_{\tau (n)}=n} τους διαιρέτες του \displaystyle{n} με \displaystyle{d_{i}d_{\tau (n) -i}=n \; \; \forall \; \;i \in \mathbb{N}}.
Τότε ισχύει \displaystyle{n\tau (n)=n+n+n+...+n=d_0d_{\tau (n)}+d_1d_{\tau (n)-1}+..+d_kd_{\tau (n)-k}+d_0d_{\tau (n)}+d_1d_{\tau (n)-1}+..+d_kd_{\tau (n)-k}=2\sum_{i=0}^{\tau (n)/2}{d_id_{\tau (n)-i}}}

Θα συγκρίνουμε το άθροισμα και το γινόμενο δύο θετικών ακεραίων \displaystyle{x,y}:
\displaystyle{xy\geq x+y\Leftrightarrow  xy-x-y+1\geq 1\Leftrightarrow x(y-1)-(y-1)\geq 1\Leftrightarrow (x-1)(y-1)\geq 1}.
Άρα παρατηρούμε ότι αν οι αριθμοί είναι μεγαλύτεροι του \displaystyle{2} ή ο ένας ίσος με \displaystyle{2} και ο άλλος μεγαλύτερος, τότε το γινόμενο τους είναι μεγαλύτερο από το άθροισμα. Αν και οι δύο είναι ίσοι με \displaystyle{2}, τότε το γινόμενο είναι ίσο με το άθροισμα, ενώ αν έστω κι ένας ένας είναι ίσος με \displaystyle{1}, τότε το άθροισμα είναι μεγαλύτερο.
Για τους διαιρέτες, όλοι εκτός από τον πρώτο είναι μεγαλύτεροι ή ίσοι του \displaystyle{2}, άρα το γινόμενο τους είναι μεγαλύτερο από το άθροισμα.
Άρα ισχύει:
\displaystyle{n\tau (n)=2\sum_{i=0}^{\tau (n)/2}{d_id_{\tau (n)-i}}=2d_0d_{\tau (n)}+2\sum_{i=1}^{\tau (n)/2}{d_id_{\tau (n)-i}}\geq2d_0d_{\tau (n)}+2\sum_{i=1}^{\tau (n)/2}{(d_i+d_{\tau (n)-i})}=}
\displaystyle{=2d_0d_{\tau (n)}+2\sum_{i=0}^{\tau (n)/2}{(d_i+d_{\tau (n)-i})}-2d_0-2d_{\tau (n)}=2n+2\sigma (n)-2-2n=2\sigma (n)-2}
Άρα:
\displaystyle{\frac{n\tau (n)}{\sigma (n)}\geq \frac{2\sigma (n)-2}{\sigma (n)}=2-\frac{2}{\sigma (n)}}.

Τελικά έχουμε:
\displaystyle{ \frac{n\tau (n)}{\sigma (n)}+\frac{\tau (n)}{\sigma (n)}\geq 2-\frac{2}{\sigma (n)}+\frac{\tau (n)}{\sigma (n)}=2+\frac{\tau (n)-2}{\sigma (n)}}.

Οπότε αντί για την \displaystyle{(1)} μπορεί να αποδειχτεί η ισχυρότερη:
\displaystyle{2+\frac{\tau (n)-2}{\sigma (n)}\geq 2\Leftrightarrow \frac{\tau (n)-2}{\sigma (n)}\geq 0\Leftrightarrow \tau (n)\geq 2}, που ισχύει αφού \displaystyle{n>1}.

Η ισότητα ισχύει αν \displaystyle{n=1}, ή \displaystyle{n} πρώτος.

Στην περίπτωση που ο \displaystyle{n} είναι τέλειο τετράγωνο ακεραίου (έστω \displaystyle{n=d_j^2}), έχουμε:
\displaystyle{d_j \geq 2 \Rightarrow d_j^2 \geq 2d_j}. Άρα όμοια με παραπάνω έχουμε:

\displaystyle{n\tau(n)=2(d_0d_{\tau (n)}+d_1d_{\tau (n)-1}+...+d_{j-1}d_{\tau (n)-j+1}+d_{j+1}d_{\tau (n)-j-1}+...+d_kd_{\tau (n)-k}+d_j^2\geq}
\displaystyle{\geq 2d_0d_{\tau (n)}+2(d_0+d_1+d_2+...+d_{j-1}+d_{j+1}+...+d_{\tau (n)})+2d_j-2(d_0+d_{\tau (n)})=2n+2\sigma (n)-2n-2=2\sigma-2} και συνεχίζουμε όμοια με την περίπτωση που ο \displaystyle{n} δεν είναι τέλειο τετράγωνο.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Τετ Αύγ 24, 2011 4:31 pm
από stavros11
Με βάση ένα ποστ του κ. Δημήτρη λίγο πιο πάνω αναπάντητη έχει μείνει η άσκηση 13.
socrates έγραψε:13.
Να βρείτε όλα τα ζεύγη θετικών ακεραίων (a,b) τέτοια ώστε ο αριθμός \displaystyle {\frac{a^3+1}{2ab^2+1}} να είναι ακέραιος.
Θέλουμε να υπάρχει \displaystyle{k\in \mathbb{N}^*}, ώστε να ισχύει: \displaystyle{\frac{a^3+1}{2ab^2+1}=k}.

Κάνοντας μερικές πράξεις έχουμε:
\displaystyle{a^3+1=2ab^2k+k\Rightarrow a^3-k+1=2ab^2k}.

Προφανώς \displaystyle{a|2ab^2k\Rightarrow 2ab^2k\equiv 0\mod a}. Άρα από την παραπάνω ισότητα έχουμε \displaystyle{a^3-k+1\equiv 0\mod a} και αφού \displaystyle{a^3\equiv 0\mod a}, τελικά παίρνουμε \displaystyle{1-k\equiv 0\mod a\Rightarrow k\equiv 1\mod a}.

Άρα ο \displaystyle{k} θα έχει την μορφή \displaystyle{k=ma+1} για κάποιο \displaystyle{m \in \mathbb{N}}.
Για \displaystyle{m=0}, παίρνουμε \displaystyle{k=1}. Άρα:
\displaystyle{\frac{a^3+1}{2ab^2+1}=1\Rightarrow a^3+1=2ab^2+1\Rightarrow a^3=2ab^2\Rightarrow a^2=2b^2\Rightarrow (\frac{a}{b})^2=2\Rightarrow \frac{a}{b}=\sqrt{2}} που είναι άτοπο, αφού το ένα μέλος είναι ρητός ενώ το άλλο άρρητος. Άρα \displaystyle{m \in \mathbb{N}^*}.

Αντικαθιστώντας το \displaystyle{k} στην ισότητα έχουμε: \displaystyle{a^3-ma-1+1=2ab^2(ma+1)\Rightarrow a^3-ma=2ab^2(ma+1)\Rightarrow a^2-m=2b^2(ma+1)\Rightarrow a^2-2b^2ma-(2b^2+m)=0}.

Θεωρώντας το παραπάνω τριώνυμο ως προς \displaystyle{a} ισχύει:
\displaystyle{\Delta =4m^2b^4+8b^2+4m=4(m^2b^4+2b^2+m)}

\displaystyle{a=\frac{2mb^2\pm 2\sqrt{m^2b^4+2b^2+m}}{2}=mb^2\pm \sqrt{m^2b^4+2b^2+m}}

Άρα η παράσταση \displaystyle{A=m^2b^4+2b^2+m} πρέπει να είναι τέλειο τετράγωνο ακεραίου.
Έστω \displaystyle{m\geq 2}:
Προφανώς ισχύει \displaystyle{(mb^2)^2<m^2b^4+2b^2+m}.
Ακόμα ισχύει \displaystyle{m^2b^4+2b^2+m<m^2b^4+2mb^2+1}, αφού είναι ισοδύναμη με την \displaystyle{2(m-1)b^2>m-1\Leftrightarrow b^2>\frac{1}{2}} (αφού \displaystyle{m\geq 2>1\Rightarrow m-1>0}).

Οπότε έχουμε \displaystyle{(mb^2)^2<A<m^2b^4+2mb^2+1\Rightarrow (mb^2)^2<A<(mb^2+1)^2}, άρα για \displaystyle{m\geq 2}, η \displaystyle{A} δεν είναι τέλειο τετράγωνο, αφού βρίσκεται ανάμεσα σε τέλεια τετράγωνα διαδοχικών ακεραίων.

Μένει η περίπτωση \displaystyle{m=1}, για την οποία \displaystyle{A=(b^2+1)^2}.
Άρα \displaystyle{a=b^2\pm(b^2+1)}. Αφού \displaystyle{a>0}, δεκτή είναι μόνο η λύση \displaystyle{a=2b^2+1}.

Άρα υπάρχουν άπειρα ζευγάρια για τα οποία ο αριθμός \displaystyle{\frac{a^3+1}{2ab^2+1}} είναι ακέραιος, αρκεί να ισχύει \displaystyle{a=2b^2+1}.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Πέμ Αύγ 25, 2011 12:18 am
από Demetres
socrates έγραψε:63.
Αν n>3, δείξτε ότι ο αριθμός 4^n+1 έχει πρώτο διαιρέτη μεγαλύτερο του 20.
Αν 4^n + 1 \equiv 0 \bmod p, όπου p πρώτος, τότε το -1 είναι τέλειο τετράγωνο \bmod p και άρα (αφού ο p περιττός) πρέπει p \equiv 1 \bmod 4.

Άρα οι μόνοι πιθανοί πρώτοι διαιρέτες του 4^n + 1 που είναι μικρότεροι του 20 είναι οι 5,13 και 17.

Επίσης αν 17|(4^n + 1) τότε πρέπει ο n να είναι άρτιος ενώ αν 5|(4^n+1) ή 13|(4^n+1) τότε πρέπει ο n να είναι περιττός. Επομένως μένει να δειχθεί ότι οι εξισώσεις

(α) 4^n+1 = 5^m
(β) 4^n+1 = 13^m
(γ) 4^n+1 = 17^m
(δ) 4^n+1 = 5^m13^{\ell}

είναι αδύνατες για n > 3.

Οι (α),(β) και (γ) είναι αδύνατες από την εικασία του Catalan (θεώρημα Mihailescu). Μπορούμε να το αποδείξουμε και πιο στοιχειωδώς. Η (β) είναι αδύνατη \bmod 3. Για τις (α) και (γ) αν δουλέψουμε \bmod 3 βρίσκουμε ότι ο m πρέπει να είναι περιττός ενώ αν δουλέψουμε \bmod 8 βρίσκουμε ότι ο m πρέπει να είναι άρτιος.

Μένει να δείξουμε ότι η (δ) είναι αδύνατη. Θα χρησιμοποιήσω την τεχνική του "lifting the exponent". (Την έχουμε δει π.χ. εδώ.) Όταν έλυσα την άσκηση πριν αρκετό καιρό είχα βρει και μια απόδειξη μόνο με modulo αλλά δυστυχώς τώρα μου διαφεύγει. :(

Επειδή 13|(4^n+1) πρέπει να έχουμε n \equiv 3 \bmod 6, έστω n = 3k με k περιττό. (Επειδή n > 3, πρέπει επίσης k > 1.) Τότε 64^k - (-1)^k = 5^m13^{\ell}. Από το lifting the exponent, πρέπει 5^{m-1}|k και 13^{\ell - 1}|k. Αλλά τότε \displaystyle{ 5^m13^{\ell} = 64^k + 1 > 64^{5^{m-1}13^{\ell-1}} = 2^{5^{m}13^{\ell-1}} > 5^m 13^{\ell}}, άτοπο. Στην τελευταία ανισότητα χρησιμοποιήσαμε ότι 2^n > 13n το οποίο ισχύει (εύκολα με επαγωγή) για n \geqslant 7.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Παρ Σεπ 30, 2011 7:13 pm
από socrates
68.
Έστω \Box : \mathbb{Z}_{\geq 0}\times \mathbb{Z}_{\geq 0}\to \mathbb{Z}_{\geq 0} μια πράξη που ικανοποιεί τα ακόλουθα αξιώματα:

(α) (x + 1)\Box 0 = (0 \Box x) + 1

(β) 0 \Box (y + 1) = (y \Box 0) + 1

(γ) (x + 1)\Box (y + 1) = (x \Box y) + 1.

Αν 1100 \Box  450 = 2000 να βρείτε το 1723 \Box 3421 και, αν θέλετε, την \Box.

69.
Σε ένα τουρνουά συμμετέχουν N ομάδες. Κάθε ομάδα έπαιξε με κάθε άλλη ακριβώς μία φορά.
Σε κάθε αγώνα ο νικητής παίρνει 1 βαθμό , ο ηττημένος 0 βαθμούς ενώ δεν υπάρχουν ισοπαλίες.

Στο τέλος του τουρνουά παρατηρήθηκε ότι ανάμεσα σε οποιεσδήποτε 4 ομάδες, υπήρχαν 2 με τον ίδιο αριθμό βαθμών στα μεταξύ τους παιχνίδια.
Να βρεθεί η μέγιστη τιμή του N.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Κυρ Οκτ 02, 2011 8:54 pm
από Φωτεινή
socrates έγραψε:68.
Έστω \Box : \mathbb{Z}_{\geq 0}\times \mathbb{Z}_{\geq 0}\to \mathbb{Z}_{\geq 0} μια πράξη που ικανοποιεί τα ακόλουθα αξιώματα:

(α) (x + 1)\Box 0 = (0 \Box x) + 1

(β) 0 \Box (y + 1) = (y \Box 0) + 1

(γ) (x + 1)\Box (y + 1) = (x \Box y) + 1.

Αν 1100 \Box  450 = 2000 να βρείτε το 1723 \Box 3421 και, αν θέλετε, την \Box.
θα δείξουμε ότι x\Box 0= 0\Box x

x=0 :~ a)\Rightarrow 1\Box 0=0\Box 0+1

y=0 :~ b)\Rightarrow 0\Box 1=0\Box 0+1

άρα 1\Box 0= 0\Box 1

έστω ισχύει για κάποιο θετικό x ,κοιτάζουμε για τον επόμενο

(x+1)\Box 0=0\Box x+1=x\Box 0+1=0 \Box (x+1)

άρα x\Box 0= 0\Box x
-----------------------------------------
επίσης επαγωγικά αποδεικνύουμε (από την α)) ότι :x\Box  0=0\Box 0+x
-------------------------------------------------

αν ~~ (y<x)

x\Box y=((x-1)+1)\Box((y-1)+1)=(x-1)\Box(y-1)+1=(x-2)\Box(y-2)+2=\dots =(x-y)\Box 0+y

έχουμε λοιπόν x\Box y=0\Box 0+x

1100\Box 450=0 \Box 0+1100\rightarrow 0\Box 0=900\longrightarrow x\Box y=900+x
----------------------------
y\Box x=((y-1)+1)\Box((x-1)+1)=(y-1)\Box(x-1)+1=(y-2)\Box(x-2)+2=\dots =(y-y)\Box (x-y)+y=0\Box (x-y)+y=0\Box 0+x

y\Box x=0\Box 0+x\rightarrow y\Box x=900+x

άρα \boxed{x\Box y=900+x,~~ x>y}

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Κυρ Οκτ 02, 2011 9:49 pm
από Demetres
socrates έγραψε: 69.
Σε ένα τουρνουά συμμετέχουν N ομάδες. Κάθε ομάδα έπαιξε με κάθε άλλη ακριβώς μία φορά.
Σε κάθε αγώνα ο νικητής παίρνει 1 βαθμό , ο ηττημένος 0 βαθμούς ενώ δεν υπάρχουν ισοπαλίες.

Στο τέλος του τουρνουά παρατηρήθηκε ότι ανάμεσα σε οποιεσδήποτε 4 ομάδες, υπήρχαν 2 με τον ίδιο αριθμό βαθμών στα μεταξύ τους παιχνίδια.
Να βρεθεί η μέγιστη τιμή του N.
Η μέγιστη τιμή είναι 7. Πράγματι αν N = 8, έγιναν συνολικά 28 αγώνες και άρα υπάρχει κάποιος, έστω ο Α με τουλάχιστον 4 νίκες. Παίρνουμε 4 οποιαδήποτε άτομα που ηττήθηκαν από τον Α. Μεταξύ τους έγιναν 6 αγώνες, άρα τουλάχιστον ένας από αυτούς, έστω ο Β έκανε τουλάχιστον δύο νίκες. Αν οι Γ,Δ ηττήθηκαν και από τον Α και από τον Β, τότε στην τετράδα Α,Β,Γ,Δ έχουν όλοι διαφορετικούς βαθμούς (στα μεταξύ τους παιγνίδια.)

Για N = 7 αν συμβολίζουμε με 1,2,3,4,5,6,7 τις ομάδες, έχουμε την εξής κατασκεύη
Ο 1 κερδίζει τους 2,3,4
Ο 2 κερδίζει τους 3,5,6
Ο 3 κερδίζει τους 4,5,7
Ο 4 κερδίζει τους 2,6,7
Ο 5 κερδίζει τους 1,4,6
Ο 6 κερδίζει τους 1,3,7
Ο 7 κερδίζει τους 1,2,5

Παρατηρούμε ότι αυτή η κατασκευή είναι πιθανή (δεν γίνεται π.χ. ο i να κερδίζει τον j και ο j τον i.) Επίσης, αν υπάρχουν τέσσερις ομάδες που έχουν όλες διαφορετικούς βαθμούς στα μεταξύ τους παιγνίδια τότε πρέπει μια από αυτές να κερδίζει όλες τις άλλες και άρα οι μόνες πιθανές τετράδες είναι οι
1,2,3,4
2,3,5,6
3,4,5,7
2,4,6,7
1,4,5,6
1,3,6,7
1,2,5,7
Πρέπει όμως στην τετράδα να υπάρχει και μια ομάδα που χάνω από όλες τις υπόλοιπες. Ελέγχοντας τις παραπάνω τετράδες μία προς μία βλέπουμε ότι αυτό είναι αδύνατο. Επομένως η κατασκευή πληρεί τις συνθήκες και άρα N = 7.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Τετ Οκτ 12, 2011 8:36 pm
από socrates
70.
Να βρεθεί η μέγιστη τιμή της πραγματικής σταθερής M έτσι ώστε

\displaystyle{ (a+bc)(b+ac)(c+ab)\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c} \right)\ge(Mabc) }

για όλους τους θετικούς πραγματικούς αριθμούς a,b,c για τους οποίους a+b+c=1.

71.
Για ποιους ακεραίους x είναι ο αριθμός x^{2009}+x^{2008}+x^{2}+x+1 πρώτος;


72.
α) Στο επίπεδο δίνονται 100 σημεία.
Να δείξετε ότι υπάρχει ευθεία που αφήνει σε κάθε ημιεπίπεδο που ορίζει ακριβώς 50 από αυτά τα σημεία.

β) Στο επίπεδο δίνονται 2010 σημεία.
Να δείξετε ότι υπάρχει κύκλος που περιέχει στο εσωτερικό του ακριβώς 1005 από αυτά τα σημεία και τα υπόλοιπα 1005 σημεία βρίσκονται στο εξωτερικό του.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Τετ Οκτ 12, 2011 8:59 pm
από matha
socrates έγραψε:70.
Να βρεθεί η μέγιστη τιμή της πραγματικής σταθερής M έτσι ώστε

\displaystyle{ (a+bc)(b+ac)(c+ab)\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c} \right)\ge(Mabc) }

για όλους τους θετικούς πραγματικούς αριθμούς a,b,c για τους οποίους a+b+c=1.
Θέτουμε στην ανισότητα \displaystyle{a=b=c=\frac{1}{3}} και προκύπτει \displaystyle{M\leq \frac{64}{3}.}
Για να ολοκληρωθεί η απόδειξη, αποδεικνύουμε την ανισότητα για \displaystyle{M=\frac{64}{3}.}

Επειδή \displaystyle{a+b+c=1,} είναι \displaystyle{a+bc=(a+b)(a+c),b+ca=(b+a)(b+c),c+ab=(c+a)(c+b)} και η προς απόδειξη γράφεται σε ομογενή μορφή ως

\displaystyle{\Big[(a+b)(b+c)(c+a)\Big]^2\Big(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\Big)\geq \frac{64}{3}(a+b+c)^2abc}.

Όπως έχουμε δει και άλλες φορές (π.χ. εδώ), ισχύει

\displaystyle{(a+b)(b+c)(c+a)\geq \frac{8}{9}(a+b+c)(ab+bc+ca).}

Επομένως, είναι τελικά αρκετό να αποδείξουμε, ότι

\displaystyle{(ab+bc+ca)^3\geq 27(abc)^2,} η οποία ισχύει από την ανισότητα ΑΜ-ΓΜ.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Παρ Οκτ 14, 2011 12:24 am
από Demetres
socrates έγραψε: 72.
α) Στο επίπεδο δίνονται 100 σημεία.
Να δείξετε ότι υπάρχει ευθεία που αφήνει σε κάθε ημιεπίπεδο που ορίζει ακριβώς 50 από αυτά τα σημεία.

β) Στο επίπεδο δίνονται 2010 σημεία.
Να δείξετε ότι υπάρχει κύκλος που περιέχει στο εσωτερικό του ακριβώς 1005 από αυτά τα σημεία και τα υπόλοιπα 1005 σημεία βρίσκονται στο εξωτερικό του.
(α) Κοιτάμε όλες τις ευθείες οι οποίες περιέχουν τουλάχιστον δύο από αυτά τα σημεία. Υπάρχει πεπερασμένος αριθμός τέτοιων ευθειών και επομένως μπορούμε να πάρουμε μια ευθεία η οποία δεν είναι παράλληλη με καμία από αυτές. Περιστρέφοντας το επίπεδο μπορούμε χωρίς βλάβη να θεωρήσουμε πως αυτή η ευθεία είναι ο άξονας των x και άρα ότι κάθε δύο από τα δοσμένα σημεία έχουν διαφορετική τεταγμένη. Έστω ότι έχουν τεταγμένες y_1 < y_2 < \cdots < y_{100}. Βλέπουμε τώρα ότι η ευθεία y = (y_{50} + y_{51})/2 έχει την ζητούμενη ιδιότητα.

(β) Με παρόμοιο σκεπτικό βρίσκουμε ένα σημείο P στο επίπεδο ώστε κάθε δυο από τα δοσμένα σημεία να έχουν διαφορετική απόσταση από αυτό. Αυτό είναι δυνατό αφού το σύνολο των σημείων που ισαπέχουν από δύο από τα δοσμένα σημεία είναι ένωση πεπερασμένου αριθμού ευθειών (των μεσοκαθέτων των ευθυγράμμων τμημάτων που ενώνουν τα σημεία) και άρα δεν μπορούν να καλύπτουν όλο το επίπεδο. (*) Υποθέτουμε τώρα ότι τα σημεία έχουν αποστάσεις r_1 < r_2 < \cdots < r_{1000} από το P και βλέπουμε ότι ο κύκλος με κέντρο το P και ακτίνα (r_{500} + r_{501})/2 έχει την ζητούμενη ιδιότητα.

(*) Ο ισχυρισμός ότι πεπερασμένος αριθμός ευθειών δεν μπορεί να καλύπτει το επίπεδο αν και «προφανές» θέλει απόδειξη. Γνωρίζω μια όμορφη και σύντομη απόδειξη αλλά σας αφήνω να το σκεφτείτε.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Παρ Οκτ 14, 2011 12:35 am
από Demetres
socrates έγραψε: 71.
Για ποιους ακεραίους x είναι ο αριθμός x^{2009}+x^{2008}+x^{2}+x+1 πρώτος;
Ισχυρίζομαι ότι το 1+x+x^2+x^3+x^4 διαιρεί το x^{2009}+x^{2008}+x^{2}+x+1. Αρκεί βέβαια να δείξω ότι το x^5 - 1 διαιρεί το (x-1)(x^{2009}+x^{2008}+x^{2}+x+1) = x^{2010} - x^{2008} + x^{3} - 1. Και πράγματι το x^5 - 1 διαιρεί τόσο το x^{2010}-1 = (x^5)^{402} - 1 όσο και το x^{2008} - x^3 = x^3((x^5)^{401} - 1) άρα και την διαφορά τους που είναι το ζητούμενο.

Επειδή όμως x^{2009} + x^{2008} + x^2 + x + 1 > x^4 + x^3 + x^2 + x + 1 για x > 1, ο αριθμός x^{2009}+x^{2008}+x^{2}+x+1 δεν μπορεί να είναι πρώτος σε αυτήν την περίπτωση. Για x = 1 ο αριθμός είναι όντως πρώτος.

[Μιας και η άσκηση ρωτάει για ακεραίους εύκολα ελέγχουμε ότι για x=0,-1 ο αριθμός δεν είναι πρώτος ενώ για x < -1 ο αριθμός είναι σε απόλυτη τιμή μεγαλύτερος του x^4 + x^3 + x^2 + x + 1 άρα και πάλι δεν είναι πρώτος ακόμη και αν θεωρήσουμε τους αρνητικούς πρώτους σαν πρώτους.]

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Παρ Οκτ 14, 2011 1:11 am
από AlexandrosG
Demetres έγραψε:(*) Ο ισχυρισμός ότι πεπερασμένος αριθμός ευθειών δεν μπορεί να καλύπτει το επίπεδο αν και «προφανές» θέλει απόδειξη. Γνωρίζω μια όμορφη και σύντομη απόδειξη αλλά σας αφήνω να το σκεφτείτε.
Δημήτρη ένα επιχείρημα σαν το παρακάτω είναι εντάξει?

Έστω ότι οι ευθείες είναι \displaystyle{\nu} το πλήθος. Θεωρούμε ένα τυχαίο κύκλο. Είναι γνωστό ότι κύκλος και ευθεία έχουν το πολύ 2 κοινά σημεία. Άρα ο κύκλος έχει με τις ευθείες το πολύ \displaystyle{2\nu} κοινά σημεία. Άρα οι ευθείες δεν καλύπτουν το επίπεδο αφού ο κύκλος έχει άπειρα σημεία.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Παρ Οκτ 14, 2011 1:14 am
από Demetres
AlexandrosG έγραψε: Δημήτρη ένα επιχείρημα σαν το παρακάτω είναι εντάξει?
Βέβαια.

Re: Διαγωνισμός Αρχιμήδης 2011 - Των φρονίμων τα παιδιά...!

Δημοσιεύτηκε: Σάβ Οκτ 29, 2011 7:30 pm
από socrates
73.
Έστω n\geq 4 και οι πραγματικοί αριθμοί x_1,x_2,...,x_n για τους οποίους

x_1+x_2+...+x_n\geq 1 και x_1^2+x_2^2+...+x_n^2\geq 1.

Να δείξετε ότι \displaystyle{\max\{x_1,x_2,...,x_n\}\geq \frac{2}{n}.}


74.
Σε ένα τουρνουά σκάκι συμμετέχουν άνδρες και γυναίκες. Κάθε δύο συμμετέχοντες έπαιξαν μεταξύ τους ακριβώς μία φορά.
Σε περίπτωση νίκης, ο νικητής κερδίζει 1 βαθμό ενώ ο ηττημένος 0 βαθμούς. Σε περίπτωση ισοπαλίας, και οι δύο παίκτες παίρνουν από 0.5 βαθμό.
Παρατηρήθηκε ότι κάθε παίκτης (είτε άνδρας είτε γυναίκα) κέρδισε τον ίδιο αριθμό βαθμών στα παιχνίδια με τους άνδρες και στα παιχνίδια με τις γυναίκες.
Να δείξετε ότι ο συνολικός αριθμός των συμμετεχόντων είναι τέλειο τετράγωνο ακεραίου.


75.
Να βρείτε όλους τους πρώτους p τέτοιους ώστε το άθροισμα όλων των θετικών ακεραίων από το 1 μέχρι τον p να διαιρείται από όλους τους πρώτους που είναι μικρότεροι ή ίσοι του p.