IMC 2015/1/2

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

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

IMC 2015/1/2

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Ιούλ 29, 2015 11:10 pm

Για κάθε θετικό ακέραιο n ορίζουμε ως f(n) τον αριθμό που προκύπτει αν γράψουμε τον n στην δυαδική του αναπαράσταση και ακολούθως αλλάξουμε κάθε εμφάνιση του 0 με το 1 και αντίστροφα. Π.χ. το n=23 ισούται με 10111 στο δυαδικό σύστημα. Αυτό γίνεται 1000 οπότε f(23) = 8.

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

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

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


ArgirisM
Δημοσιεύσεις: 224
Εγγραφή: Δευ Απρ 16, 2012 10:38 pm

Re: IMC 2015/1/2

#2

Μη αναγνωσμένη δημοσίευση από ArgirisM » Πέμ Ιούλ 30, 2015 5:53 pm

Η ιδέα της δοθείσας συνάρτησης στηρίζεται στην έννοια του συμπληρώματος ως προς 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 να μην υπερβαίνει το n. Θα είναι τέτοιο ώστε \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)}
Θεωρώντας την δεξιά μεριά τριώνυμο ως προς n έχουμε διακρίνουσα \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} το οποίο είναι αδύνατο διότι το 3 στο δεξί μέλος θα έπρεπε να υπάρχει ως παράγοντας και στο αριστερό. Άρα η ανισότητα αληθεύει για κάθε φυσικό. Μένει τώρα να εξετάσουμε την περίπτωση της ισότητας. Θα πρέπει n = \frac{4}{3}(2^k - 1) \vee n = \frac{2}{3}(2^{k + 1} - 1), όπου όμως θα πρέπει να διασφαλισθεί ότι θα πληροίται ο περιορισμός ότι k = [lgn], καθώς και ότι οι τιμές που θα λαμβάνει το k θα είναι τέτοιες ώστε το n να είναι φυσικός. Αυτό μας οδηγεί στο συμπέρασμα πως ο πρώτος τύπος ισχύει για κάθε k: άρτιο, ενώ ο δεύτερος για κάθε k: περιττό.
edit: Νομίζω πως τώρα είναι πλήρης η απόδειξη. Διορθώθηκε μία αβλεψία (είχα ξεχάσει να διαιρέσω τις ρίζες του τριωνύμου με 9 οπότε δεν έβγαινε περίπτωση ισότητας), ενώ προσπάθησα να την καταστήσω πιο επεξηγηματική σε κάποια σημεία. Σχόλια πάντοτε ευπρόσδεκτα :)


Αν κάτι μπορεί να πάει στραβά, θα πάει!
Νόμος του Μέρφυ
Απάντηση

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

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

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