Suppose f is a function such that \( f:\mathbb{Z} ^+\to \mathbb{Z} ^+ \) satisfying

\(f(1)=1, f(2n)=f(n)\) and \(f(2n+1)=f(2n)+1\),

for all positive integers \(n\).

Find the maximum of \(f(n)\) when \( 1 \leq n \leq 2013\).

Suppose f is a function such that \( f:\mathbb{Z} ^+\to \mathbb{Z} ^+ \) satisfying

\(f(1)=1, f(2n)=f(n)\) and \(f(2n+1)=f(2n)+1\),

for all positive integers \(n\).

Find the maximum of \(f(n)\) when \( 1 \leq n \leq 2013\).

No vote yet

11 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewest\(f(n)\) is the number of \(1\)s in the binary expansion of \(n\). Since \(2^{11} = 2048\), the smallest integer \(n\) with \(f(n) = 11\) is \(2047\). Since \(f(1983) = 10\), the maximum of \(f(n)\) over \(1 \le n \le 2013\) is \(10\). – Mark Hennings · 3 years, 9 months ago

Log in to reply

But, yes, although it would have sufficed simply to use \(2^{10}-1\) (since there cannot be any more \(1\)s, as this number would then be \(2^{11}-1\)).

The argument for the sum of the digits of the binary expansion can be seen by simple construction

(this is just a quick, non-rigorous sketch)of a two-case inductive proof:Allow the number \(n\) to be of the form \(n=a_k2^{k-1}+a_{k-1}2^{k-2}+\cdots+a_1\), where \(a_i\in\{0,1\}\) and \(a_k=1\).

Case 1Then, if this number is odd, we must have \(a_1=1\), hence, we have \(f(2m+1)=f(2m)+1\) for some \(m\in\mathbb{Z}\). So, now our number becomes: \[ 2m+1=a_k2^{k-1}+a_{k-1}2^{k-2}+\cdots+a_22^{1}+1 \] \[ m=a_k2^{k-2}+a_{k-1}2^{k-3}+\cdots+a_2 \] This adds unity to our count, removes the last digit, and continues the process until the only value left of \(m\) is one.

Case 2Say that \(n\) is even, then we must have \(a_1=0\). Clearly, then, we have: \(f(2m)=f(m)\), which, after dividing, gives us a new number with the last digit removed and adds nothing to the count (as the last digit is 0 in base 2).

The same process applies.

Hence, we are done (note that this proof can easily be extended for uniqueness of definition as Paramjit S.'s request).

Hopefully this makes the case a little more clear for those in doubt. – Guillermo Angeris · 3 years, 9 months ago

Log in to reply

– Paramjit Singh · 3 years, 9 months ago

This function doubtlessly suffices the condition, & the solution is beautiful. But is this definition of \(f(n)\) unique? Why?Log in to reply

– Mark Mottian · 3 years, 9 months ago

Please help me solve my problem above!Log in to reply

– Mark Hennings · 3 years, 9 months ago

Prove it by (strong) induction on \(n\).Log in to reply

We start with f(1), or "1" in binary. The f(2n) equation will tell us what f provides when we append 0 to our input, that is, f(10), and f(2n+1) tells us what happens when we append a 1.

e.g. f(110101) is computed by f(1) --> f(11) --> f(110) --> f(1101) --> f(11010) --> f(110101).

(all numbers in binary) – Alex Meiburg · 3 years, 9 months ago

Log in to reply

While preparing for the South African National Olympiad, the following problem featured in my training material:

"An 11 sided polygon has its vertices on a circle. How many triangles can be formed using three vertices of the polygon but sharing no side with a side of the polygon?"

Can somebody please provide a solution?

Thanks! – Mark Mottian · 3 years, 9 months ago

Log in to reply

– Rajarshi Chatterjee · 3 years, 9 months ago

a very good thing indeed.good work Mark H.Log in to reply

1009! – Neerad Nandan · 3 years, 9 months ago

Log in to reply

– Paramjit Singh · 3 years, 9 months ago

Sorry, it's not 1009 factorial. :) Lol Careful with the !Log in to reply

Is it 11? – Daniel Leong · 3 years, 9 months ago

Log in to reply