Putnam 1992/B1

Συντονιστές: Demetres, socrates, silouan

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

Putnam 1992/B1

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Ιαν 30, 2018 11:08 pm

Έστω θετικός ακέραιος n με n \geqslant 2, και έστω ένα σύνολο S από n διακεκριμένους ακεραίους. Έστω A_S το σύνολο όλων των αριθμών που μπορούν να προκύψουν ως ο μέσος όρος δύο στοιχείων του S.

Να βρεθεί το ελάχιστο δυνατό μέγεθος του A_S.



Λέξεις Κλειδιά:
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 793
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Putnam 1992/B1

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Τετ Ιαν 31, 2018 6:57 pm

Θεωρούμε τους αριθμούς a_1, a_2, ..., a_n που ανήκουν στο S, έτσι ώστε a_1<a_2<...<a_n.

Παρατηρούμε πως \dfrac{a_1+a_2}{2}<\dfrac{a_1+a_3}{2}<\dfrac{a_2+a_3}{2}<\dfrac{a_2+a_4}{2}<...<\dfrac{a_{n-2}+a_{n-1}}{2}<\dfrac{a_{n-2}+a_n}{2}<\dfrac{a_{n-1}+a_n}{2}.

Αυτοί οι μέσοι όροι είναι 2n-3 σε πλήθος και είναι όλοι διαφορετικοί. Άρα το A_S έχει αυτούς τους μέσους όρους τουλάχιστον, δηλαδή τουλάχιστον 2n-3 στοιχεία.

Θα αποδείξουμε πως υπάρχει σύνολο S, έτσι ώστε το πλήθος των στοιχείων του A_S να είναι 2n-3.

Πράγματι ας θεωρήσουμε το σύνολο 1, 2, 3, ..., n (Μπορούμε και μια γενικότερη αριθμητική πρόοδο).

Θεωρούμε B_S το σύνολο των μέσων όρων της μορφής \dfrac{1+2}{2}, \dfrac{1+3}{2}, \dfrac{2+3}{2}, \dfrac{2+4}{2},..., \dfrac{(n-2)+n}{2}, \dfrac{(n-1)+n}{2}. Το πλήθος των στοιχείων του B_S είναι 2n-3.

Για οποιοδήποτε μέσο όρο \dfrac{a_i+a_j}{2} με j>i+2, έχουμε πως αν i\equiv j \pmod{2}, τότε \dfrac{a_i+a_j}{2}=\dfrac{a_{\dfrac{i+j}{2}-1}+a_{\dfrac{i+j}{2}+1}}{2}, ο οποίος είναι μέσος όρος του B_S. Αν i\ne j \pmod{2}, τότε \dfrac{a_i+a_j}{2}=\dfrac{a_{\dfrac{i+j-1}{2}}+a_{\dfrac{i+j+1}{2}}}{2}, που ανήκει στο B_S.

Άρα κάθε μέσος όρος έχει ήδη μετρηθεί στο B_S , άρα A_S\equiv B_S και πράγματι το A_S έχει 2n-3 στοιχεία.


Houston, we have a problem!
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11289
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Putnam 1992/B1

#3

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τετ Ιαν 31, 2018 9:22 pm

Διονύσιος Αδαμόπουλος έγραψε:
Τετ Ιαν 31, 2018 6:57 pm
Θεωρούμε τους αριθμούς a_1, a_2, ..., a_n που ανήκουν στο S, έτσι ώστε a_1<a_2<...<a_n.

Παρατηρούμε πως \dfrac{a_1+a_2}{2}<\dfrac{a_1+a_3}{2}<\dfrac{a_2+a_3}{2}<\dfrac{a_2+a_4}{2}<...<\dfrac{a_{n-2}+a_{n-1}}{2}<\dfrac{a_{n-2}+a_n}{2}<\dfrac{a_{n-1}+a_n}{2}.

Αυτοί οι μέσοι όροι είναι 2n-3 σε πλήθος και είναι όλοι διαφορετικοί.
Ωραία λύση.

Ο δικός μου τρόπος να δείξω ότι οι μέσοι όροι είναι τουλάχιστον 2n-3 είναι με επαγωγή: Έστω f(n) το ελάχιστο πλήθος, και ειδικά f(2)=1 (άμεσο). Για το επαγωγικό βήμα, αν a_1<a_2<...<a_n < a_{n+1} δοθέντες τότε πέρα από τους μέσους όρους των πρώτων n όρων έχουμε τουλάχιστον δύο καινούργιους όταν εξετάζουμε n+1 στοιχεία, τους \dfrac{a_n+a_{n+1}}{2} και \dfrac{a_{n-1}+a_{n+1}}{2}. Άρα

f(n+1) \ge f(n)+2 . Αναδρομικά, f(n+1) \ge f(2)+ 2(n-1)=2n-1. Και λοιπά.


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Juniors)”

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

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