uniolympiads English

IMC 2015, Ημέρα 1, Θέμα 2

For a positive integer nn, let f(n)f(n) be the number obtained by writing nn in binary and replacing every 00 with 11 and vice versa. For example, n=23n = 23 is 1011110111 in binary, so f(n)f(n) is 10001000 in binary, therefore f(23)=8f(23) = 8. Prove that

∑k=1nf(k)≤n24.\sum_{k=1}^{n} f(k) \le \frac{n^2}{4}.

When does equality hold?

Πρωτότυπο από το επίσημο PDFFor 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 n X f (k) ≤ k=1 n 2 . 4 When does equality hold?

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(Proposed by Stephan Wagner, Stellenbosch University)

Solution. If rr and kk are positive integers with 2r−1≤k<2r2^{r-1}\le k<2^r then kk has rr binary digits, so k+f(k)=11…1‾⏟r(2)=2r−1k+f(k) = \underbrace{\overline{11\ldots1}}_{r}^{(2)} = 2^r-1.

Assume that 2s−1−1≤n≤2s−12^{s-1}-1\le n\le 2^s-1. Then

n(n+1)2+∑k=1nf(k)=∑k=1n(k+f(k))==∑r=1s−1 ∑2r−1≤k<2r(k+f(k))+∑2s−1≤k≤n(k+f(k))==∑r=1s−12r−1⋅(2r−1)+(n−2s−1+1)⋅(2s−1)==∑r=1s−122r−1−∑r=1s−12r−1+(n−2s−1+1)(2s−1)==23(4s−1−1)−(2s−1−1)+(2s−1)n−22s−1+3⋅2s−1−1==(2s−1)n−134s+2s−23\begin{aligned} \frac{n(n+1)}{2}+\sum_{k=1}^{n} f(k) &= \sum_{k=1}^{n}(k+f(k)) = \\ &= \sum_{r=1}^{s-1}\ \sum_{2^{r-1}\le k<2^r}(k+f(k)) + \sum_{2^{s-1}\le k\le n}(k+f(k)) = \\ &= \sum_{r=1}^{s-1} 2^{r-1}\cdot(2^r-1) + (n-2^{s-1}+1)\cdot(2^s-1) = \\ &= \sum_{r=1}^{s-1} 2^{2r-1} - \sum_{r=1}^{s-1} 2^{r-1} + (n-2^{s-1}+1)(2^s-1) = \\ &= \tfrac{2}{3}(4^{s-1}-1) - (2^{s-1}-1) + (2^s-1)n - 2^{2s-1} + 3\cdot 2^{s-1} - 1 = \\ &= (2^s-1)n - \tfrac{1}{3}4^s + 2^s - \tfrac{2}{3} \end{aligned}
and therefore
n24−∑k=1nf(k)=n24−((2s−1)n−134s+2s−23−n(n+1)2)==34n2−(2s−32)n+134s−2s+23==34(n−2s+1−23)(n−2s+1−43).\begin{aligned} \frac{n^2}{4} - \sum_{k=1}^{n} f(k) &= \frac{n^2}{4} - \left((2^s-1)n - \tfrac{1}{3}4^s + 2^s - \tfrac{2}{3} - \frac{n(n+1)}{2}\right) = \\ &= \tfrac{3}{4}n^2 - (2^s-\tfrac{3}{2})n + \tfrac{1}{3}4^s - 2^s + \tfrac{2}{3} = \\ &= \frac{3}{4}\left(n-\frac{2^{s+1}-2}{3}\right)\left(n-\frac{2^{s+1}-4}{3}\right). \end{aligned}
Notice that the difference of the last two factors is less than 1, and one of them must be an integer: 2s+1−23\frac{2^{s+1}-2}{3} is integer if ss is even, and 2s+1−43\frac{2^{s+1}-4}{3} is integer if ss 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=2s+1−23n = \dfrac{2^{s+1}-2}{3} (ss is even) or n=2s+1−43n = \dfrac{2^{s+1}-4}{3} (ss is odd).

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 2–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;