Функция натурального аргумента

[wpoms.]

Функция `f`, определенная на множестве натуральных чисел `NN`, удовлетворяет следующим условиям: (a) `f(1) = 1`; (b) `f(2n) = f(n)` и `f(2n + 1) = f(2n) + 1` для всех `n in NN`. Найдите наибольшее значение функции на отрезке `[1; 1989]`, а так же количество точек отрезка, в которых оно принимается.

@темы: Задачи на экстремум

Comments

[Adjirranirr]

Было уже где-то.
`f(\cdot)` — сумма цифр числа в двоичной записи. В самом деле, очевидно, что функция определена однозначно значением `f(1)`; сумма цифр в двоичной системе удовлетворяет `\text{sod}_2(2n) = \text{sod}_2(n)` и `\text{sod}_2(2n + 1) = \text{sod}_2(2n) + 1`. А так как `\text{sod}_2 (1) = f(1)`, то `\text{sod}_2 (n) \equiv f(n)`
Очевидно, сумма двоичных цифр числа не превышает количества цифр в этом числе; т.е., `f(n) <= log_2 (n) + 1` и при `n \in [1;\ 1989]` `f(n) <= log_2 (1989) + 1 < 12`. Таким образом, максимальное значение не превышает `11`. Но первое число с `f(n) = 11` есть `11111111111_2 = 2^{11} - 1 = 2047 > 1989`, и, следовательно, сумма цифр `11` не достигается. При этом, так как `f(1023) = f(1535) = f(1791) = f(1919) = f(1983) = 10`, `max_{n \in [1;\ 1989]} f(n) = 10` и достигается на `5` значениях.