For a positive integer n, let f(n) be the number obtained by writing n in binary and replacing every 0 with 1 and vice versa. For example, n=23 is 10111 in binary, so f(n) is 1000 in binary, therefore f(23)=8. Prove that
k=1∑nf(k)≤4n2.
When does equality hold?
Πρωτότυπο από το επίσημο PDF
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Χρόνος σε αυτό το θέμα
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(Proposed by Stephan Wagner, Stellenbosch University)
Solution. If r and k are positive integers with 2r−1≤k<2r then k has r binary digits, so k+f(k)=(2)11…1=2r−1.
Notice that the difference of the last two factors is less than 1, and one of them must be an integer: 32s+1−2 is integer if s is even, and 32s+1−4 is integer if s is odd. Therefore, either one of them is 0, resulting a zero product, or both factors have the same sign, so the product is strictly positive. This solves the problem and shows that equality occurs if n=32s+1−2 (s is even) or n=32s+1−4 (s is odd).
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 2–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.