A brief math problem

MATHEMATICS

Q1. Suppose f is a function from positive integers to positive integers satisfying (I) f(1)=1,(II) f(2n)=f(n), and (III) f(2n+1)=f(2n)+1, for all positives integers n. Find the maximum of f(n) when n is grater than or equal to 1 and less than or equal to 1994. 

Ans.: 

First of all, let’s organize the things a little bit. Instead of 

f(2n+1)=f(2n)+1, we’re gonna change it into (IV) f(2n+1)=f(n)+1 (II on I)  Furthermore, let’s see if we find out a pattern on the f(n) value by testing 10 possibilities (1≤𝑛 ≤5).

Note: You’re gonna notice that we can find f(n) for every n in the domain, once we already have f(1), and all the values to n even and n odd.

•      f(1)=1

•      For n=1: f(2)=f(1)=1 (comes from II)               

                   f(3)=f(2)+1=2 (comes from III)   

•      For n=2: f(4)=f(2)=1

                    f(5)=f(2)+1=2

•      For n=3: f(6)=f(3)=2                

                   f(7)=3

•      For n=4: f(8)=f(4)=1

                       f(9)=2

•      For n=5: f(10)=f(5)=2                

                            f(11)=3

   What we can extract from the topics above is that the maximum in a series of numbers always shows up first when you pick an odd number in the domain. For instance, in crescent order, the first maximum is f(3)=2, the second maximum is f(7)=3. Note that f(11) IS NOT THE THIRD MAXIMUM once 3 has already appeared. It happens because if your number in the domain is an even number, f(e), where e is an even number, equals to f(e/2), so you’ll never have a brand new maximum in this situation. Whereas, if you pick an odd number, f(o), where o is an odd number, equals to f(e/2) +1, so it could be a brand new maximum. 

   

So, let’s see if we find out an algorithm that show us when there is a brand new maximum. Note that we can find other b.n.m (brand new maximum) when we have (V) f(2(l.b.n.d.)+1)=f(l.b.n.d.)+1 (from IV), where l.b.n.d. is the last brand new domain. Let’s analyze: 

First b.n.m: f(3)=2

Second b.n.m: f(7)=3, “l.b.n.d = 3”

Third b.n.m: f(2(7) + 1) = f(15) = f(7) + 1 = 4, “l.b.n.d = 7”

Fourth b.n.m: f(2(15) + 1) = f(31) = 5, “l.b.n.d=15”

So what we can see is that, 𝑓(2^𝑎−1)=𝑎, where a is a b.n.m.

If n goes up to 1994, if we want to see what’s the maximum f(n), we must find 2^𝑎−1 value, which must be the closest to 2(1994) +1. So a, in this case, equals to 11.

So f(2047)=11, is the maximum.