Step by step ... Informazioni sulle gare, come allenarsi, chi corrompere.

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




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

Комментарии
15.08.2013 в 15:06

Только дурак нуждается в порядке — гений господствует над хаосом.
Было уже где-то.
`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` значениях.