Zbiór zadań, (zadania różne)
Zadanie 331
Niech $f(n)$ równe jest liczbie par kolejnych jedynek w binarnej reprezentacji liczby naturalnej $n$.
Oblicz $f(1) + f(2) + f(3) + \ldots + f(2014)$.
Rozwiązanie
Niech $A_n$ to zbiór $n$-bitowych liczb, a $S_n$ to suma wartości $f(n)$ wszystkich $n$-bitowych liczb.
Liczby:
- jednobitowe: $S_1=0$
- dwubitowe: $10_2$, $11_2 \rightarrow S_2=1$
- trzybitowe: $100_2$, $101_2$, $110_2$, $111_2 \rightarrow S_3=3$
- czterobitowe: $1000_2$, $1001_2$, $1010_2$, $1011_2$, $1100_2$, $1101_2$, $1110_2$, $1111_2 \rightarrow S_4=8$
Liczby $A_{n+1}$ powstają przez dodanie bitu $1$ lub $0$ do liczb $A_{n}$, więc każda liczba $A_{n}$ generuje dwie liczby $A_{n+1}$. Stąd $S_{n+1} = 2S_n +$ nowe pary, których jest $2^{n-2}$.
$S_{n+1} = 2S_n + 2^{n-2}$, dla $n \ge 2$.
Liczba $2014=11111011110_{(2)}$ w postaci binarnej składa się z 11 bitów. Liczby $12$-bitowe rozpoczynają się od $2^{11}=2048$, stąd rozwiązaniem jest $S_1 + S_2 + \ldots +S_{11} - \sum_{n=2015}^{2048} f(n)$.
$S_{1} = 0$
$S_{2} = 1$
$S_{3} = 2 \cdot 1 + 1 = 3$
$S_{4} = 2 \cdot 3 + 2 = 8$
$S_{5} = 2 \cdot 8 + 4 = 20$
$S_{6} = 2 \cdot 20 + 8 = 48$
$S_{7} = 2 \cdot 48 + 16 = 112$
$S_{8} = 2 \cdot 112 + 32 = 256$
$S_{9} = 2 \cdot 256 + 64 = 576$
$S_{10} = 2 \cdot 576 + 128 = 1280$
$S_{11} = 2 \cdot 1280 + 256 = 2816$
$\sum_{n=2015}^{2048} f(n) = 216$
Ostatecznie otrzymujemy $\sum_{i=0}^{11} S(i)- \sum_{n=2015}^{2048} f(n) = 5120 - 216 = 4904$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>