mathematica.gr


https://www.mathematica.gr/forum/

Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2014/15 (ΙΙΦ τάξη 9)

https://www.mathematica.gr/forum/viewtopic.php?t=54916

Σελίδα 1 από 1

Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2014/15 (ΙΙΦ τάξη 9)

Δημοσιεύτηκε: Τετ Ιούλ 13, 2016 11:14 pm
από Al.Koutsouridis
Μαθηματική Ολυμπιάδα Αγίας Πετρούπολης 2014-2015

Θέματα της δεύτερης φάσης (τελικής) για την 9η τάξη. Διάρκεια εξέτασης 3 ώρες. (*)


1. Υπάρχει τριώνυμο f(x) δευτέρου βαθμού με ακέραιους συντελεστές τέτοιο, ώστε f(f(\sqrt{2})) = 0 ;


2. Δίνεται ισοσκελές τραπέζιο ABCD (AD || BC , AD > BC) και σημείο E στον περιγεγραμμένο κύκλο του τέτοιο ώστε BE \perp AD. Να αποδείξετε ότι AE +BC > DE.


3. Τα κελιά ενός τετραγώνου διαστάσεων 2015 \times 2015 χρωματίζονται με τέσσερα χρώματα. Θεωρούμε όλους τους τρόπους τοποθέτησης εσωτερικά αυτού του τετραγώνου σχήματος ταυ (T) των τεσσάρων κελιών (μπορεί και περιστροφές του). Να αποδείξετε ότι το σχήμα περιέχει τέσσερα διαφορετικά χρώματα λιγότερο από το 51% αυτών των περιπτώσεων.


4. Οι θετικοί αριθμοί x,y,z ικανοποιούν την συνθήκη

xy+yz+zx+2xyz =1

να αποδείξετε ότι 4x+y+z \geq 2 .


Καταληκτική αίθουσα (**)


5. Δίνεται κυρτό τετράπλευρο ABCD. Ο περιγεγραμμένος κύκλος του τριγώνου ABC τέμνει τις πλευρές AD και DC στα σημεία P και Q αντίστοιχα. Ο περιγεγραμμένος κύκλος του τριγώνου ADC τέμνει τις πλευρές AB και BC στα σημεία S και R αντίστοιχα. Αν το τετράπλευρο PQRS είναι παραλληλόγραμμο να αποδείξετε ότι και το ABCD θα είναι παραλληλόγραμμο.


6. Στην διαγαλαξιακή αυτοκρατορία υπάρχουν 10^{2015} πλανήτες, οποιοιδήποτε δύο από τους οποίους συνδέονται με μια κοσμική γραμμή διπλής κατεύθυνσης. Αυτές οι συνδέσεις εξυπηρετούνται από 2015 μεταφορικές εταιρείες. Ο αυτοκράτορας θέλει να κλείσει k από αυτές τις εταιρίες έτσι, ώστε, χρησιμοποιώντας τις υπόλοιπες να μπορεί κάποιος να βρει τρόπο να μεταφερθεί από οποιοδήποτε πλανήτη σε κάποιον άλλο. Για ποιο μέγιστο k με σιγουριά μπορεί να επιτευχθεί ένα τέτοιο πλάνο;

7. Ακολουθία φυσικών αριθμών ορίζεται ως εξής: a_{1} =1, a_{2}=2, a_{3}=3, a_{n} = - ο ελάχιστος φυσκός αριθμός, που δεν έχει εμφανιστεί πιο πριν (στην ακολουθία),σχετικά πρώτος με τον a_{n-1} και σχετικά μη πρώτος με τον a_{n-2}. Να αποδείξετε, ότι σε αυτή την ακολουθία εμφανίζονται ακριβώς από μια φορά όλοι οι φυσικοί αριθμοί.




(*) Η τελική φάση της ολυμπιάδας είναι προφορική.
(**) Όσοι έλυσαν τρια από τα τέσσερα αρχικά προβλήματα καλέστηκαν να λύσουν άλλα τρία σε διαφορετική αίθουσα. Ο επιπλέον χρόνος που δίνεται είναι μια ώρα.

Στατιστικά: Στον πρώτο πίνακα αναγράφεται ο αριθμός των λυτών ανά θέμα (πόσοι έλυσαν το πρώτο, δύτερο θέμα κτλ.). Στον δεύτερο πίνακα ο αριθμός των μαθητών ανά πλήθος θεμάτων που έλυσαν(πόσοι έλυσαν ένα, δυο κτλ θέματα).

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{\gr τάξη} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \text{\gr σύνολο} &\text{\gr καταληκτική} \\ \hline 9 & 53 & 11 & 32 & 7 & 0 & 3 & 5 & 97 & 34 \\ \hline \end{tabular}

\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline \text{\gr τάξη} & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 9 & 24 & 20 & 10 & 3 & 1 & 0 & 0 \\ \hline \end{tabular}

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Τετ Ιούλ 13, 2016 11:35 pm
από george visvikis
Al.Koutsouridis έγραψε: 2. Δίνεται ισοσκελές τραπέζιο ABCD (AD || BC , AD > BC) και σημείο E στον περιγεγραμμένο κύκλο του τέτοιο ώστε BE \perp AD. Να αποδείξετε ότι AE +BC > DE.
Πετρούπολη 2015 ΙΙΦ 9_2.png
Πετρούπολη 2015 ΙΙΦ 9_2.png (13.73 KiB) Προβλήθηκε 2998 φορές
Από το E φέρνω παράλληλη στη BC που τέμνει τον κύκλο στο H.Το AEHD είναι ισοσκελές τραπέζιο:

\displaystyle{AE + BC = AE + EH > AH \Leftrightarrow } \boxed{AE+BC>DE}

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Πέμ Ιούλ 14, 2016 12:30 am
από matha
Al.Koutsouridis έγραψε:
4. Οι θετικοί αριθμοί x,y,z ικανοποιούν την συνθήκη

xy+yz+zx+2xyz =1

να αποδείξετε ότι 4x+y+z \geq 2 .
Η ανισότητα είναι αυστηρή, εκτός και αν στην εκφώνηση έλεγε "μη αρνητικοί".

Υπάρχουν θετικοί \displaystyle{a,b,c} ώστε

\displaystyle{x=\frac{a}{b+c},y=\frac{b}{c+a},z=\frac{c}{a+b},} οπότε η αποδεικτέα γράφεται

\displaystyle{\frac{4a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\geq 2.}

Από Cauchy-Schwarz είναι

\displaystyle{\frac{4a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}=\frac{4a^2}{ab+ac}+\frac{b^2}{bc+ab}+\frac{c^2}{ac+bc}\geq \frac{(2a+b+c)^2}{2(ab+bc+ca)}}

οπότε αρκεί να αποδειχθεί ότι

\displaystyle{(2a+b+c)^2\geq 4(ab+bc+ca)}

που αυτή ισοδυναμεί με την προφανή \displaystyle{4a^2+(b-c)^2\geq 0.}

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Παρ Ιούλ 15, 2016 10:28 am
από Demetres
Al.Koutsouridis έγραψε:1. Υπάρχει τριώνυμο f(x) δευτέρου βαθμού με ακέραιους συντελεστές τέτοιο, ώστε f(f(\sqrt{2})) = 0 ;
Ίσως να υπάρχει και κάτι καλύτερο.

Θα δείξουμε πως τέτοιο πολυώνυμο δεν υπάρχει. Έστω λοιπόν προς άτοπο ότι το f(x) = ax^2+bx+c ικανοποιεί το ζητούμενο. Τότε το f(\sqrt{2}) = (2a+c)+b\sqrt{2} είναι ρίζα του f(x). Δηλαδή

\displaystyle{ (2a+c) + b\sqrt{2} = \frac{-b \pm \sqrt{b^2-4ac}}{2a}.}

Από εδώ παίρνουμε 2a(2a+c) = -b και 2ab\sqrt{2} = \pm \sqrt{b^2 - 4ac}.

Η δεύτερη συνθήκη δίνει 8a^2b^2 = b^2 - 4ac οπότε 4ac = (1-8a^2)b^2. Αντικαθιστώντας στην πρώτη παίρνω

\displaystyle{ 8a^2 + (b^2 - 8a^2b^2) + 2b = 0}

δηλαδή

\displaystyle{ (1-8a^2)b^2 + 2b + 8a^2 = 0}

Βλέποντας το τελευταίο ως τριώνυμο ως προς b, για να έχει ακέραια ρίζα, πρέπει η διακρίνουσά του να είναι τέλειο τετράγωνο. Όμως

\displaystyle{ \Delta = 4 - 4 \cdot 8a^2 (1-8a^2) = 256a^4 - 32a^2 + 4 = (16a^2 - 1)^2 + 3}

Οι μοναδικές όμως λύσεις της x^2 = y^2 + 3 στους ακεραίους είναι οι (\pm 2, \pm 1). (Εύκολο αφού (x-y)(x+y) = 3.) Πρέπει λοιπόν 16a^2 - 1 = \pm 1 που δίνει a=0, άτοπο.

Επεξεργασία: Τελικά την πάτησα την μπανανόφλουδα. Ψάξτε να βρείτε το λάθος. Αν δεν το βρείτε τότε δείτε την επόμενη ανάρτηση του Αχιλλέα.

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Παρ Ιούλ 15, 2016 4:50 pm
από achilleas
Al.Koutsouridis έγραψε:1. Υπάρχει τριώνυμο f(x) δευτέρου βαθμού με ακέραιους συντελεστές τέτοιο, ώστε f(f(\sqrt{2})) = 0 ;


....
Έστω ότι υπάρχει f(x) = ax^2+bx+c που να ικανοποιεί το ζητούμενο και τέτοιο ώστε a>0 και \gcd(a,b,c)=1.

Τότε, αν b\ne 0, όπως ο Δημήτρης παραπάνω παίρνουμε 2a(2a+c) = -b και 2ab\sqrt{2} =\pm \sqrt{b^2 - 4ac}.

Αφού (2a+c)-b\sqrt{2}=\dfrac{-b\mp\sqrt{b^2-4ac}}{2a}, ο αριθμός (2a+c)-b\sqrt{2} είναι επίσης ρίζα του f(x).

Συνεπώς, αν b\ne 0, τότε f(x)=a((x-2a-c)^2-2b^2), απ' όπου έπεται ότι b=-2a(2a+c) και a((2a+c)^2-2b^2)=c.

Αφού a>0 και \gcd(a,b,c)=1, έπεται ότι a=1, b=-4-2c και (2+c)^2-2b^2=c.

Οι τελευταίες δύο σχέσεις, όμως, δίνουν την εξίσωση 7c^2+29c+28=0, η οποία δεν έχει ακέραια ρίζα, άτοπο.

ΠΡΟΣΘΗΚΗ (6:04μμ)

Αν b=0, τότε f(x)=a(x^2-(2a+c)^2), απ' όπου έπεται ότι -a((2a+c)^2=c.
Όπως παραπάνω, παίρνουμε a=1 και -(2+c)^2=c, η οποία δίνει c=-1 ή c=-4, κι άρα

f(x)=x^2-1 ή f(x)=x^2-4.

Για αυτά τα πολυώνυμα εύκολα βλέπουμε ότι ισχύει f(f(\sqrt{2}))=0.

Φιλικά,

Αχιλλέας

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Σάβ Ιούλ 16, 2016 9:42 am
από Demetres
Al.Koutsouridis έγραψε: 3. Τα κελιά ενός τετραγώνου διαστάσεων 2015 \times 2015 χρωματίζονται με τέσσερα χρώματα. Θεωρούμε όλους τους τρόπους τοποθέτησης εσωτερικά αυτού του τετραγώνου σχήματος ταφ (T) των τεσσάρων κελιών (μπορεί και περιστροφές του). Να αποδείξετε ότι το σχήμα περιέχει τέσσερα διαφορετικά χρώματα λιγότερο από το 51% αυτών των περιπτώσεων.
Θα ονομάζω σχήματα ταυ με τέσσερα διαφορετικά χρώματα παρδαλά.

Η βασική ιδέα είναι να βρούμε ένα μικρό σχήμα όπου όπως και να το χρωματίσουμε, το πολύ τα μισά από τα ταυ του να είναι παρδαλά. Αν τώρα το 98\% των ταυ του 2015 \times 2015 ανήκουν σε τέτοια σχήματα (*) τότε θα έχουμε τελειώσει: Από αυτά μόνο τα μισά, δηλαδή το 49\% όλων των ταυ, θα μπορούν να είναι παρδαλά. Αν προσθέσουμε και όλα τα υπόλοιπα (που είναι το 2\%) θα έχουμε το πολύ 51\%.

(*) Εδώ θα χρειαστεί επίσης κάθε ταυ να ανήκει σε ίσο αριθμό από τέτοια σχήματα για να βγει σωστά το αποτέλεσμα.

Αρχικά δοκίμασα το 3\times 3 τετράγωνο αλλά τελικά δεν δουλεύει αφού ο πιο κάτω χρωματισμός έχει 5 στα 8 ταυ παρδαλά.

\begin{tabular}{|c|c|c|} \hline 1 & 3 & 2 \\ \hline 2 & 4 & 2 \\ \hline 3 & 1 & 2 \\ \hline \end{tabular}

Αντί αυτού, τελικά αυτό που δουλεύει είναι οι σταυροί με 5 τετράγωνα.


\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \clip(1.5,0.68) rectangle (5.44,4.36); \draw (2.,3.)-- (2.,2.); \draw (2.,2.)-- (5.,2.); \draw (5.,2.)-- (5.,3.); \draw (5.,3.)-- (2.,3.); \draw (3.,4.)-- (3.,1.); \draw (3.,1.)-- (4.,1.); \draw (4.,1.)-- (4.,4.); \draw (4.,4.)-- (3.,4.); \end{tikzpicture}

Αυτοί περιέχουν 4 ταυ ο καθένας και κάθε χρωματισμός τους έχει το πολύ δύο παρδαλά ταυ. Πράγματι, αφού ο Σταυρός έχει 5 τετράγωνα σε κάθε χρωματισμό θα έχουμε τουλάχιστον δύο τετράγωνα με το ίδιο χρώμα. Οποιαδήποτε δύο τετράγωνα όμως ανήκουν σε τουλάχιστον δύο ταυ. (Απλός έλεγχος τριών διαφορετικών περιπτώσεων.)

Παρατηρούμε τώρα ότι το 2015\times 2015 τετράγωνο περιέχει 2013^2 τέτοιους σταυρούς. (Το κέντρο του σταυρού πρέπει να βρίσκεται στο εσωτερικό 2013 \times 2013 τετράγωνο.) Κάθε σταυρός έχει ακριβώς τέσσερα ταυ εκ των οποίων το πολύ τα δύο είναι παρδαλά. Επίσης κάθε παρδαλό ταυ ανήκει σε ακριβώς έναν σταυρό εκτός από αυτά που έχουν το κέντρο τους στον περίγυρο του μεγάλου τετραγώνου.


Συνολικά λοιπόν έχουμε ακριβώς 4 \cdot 2013^2 + 4 \cdot 2013 ταυ. Ο δεύτερος προσθετέος προέρχεται από το ότι έχουμε 2013 ταυ που εφάπτονται σε κάθε μία πλευρά.

Από αυτά το πολύ 2 \cdot 2013^2 + 4\cdot 2013 είναι παρδαλά.

Επειδή τώρα

\displaystyle{ \frac{2 \cdot 2013^2 + 4\cdot 2013}{4 \cdot 2013^2 + 4 \cdot 2013} = \frac{1}{2} + \frac{2 \cdot 2013}{4 \cdot 2013^2 + 4 \cdot 2013} = \frac{1}{2} + \frac{1}{2 \cdot 2013 +2} < \frac{51}{100}}

οπότε το ζητούμενο αποδείχθηκε.

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Τετ Ιούλ 27, 2016 10:08 pm
από Demetres
Al.Koutsouridis έγραψε: 6. Στην διαγαλαξιακή αυτοκρατορία υπάρχουν 10^{2015} πλανήτες, οποιοιδήποτε δύο από τους οποίους συνδέονται με μια κοσμική γραμμή διπλής κατεύθυνσης. Αυτές οι συνδέσεις εξυπηρετούνται από 2015 μεταφορικές εταιρείες. Ο αυτοκράτορας θέλει να κλείσει k από αυτές τις εταιρίες έτσι, ώστε, χρησιμοποιώντας τις υπόλοιπες να μπορεί κάποιος να βρει τρόπο να μεταφερθεί από οποιοδήποτε πλανήτη σε κάποιον άλλο. Για ποιο μέγιστο k με σιγουριά μπορεί να επιτευχθεί ένα τέτοιο πλάνο;
Θα δείξουμε ότι μπορούμε να κλείσουμε 1007 εταιρίες αλλά όχι περισσότερες.

Για να δείξουμε ότι μπορούμε να κλείσουμε 1007 εταιρίες χωρίζουμε αυθαίρετα τις εταιρίες σε δυο σύνολο A και B με 1007 και 1008 εταιρίες αντίστοιχα. Αρκεί να δείξουμε πως για τουλάχιστον ένα από τα δύο σύνολα εταιριών μπορούμε να μεταφερθούμε από οποιοδήποτε πλανήτη σε οποιοδήποτε άλλο χρησιμοποιώντας μόνο εταιρίες από αυτό το σύνολο.

Έστω λοιπόν προς άτοπο ότι δεν μπορούμε να το κάνουμε αυτό για το σύνολο A και έστω δύο πόλεις x,y ώστε να μην μπορούμε να μετακινηθούμε από την πόλη x στην πόλη y χρησιμοποιώντας μόνο εταιρίες του συνόλου A. Αυτό σημαίνει ότι οι πόλεις x,y συνδέονται με μια εταιρία του συνόλου B. Επίσης για κάθε άλλη πόλη z, είτε οι x,z συνδέονται με μια εταιρεία του B είτε οι y,z συνδέονται με μια εταιρεία του B. (Πράγματι, σε αντίθετη περίπτωση θα μπορούσαμε να μετακινηθούμε από την x στην y μέσω της z χρησιμοποιώντας εταιρείες μόνο της A, άτοπο.) Αυτό όμως σημαίνει ότι μπορούμε να πάμε από κάθε πόλη z και στην x και στην y μέσω εταιρειών του B. Άρα μπορούμε να πάμε μέσω εταιρειών του B από κάθε πόλη σε κάθε άλλη πόλη, μέσω των x,y αν χρειαστεί.

(Το πιο πάνω είναι ουσιαστικά το «γνωστό» αποτέλεσμα που λέει ότι για κάθε γράφημα G τουλάχιστον ένα από τα G,\bar{G} είναι συνεκτικό.)

Μένει τώρα να βρούμε παράδειγμα που να δείχνει ότι δεν μπορούμε να κλείσουμε 1008 εταιρίες.

Ξεκινάμε με \binom{2015}{1008} < 2^{2015} < 10^{2015} πόλεις, μια για κάθε υποσύνολο του \{1,2,\ldots,2015\} μεγέθους 1008. Για κάθε δυο πόλεις τα αντίστοιχα υποσύνολα έχουν αναγκαστικά μη κενή τομή. Συνδέουμε λοιπόν τις πόλεις με την εταιρεία i όπου το i είναι το ελάχιστο στοιχείο της τομής των συνόλων των δύο πόλεων.

Αν τώρα κλείσουμε 1008 εταιρείες θα υπάρχει τουλάχιστον μία πόλη (αυτή για την οποία το αντίστοιχο σύνολο αποτελείται από αυτές τις 1008 εταιρείες) η οποία δεν θα συνδέεται με καμία άλλη πόλη μέσω αυτών των εταιρειών, άτοπο.

Καταλήξαμε σε άτοπο αν έχουμε \binom{2015}{1008} πόλεις. Αν έχουμε αντιπαράδειγμα με n πόλεις μπορούμε να κατασκευάσουμε αντιπαράδειγμα με n+1 πόλεις ως εξής: Παίρνουμε αυθαίρετα μια πόλη x και κατασκευάζουμε μια καινούργια πόλη x' συνδέοντας την x' με την x χρησιμοποιώντας την εταιρεία 1. Επίσης για κάθε άλλη πόλη y συνδέουμε την x' με την y με την εταιρεία που συνδέει την x με την y. Αν μπορούμε να κλείσουμε 1008 εταιρείες στην δεύτερη περίπτωση ώστε να μπορούμε να έχουμε μετακινήσεις τότε μπορούμε να το κάνουμε και στην πρώτη περίπτωση, άτοπο.

Οπότε έχουμε αντιπαράδειγμα και με 10^{2015} πόλεις.

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Τετ Ιούλ 27, 2016 11:55 pm
από taratoris
Demetres έγραψε:
Από εδώ παίρνουμε 2a(2a+c) = -b και 2ab\sqrt{2} = \pm \sqrt{b^2 - 4ac}.
Το λάθος του Δημήτρη (για όποιον ενδιαφέρεται) είναι οτι θεωρεί οτι b \neq 0 και μετά διαχωρίζει ρητά και άρρητα μέλη της εξίσωσης.

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Πέμ Ιούλ 28, 2016 9:55 am
από dement
taratoris έγραψε:
Demetres έγραψε:
Από εδώ παίρνουμε 2a(2a+c) = -b και 2ab\sqrt{2} = \pm \sqrt{b^2 - 4ac}.
Το λάθος του Δημήτρη (για όποιον ενδιαφέρεται) είναι οτι θεωρεί οτι b \neq 0 και μετά διαχωρίζει ρητά και άρρητα μέλη της εξίσωσης.
Δεν είμαι σίγουρος ότι είναι λάθος. Η εκφώνηση αναφέρει ρητά τριώνυμο.

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Πέμ Ιούλ 28, 2016 10:15 am
από Demetres
Al.Koutsouridis έγραψε:
7. Ακολουθία φυσικών αριθμών ορίζεται ως εξής: a_{1} =1, a_{2}=2, a_{3}=3, a_{n} = - ο ελάχιστος φυσκός αριθμός, που δεν εμφανίζεται πριν, από το πρώτο μεταξύ του a_{n-1} και πρώτο μεταξύ του a_{n-2}. Να αποδείξετε, ότι σε αυτή την ακολουθία εμφανίζονται ακριβώς από μια φορά όλοι οι φυσικοί αριθμοί.
Δεν καταλαβαίνω το κοκκινισμένο. :oops:

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Πέμ Ιούλ 28, 2016 2:08 pm
από Al.Koutsouridis
Demetres έγραψε:
Al.Koutsouridis έγραψε:
7. Ακολουθία φυσικών αριθμών ορίζεται ως εξής: a_{1} =1, a_{2}=2, a_{3}=3, a_{n} = - ο ελάχιστος φυσκός αριθμός, που δεν εμφανίζεται πριν, από το πρώτο μεταξύ του a_{n-1} και πρώτο μεταξύ του a_{n-2}. Να αποδείξετε, ότι σε αυτή την ακολουθία εμφανίζονται ακριβώς από μια φορά όλοι οι φυσικοί αριθμοί.
Δεν καταλαβαίνω το κοκκινισμένο. :oops:
Καλησπέρα,

Δικό μου το λάθος :oops: , δεν έκανα σωστή απόδοση και συγνώμη για όσους ταλαιπώρησα. Το σωστό και πάλι, επιφυλάσσομαι όμως, γιατι δεν έχω λύσει την άσκηση είναι:

Ακολουθία φυσικών αριθμών ορίζεται ως εξής: a_{1} =1, a_{2}=2, a_{3}=3, a_{n} = - ο ελάχιστος φυσκός αριθμός, που δεν έχει εμφανιστεί πιο πριν (στην ακολουθία),σχετικά πρώτος με τον a_{n-1} και σχετικά μη πρώτος με τον a_{n-2}. Να αποδείξετε, ότι σε αυτή την ακολουθία εμφανίζονται ακριβώς από μια φορά όλοι οι φυσικοί αριθμοί.

Έχω αλλάξει την εκφώνηση και στην αρχική ανάρτηση.

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Δευ Αύγ 15, 2016 1:37 pm
από Demetres
Al.Koutsouridis έγραψε: 7. Ακολουθία φυσικών αριθμών ορίζεται ως εξής: a_{1} =1, a_{2}=2, a_{3}=3, a_{n} = - ο ελάχιστος φυσκός αριθμός, που δεν έχει εμφανιστεί πιο πριν (στην ακολουθία),σχετικά πρώτους με τον a_{n-1} και σχετικά μη πρώτος με τον a_{n-2}. Να αποδείξετε, ότι σε αυτή την ακολουθία εμφανίζονται ακριβώς από μια φορά όλοι οι φυσικοί αριθμοί.
Δεν βρήκα κάτι πιο απλό από το πιο κάτω. :(

Ασφαλώς κάθε φυσικός εμφανίζεται το πολύ μία φορά οπότε το κύριο κομμάτι της άσκηση είναι να δειχθεί ότι κάθε φυσικός εμφανίζεται. Είναι επίσης απλό ότι η ακολουθία είναι άπειρη αφού για οποιουσδήποτε πρώτος μεταξύ τους αριθμούς a,b με a > 1 υπάρχουν άπειροι αριθμοί c με (a,c) > 1 και (b,c) = 1.

Έστω πρώτος p > 3. Έστω n_p η πρώτη φορά που εμφανίζεται ένα πολλαπλάσιο του p. Αν δεν εμφανίζεται κανένα πολλαπλάσιο του p τότε ορίζω n_p = \infty.

Θα αποδείξουμε κατά σειρά τα πιο κάτω λήμματα με το Λήμμα 5 να ολοκληρώνει την απόδειξη της άσκησης. Τις αποδείξεις των Λημμάτων τις βάζω σε απόκρυψη ώστε να τις δοκιμάσετε χωρίς να τις δείτε.

Λήμμα 1: Αν p < q πρώτοι με n_q < \infty τότε είναι και n_q \neq \infty και επιπλέον n_p < n_q.
Μπορούμε να υποθέσουμε ότι p > 3 αφού αλλιώς το συμπέρασμα είναι άμεσο. Ας υποθέσουμε ότι a_{n_q} = kq. Αυτό σημαίνει ότι (a_{n_q-2},k) > 1 και (a_{n_q-1},k) = 1. Επειδή όμως kp < kq τότε είτε ήδη έχει εμφανιστεί ο kp στην ακολουθία (πριν τον kq) είτε (a_{n_q-1},p) > p. Και στις δύο περιπτώσεις παίρνουμε n_p < n_q.
Λήμμα 2: Για κάθε πρώτο p έχουμε n_p \neq \infty.
Ας υποθέσουμε ότι υπάρχει πρώτος p με n_p = \infty. Έστω p_1,\ldots,p_r όλοι οι πρώτοι οι οποίοι είναι μικρότεροι του p. Από το Λήμμα 1 οι πρώτοι παράγοντες κάθε όρου της ακολουθίας ανήκουν στο σύνολο \{p_1,\ldots,p_r\}. Σε κάποια φάση η ακολουθία θα έχει όρο a_n με a_n > pp_r. Έστω p_i | (a_{n-2},a_n). Τότε στην θέση του a_n θα μπορούσαμε να γράψουμε τον pp_i ο οποίος είναι μικρότερος, άτοπο. [Αφού (a_{n-2},pp_i) > 1 και (a_{n-1},p_i)=1.]
Λήμμα 3: Για κάθε πρώτο p έχουμε άπειρους όρους της ακολουθίας οι οποίοι είναι πολλαπλάσια του p.
Έστω ότι αυτό δεν ισχύει και έστω πρώτος p ώστε το μεγαλύτερό του πολλαπλάσιο το οποίο εμφανίστηκε στην ακολουθία να είναι το a_n = Np. Έστω r ώστε p^r > N. Παίρνουμε ένα πρώτο q με n_q > n και q > p^r. Τέτοιος q υπάρχει από το Λήμμα 2. Έστω ότι a_{n_q} = kq. Όμως στην θέση του θα μπορούσαμε να γράψουμε τον kp^r < kq ο οποίος δεν έχει εμφανιστεί, άτοπο.
Λήμμα 4: Κάθε πρώτος p εμφανίζεται στην ακολουθία.
Έστω n_1 < n_2 < n_3 < \cdots με a_{n_i} πολλαπλάσιο του p για κάθε i. (Υπάρχουν από το Λήμμα 3.) Έστω επίσης n ώστε a_N > p για κάθε n > N. Παίρνω i με n_i > n. Τότε στην θέση a_{n_i+2} μπορώ να γράψω τον p, άτοπο. Άρα ο p πρέπει να έχει ήδη γραφτεί.
Λήμμα 5: Στην ακολουθία εμφανίζεται κάθε φυσικός.
Ας υποθέσουμε πως αυτό δεν συμβαίνει και έστω N ο μικρότερος αριθμός ο οποίος δεν εμφανίζεται στην ακολουθία. Έστω p_1,\ldots,p_r οι πρώτοι παράγoντες του N. Έστω επίσης M ώστε a_n > N για κάθε n > M. Παίρνουμε n_1 > M ώστε p_i|a_n για κάποιο 1 \leqslant i \leqslant r. Τότε μπορώ να γράψω a_{n_1+2} = N εκτός και αν p_j|a_{n_1+1} για κάποιο 1 \leqslant j \leqslant r. Αλλά τότε μπορώ να γράψω a_{n_1+3} = N εκτός και αν p_k|a_{n_1+2} για κάποιο 1 \leqslant k \leqslant r κ.ο.κ.

Άρα επαγωγικά για κάθε n > n_1 έχει p_{\ell} | a_n. Αυτό όμως είναι άτοπο από το Λήμμα 4 αφού θα υπάρχει πρώτος p > p_1,\ldots,p_r και n > n_1 ώστε a_n = p. Άρα και η απόδειξη του Λήμματος 5 ολοκληρώθηκε.

Re: Μαθηματική Ολυμπιάδα Α.Πετρούπολης 2015 ΙΙΦ (9η τάξη)

Δημοσιεύτηκε: Τρί Αύγ 16, 2016 3:08 pm
από taratoris
Πολύ ωραία η απόδειξη του Δημήτρη.

Έχω κάποιες ερωτήσεις/ιδέες σχετικά με περεταίρω προβλήματα:

1) Έγραψα κώδικα ο οποίος για κάθε πρώτο αριθμό μου επιστρέφει την θέση που εμφανίζεται ο πρώτος αυτός στην ακολουθία. Πχ ο αριθμός 2 εμφανίζεται στην θέση 2 κοκ. Επιπλέον για κάθε τέτοιο πρώτο αριθμό ο κώδικας επιστρέφει τον λόγο (ratio) της θέσης στην οποία εμφανίζεται ο αριθμός ως προς τον αριθμό.(δηλαδή για τον p=2 ο λόγος θα είναι 2/2=1 κοκ). Επιστρέφω κάποια ποτελέσματα κάτωθι:

p= 103 location is 221 ratio is 2.14563106796
p= 107 location is 232 ratio is 2.16822429907
p= 109 location is 237 ratio is 2.17431192661
p= 113 location is 246 ratio is 2.17699115044
p= 127 location is 273 ratio is 2.14960629921
p= 131 location is 282 ratio is 2.15267175573
p= 137 location is 295 ratio is 2.15328467153
p= 139 location is 300 ratio is 2.15827338129
p= 149 location is 323 ratio is 2.1677852349
p= 151 location is 328 ratio is 2.17218543046
p= 157 location is 337 ratio is 2.14649681529
p= 163 location is 354 ratio is 2.1717791411
p= 167 location is 363 ratio is 2.17365269461
p= 173 location is 374 ratio is 2.16184971098
p= 179 location is 385 ratio is 2.15083798883
p= 181 location is 392 ratio is 2.16574585635
p= 191 location is 413 ratio is 2.16230366492
p= 193 location is 422 ratio is 2.18652849741
p= 197 location is 429 ratio is 2.17766497462
p= 199 location is 434 ratio is 2.18090452261
p= 211 location is 451 ratio is 2.13744075829
p= 223 location is 478 ratio is 2.14349775785
p= 227 location is 489 ratio is 2.15418502203
p= 229 location is 496 ratio is 2.16593886463
p= 233 location is 505 ratio is 2.16738197425
p= 239 location is 522 ratio is 2.18410041841
p= 241 location is 527 ratio is 2.1867219917
p= 251 location is 540 ratio is 2.15139442231
p= 257 location is 549 ratio is 2.13618677043
p= 263 location is 570 ratio is 2.16730038023
p= 269 location is 581 ratio is 2.15985130112
p= 271 location is 588 ratio is 2.16974169742
p= 277 location is 601 ratio is 2.16967509025
p= 281 location is 610 ratio is 2.17081850534
p= 283 location is 619 ratio is 2.18727915194
p= 293 location is 636 ratio is 2.17064846416
p= 307 location is 667 ratio is 2.17263843648
p= 311 location is 674 ratio is 2.16720257235
p= 313 location is 681 ratio is 2.17571884984
p= 317 location is 690 ratio is 2.17665615142
p= 331 location is 719 ratio is 2.17220543807
p= 337 location is 728 ratio is 2.16023738872
p= 347 location is 753 ratio is 2.17002881844
p= 349 location is 758 ratio is 2.17191977077
p= 353 location is 765 ratio is 2.1671388102
p= 359 location is 778 ratio is 2.16713091922
p= 367 location is 793 ratio is 2.16076294278
p= 373 location is 808 ratio is 2.16621983914
p= 379 location is 819 ratio is 2.16094986807
p= 383 location is 830 ratio is 2.16710182768
p= 389 location is 847 ratio is 2.17737789203
p= 397 location is 860 ratio is 2.16624685139
p= 401 location is 867 ratio is 2.16209476309
p= 409 location is 884 ratio is 2.16136919315
p= 419 location is 903 ratio is 2.15513126492
p= 421 location is 908 ratio is 2.1567695962
...
...
...
p= 643 location is 1391 ratio is 2.1632970451
p= 647 location is 1400 ratio is 2.16383307573
p= 653 location is 1413 ratio is 2.16385911179
p= 659 location is 1428 ratio is 2.16691957511
p= 661 location is 1433 ratio is 2.16792738275
p= 673 location is 1458 ratio is 2.16641901932
p= 677 location is 1467 ratio is 2.16691285081
p= 683 location is 1478 ratio is 2.16398243045
p= 691 location is 1499 ratio is 2.16931982634
p= 701 location is 1520 ratio is 2.16833095578
p= 709 location is 1533 ratio is 2.16220028209
p= 719 location is 1552 ratio is 2.15855354659
p= 727 location is 1573 ratio is 2.16368638239
p= 733 location is 1582 ratio is 2.15825375171
p= 739 location is 1601 ratio is 2.16644113667
p= 743 location is 1608 ratio is 2.16419919246

Παρατηρώ οτι ο λόγος της θέσης που εμφανίζεται ενας πρώτος ως προς τον πρώτο είναι πάντα κάπου ανάμεσα στο 2.13 και 2.19. Αυτή η παρατήρηση ισχύει και για αρκετά μεγαλύτερους πρώτους. Αναρωτιέμαι αν μπορούμε να αποδείξουμε οτι ο λόγος τείνει σε κάποιο όριο (πχ 2.16) ή εαν τουλάχιστον ο λόγος είναι άνω και κάτω φραγμένος.

2) Αρχικά διαβάζοντας το πρόβλημα, το διάβασα λάθος και θεώρησα οτι κάθε αριθμός a_n που εμφανίζεται είναι ο μικρότερος που είναι σχετικά πρώτος με τον a_{n-1} και με τον a_{n-2}. Γράφοντας κώδικα φαίνεται οτι ισχύει οτι και σε αυτή την περίπτωση όλοι οι θετικοί ακέραιοι εμφανίζονται. Θεωρώ είναι ενδιαφέρον να δείξουμε εαν ισχύει ή όχι.
Όλοι οι χρόνοι είναι UTC+02:00
Σελίδα 1 από 1

Δημιουργήθηκε από phpBB® Forum Software © phpBB Limited


Ελληνική μετάφραση από το phpbbgr.com