Cho hàm số $f(x)$ xác định trên tập hợp các số nguyên dương và nhận giá trị cũng trên tập đó và được xác định như sau:
$\left\{\begin{matrix} f(1) = 1 \\ f(2n) = f(n) \\ f(2n+1) = f(2n) + 1 \end{matrix}\right.$ $\forall n = 1,2...$
Tìm $max$ $f(n)$ với $n \in [1;2011] $
Gọi M là giá trị cần tìm
Ta dễ dàng nhận thấy f(n) chính là số chữ số 1 trong biểu diễn nhị phân của số thập phân n,
Như vậy, ta sẽ tìm số có biểu diễn nhị phân chứa nhiều chữ số 1 nhất
Ta nhận xét:
m = $\sum_{i=0}^{k}(ai.2^{i})$ trong đó ai là 0 hoặc 1
Số lượng các số ai = 1 chính là số chữ số "1" trong biểu diễn nhị phân của số m
VD: 3 = 1.2^1 + 1.2^0 => f(3) =2.
Ta có: 2^11 > 2011 nên các số từ 1 tới 2011 trong biểu diễn nhị phân chỉ có tối đa 11 chữ số
=> nên M <= 11.
Nếu M =11 thì số nhỏ nhất có biểu diễn nhị phân chứa 11 số "1" là 2047 ( loại)
Vậy M <=10. Ta thấy 1023 có biểu diễn nhị phân có 10 số "1" (thỏa)
Kết luận: M =10 là giá trị cần tìm