Chủ đề này có 1 trả lời

[Nguyen Tang Sy]

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] $

Bài viết đã được chỉnh sửa nội dung bởi Nguyen Tang Sy: 23-05-2014 - 17:49

[TMW]

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