IMC 2016/2/4

Συντονιστής: Demetres

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

IMC 2016/2/4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Ιούλ 28, 2016 11:21 pm

Έστω θετικός ακέραιος k. Για κάθε μη αρνητικό ακέραιο n συμβολίζουμε με f(n) το πλήθος των (x_1,\ldots,x_k) \in \mathbb{Z}^k τα οποία ικανοποιούν |x_1| + \cdots + |x_k| \leqslant n.

Να δειχθεί ότι f(n-1)f(n+1) \leqslant f(n)^2 για κάθε n \geqslant 1.



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

Re: IMC 2016/2/4

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 29, 2016 3:56 pm

Ας υπολογίσουμε πρώτα το f(n).

Θα μετρήσουμε αρχικά το πλήθος των λύσεων της |x_1| + \cdots + |x_k| \leqslant n όπου ακριβώς r από τα x_i είναι διάφορα του 0.

Έχουμε \displaystyle{\binom{k}{r}} τρόπους να επιλέξουμε ποια δεν θα ισούνται με 0 και 2^r επιλογές για το πρόσημο των μη μηδενικών στοιχείων. Μένει να βρούμε πόσες λύσεις έχει η y_1 + \cdots + y_r \leqslant n στους θετικούς ακεραίους.

Ισοδύναμα θέλουμε το πλήθος των λύσεων της y_1 + \cdots + y_r + y_{r+1} = n+1 στους θετικούς ακεραίους. Είναι γνωστό ότι η απάντηση ισούται με \binom{n}{r}. [Αν δεν το γνωρίζετε δοκιμάστε το!]

Καταλήγουμε στο \displaystyle{ f(n) = \sum_{r=0}^k 2^r \binom{k}{r} \binom{n}{r}}

Θέτω \displaystyle{a_r = 2^r \binom{n}{r}} και b_r = \binom{k}{r}.


Ονομάζω μια ακολουθία (c_n)_{n \geqslant 0} μη αρνητικών αριθμών log-concave αν
(α) c_n^2 \geqslant c_{n-1}c_{n+1} για κάθε n \geqslant 1 και
(β) Η ακολουθία δεν έχει ενδιάμεσες μηδενικές τιμές. Δηλαδή αν c_n = 0 τότε είτε c_m = 0 για κάθε m < n είτε c_m = 0 για κάθε m > n.

Θέλω να δείξω ότι η f(n) είναι log-concave.

Είναι γνωστό (και απλό) ότι οι (a_r) και (b_r) είναι log-concave.

Αρκεί να δείξω ότι αν οι ακολουθίες (a_r),(b_r) είναι log-concave το ίδιο ισχύει και για την ακολουθία \displaystyle{ c_n = \sum_{r=0}^k a_rb_{k-r}}

Θέλω λοιπόν να δείξω ότι

\displaystyle{\sum_r \sum_s a_ra_s b_{k-r}b_{k-s} \geqslant \sum_r \sum_s a_ra_sb_{k+1-r}b_{k-1-s} \qquad (\ast) }

Παρατηρώ αρχικά ότι r \leqslant s \implies a_ra_s - a_{r-1}a_{s+1} \geqslant 0}. Πράγματι
- Αν a_{r-1} = 0 η ανισότητα είναι προφανής.
- Αν τα a_{r-1},\ldots,a_s είναι όλα διάφορα του 0, τότε είναι
\displaystyle{ \frac{a_r}{a_{r-1}} \geqslant \frac{a_{r+1}}{a_r} \geqslant \cdots \geqslant \frac{a_{s+1}}{a_s}}
- Αν a_t = 0 για κάποιο t \in \{r,r+1,\ldots,s\} τότε είτε a_s = a_{s+1} = 0 είτε a_r = a_{r-1} = 0. Και στις δύο περιπτώσεις η ανισότητα είναι προφανής.

Ομοίως έχω r \geqslant s \implies a_ra_s - a_{r-1}a_{s+1} \leqslant 0}.

Ανάλογες ανισότητες ισχύουν ασφαλώς και για τα b_i. Οπότε για κάθε r,s έχω

\displaystyle{ (a_ra_s - a_{r-1}a_{s+1})(b_{k-r}b_{k-s} - b_{k-r+1}b_{k-s-1}) \geqslant 0}

το οποίο δίνει

\displaystyle{ a_ra_sb_{k-r}b_{k-s} + a_{r-1}a_{s+1}b_{k-r+1}b_{k-s-1} \geqslant a_ra_sb_{k-r+1}b_{k-s-1} + a_{r-1}a_{s+1}b_{k-r}b_{k-s}}

Προσθέτοντας λαμβάνω την (\ast) όπως ήθελα. [Τα αθροίσματα είναι πεπερασμένα οπότε δεν υπάρχει οποιοδήποτε θέμα σύγκλισης.]


silouan
Επιμελητής
Δημοσιεύσεις: 1237
Εγγραφή: Τρί Ιαν 27, 2009 10:52 pm

Re: IMC 2016/2/4

#3

Μη αναγνωσμένη δημοσίευση από silouan » Σάβ Ιούλ 30, 2016 12:28 am

Δημήτρη ωραία απόδειξη!
Μπορούμε να κάνουμε ένα διαφορετικό τελείωμα ως εξής:
Demetres έγραψε: Θέλω να δείξω ότι η f(n) είναι log-concave.

Είναι γνωστό (και απλό) ότι οι (a_r) και (b_r) είναι log-concave.

Αρκεί να δείξω ότι αν οι ακολουθίες (a_r),(b_r) είναι log-concave το ίδιο ισχύει και για την ακολουθία \displaystyle{ c_n = \sum_{r=0}^k a_rb_{k-r}}
Αυτό ισχύει γενικά: Αν έχουμε δύο συναρτήσεις που είναι log-concave, τότε η συνέλιξή τους (convolution) είναι επίσης log-concave και τελειώσαμε.
Η απόδειξη γίνεται μέσω της ανισότητας Prékopa–Leindler.
Δείτε πχ εδώ: https://en.wikipedia.org/wiki/Logarithm ... e_function


Σιλουανός Μπραζιτίκος
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

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