IMC 2015/1/2

#1

Για κάθε θετικό ακέραιο

ορίζουμε ως f(n)

τον αριθμό που προκύπτει αν γράψουμε τον

στην δυαδική του αναπαράσταση και ακολούθως αλλάξουμε κάθε εμφάνιση του

με το

και αντίστροφα. Π.χ. το n=23

ισούται με 10111

στο δυαδικό σύστημα. Αυτό γίνεται 1000

οπότε

.

Να αποδειχθεί ότι

$\displaystyle{\sum_{k=1}^n f(k) \leqslant \frac{n^2}{4}.}$

Πότε ισχύει η ισότητα;

ArgirisM · #2

Η ιδέα της δοθείσας συνάρτησης στηρίζεται στην έννοια του συμπληρώματος ως προς 1 (Για περισσότερες πληροφορίες: https://en.wikipedia.org/wiki/Ones%27_complement). Ο τύπος της είναι λοιπόν $\displaystyle{f(n) = (2^{[lgn] + 1} - 1) - n, \forall n \in N}$ (Με $\displaystyle{[lgn] + 1}$ ισούται ο ελάχιστος αριθμός ψηφίων που χρειάζονται για να αναπαρασταθεί δυαδικώς ένας αριθμός). Συνεπώς η προς απόδειξη σχέση γράφεται ισοδύναμα:
$\displaystyle{2(2^{[lg1]} + 2^{[lg2]} +...+ 2^{[lgn]}) - n - \frac{n(n + 1)}{2} \le \frac{n^2}{2}} \Longleftrightarrow \sum_{i = 1}^{n}2^{[lgi]} \le \frac{3}{8}n(n + 2)}$
Θα διακρίνουμε δύο περιπτώσεις:
i) Έστω ότι $\displaystyle{n = 2^k - 1, k \in N}$ . Τότε το άθροισμα γράφεται:
$\displaystyle{1 + 2 \cdot 2 + 4 \cdot 4 + ... + 2^{k - 1} \cdot 2^{k - 1} = 1 + 4 + 4^2 + ... + 4^{k - 1} = \frac{4^k - 1}{3} \le \frac{3}{8}(2^k - 1)(2^k + 1) \Longleftrightarrow 1 \le 4^k}$ , το οποίο ισχύει πάντοτε (Η ιδέα εδώ είναι πως οι 2^i

αριθμοί μεταξύ 2^i

και $2^{i + 1} - 1$ έχουν όλοι ίδιο μήκος δυαδικής αναπαράστασης, οπότε προκύπτουν τα γινόμενα που αποτελούν τους επιμέρους όρους του αθροίσματος).
ii) Έστω ότι δεν υπάρχει φυσικός με την ιδιότητα που υποθέσαμε παραπάνω. Βρίσκουμε τότε το μέγιστο $k \in N$ που είναι τέτοιο ώστε το 2^k

να μην υπερβαίνει το

. Θα είναι τέτοιο ώστε $\displaystyle{2^k \le n < 2^{k + 1} - 1 < 2^{k + 1} \Longrightarrow k \le lgn < k + 1 \Longrightarrow k = [lgn]}$ . Τότε το άθροισμα γράφεται:
$\displaystyle{\frac{4^k - 1}{3} + (n + 1 - 2^k)2^k \le \frac{3}{8}n(n + 2) \Longleftrightarrow (n + 1)2^k - \frac{2 \cdot 4^k + 1}{3} \le \frac{3}{8}n(n + 2) \Longleftrightarrow 0 \le 9n^2 + (18 - 24 \cdot 2^k)n + (16 \cdot 4^k - 24 \cdot 2^k + 8)}$
Θεωρώντας την δεξιά μεριά τριώνυμο ως προς

έχουμε διακρίνουσα $\Delta = 36 \Longrightarrow n_{1, 2} = \frac{4}{3} \cdot 2^k - 1 \pm \frac{1}{3}$ . Έχουμε λοιπόν ότι πρέπει για κάθε φυσικό να ισχύει μία εκ των σχέσεων $n \le \frac{4}{3} \cdot 2^k - \frac{4}{3}$ ή $n \geq \frac{4}{3} \cdot 2^k - \frac{2}{3}$ . Υποθέτουμε πως δεν ισχύει καμιά εκ των δύο, για κάποιον φυσικό. Τότε όμως θα ήταν $\displaystyle{\frac{4}{3} \cdot 2^k - \frac{4}{3} < n < \frac{4}{3} \cdot 2^k - \frac{2}{3} \Longleftrightarrow 4 \cdot 2^k - 4 < 3n < 4 \cdot 2^k - 2 \Longrightarrow 3n = 4 \cdot 2^k - 3 \Longleftrightarrow 3(n + 1) = 4 \cdot 2^k}$ το οποίο είναι αδύνατο διότι το

στο δεξί μέλος θα έπρεπε να υπάρχει ως παράγοντας και στο αριστερό. Άρα η ανισότητα αληθεύει για κάθε φυσικό. Μένει τώρα να εξετάσουμε την περίπτωση της ισότητας. Θα πρέπει $n = \frac{4}{3}(2^k - 1) \vee n = \frac{2}{3}(2^{k + 1} - 1)$ , όπου όμως θα πρέπει να διασφαλισθεί ότι θα πληροίται ο περιορισμός ότι k = [lgn]

, καθώς και ότι οι τιμές που θα λαμβάνει το

θα είναι τέτοιες ώστε το

να είναι φυσικός. Αυτό μας οδηγεί στο συμπέρασμα πως ο πρώτος τύπος ισχύει για κάθε

άρτιο, ενώ ο δεύτερος για κάθε

περιττό.
edit: Νομίζω πως τώρα είναι πλήρης η απόδειξη. Διορθώθηκε μία αβλεψία (είχα ξεχάσει να διαιρέσω τις ρίζες του τριωνύμου με

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

mathematica.gr

IMC 2015/1/2

IMC 2015/1/2

Re: IMC 2015/1/2

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