PUMaC 2014 · 团队赛 · 第 7 题

PUMaC 2014 — Team Round — Problem 7

[ 6 ] Let us consider a function f : N ! N for which f (1) = 1, f (2 n ) = f ( n ) and f (2 n + 1) = f (2 n ) + 1. Find the number of values at which the maximum value of f ( n ) is attained for integer n satisfying 0 < n < 2014. 1 2 6

解析

[ 6 ] Let us consider a function f : N → N for which f (1) = 1, f (2 n ) = f ( n ) and f (2 n + 1) = f (2 n ) + 1. Find the number of values at which the maximum value of f ( n ) is attained for integer n satisfying 0 < n < 2014. Solution: 2 Function is the number of 1 in the binary representation of the number. 1023 = 1111111111 (10 1s). For 11 1s, one will need 2047, which is greater than 2014. We see that 2015 = 11111011111 and hence only 5 values satisfies f ( n ) = 10. 1 2 6