Putnam 1992/B1

#1

Έστω θετικός ακέραιος

με $n \geqslant 2$ , και έστω ένα σύνολο

από

διακεκριμένους ακεραίους. Έστω A_S

το σύνολο όλων των αριθμών που μπορούν να προκύψουν ως ο μέσος όρος δύο στοιχείων του

.

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

.

Διονύσιος Αδαμόπουλος · #2

Θεωρούμε τους αριθμούς a_1, a_2, ..., a_n

που ανήκουν στο

, έτσι ώστε 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

στοιχεία.

Θα αποδείξουμε πως υπάρχει σύνολο

, έτσι ώστε το πλήθος των στοιχείων του A_S

να είναι

.

Πράγματι ας θεωρήσουμε το σύνολο 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

είναι

.

Για οποιοδήποτε μέσο όρο $\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

έχει

στοιχεία.

#3

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

Παρατηρούμε πως $\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

είναι με επαγωγή: Έστω f(n)

το ελάχιστο πλήθος, και ειδικά f(2)=1

(άμεσο). Για το επαγωγικό βήμα, αν $a_1<a_2<...<a_n < a_{n+1}$ δοθέντες τότε πέρα από τους μέσους όρους των πρώτων

όρων έχουμε τουλάχιστον δύο καινούργιους όταν εξετάζουμε 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$ . Και λοιπά.

Putnam 1992/B1

Putnam 1992/B1

Re: Putnam 1992/B1

Re: Putnam 1992/B1

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