The Student Room Group

Maths Problem of the week

Suppose f is a function from positive integers to positive integers satisfying f(1)=1, f(2n)=f(n) and f(2n+1)=f(2n)+1, for all positive integers of n.

Find the maximum of f(n) when n is greater than or equal to 1 and less than or equal to 1994.

So that is what it says on the back of a pack of HP paper i bought today. :biggrin:
Reply 1
Avatar for Smaug123
Smaug123
15
Original post by Zenarthra
Suppose f is a function from positive integers to positive integers satisfying f(1)=1, f(2n)=f(n) and f(2n+1)=f(2n)+1, for all positive integers of n.

Find the maximum of f(n) when n is greater than or equal to 1 and less than or equal to 1994.

So that is what it says on the back of a pack of HP paper i bought today. :biggrin:

Nice puzzle - took me thirty seconds or so :smile:
Original post by Zenarthra
Suppose f is a function from positive integers to positive integers satisfying f(1)=1, f(2n)=f(n) and f(2n+1)=f(2n)+1, for all positive integers of n.

Find the maximum of f(n) when n is greater than or equal to 1 and less than or equal to 1994.

So that is what it says on the back of a pack of HP paper i bought today. :biggrin:


So far I have f(1023)=10. Haven't found any larger value for f. Still trying to prove it.
Reply 3
Avatar for Flauta
Flauta
9
Yeah got it, took me a few minutes
Reply 4
Avatar for Smaug123
Smaug123
15
Original post by brianeverit
So far I have f(1023)=10. Haven't found any larger value for f. Still trying to prove it.


Key idea in spoiler:

Spoiler

Can I get a hint as to how to approach this question?

Spoiler


Also, what label would this type of question fall under i.e. calculus, number theory, geometry etc. ?
(edited 10 years ago)
Reply 6
Avatar for Smaug123
Smaug123
15
Original post by Khallil
Can I get a hint as to how to approach these questions?

So far I've eliminated f(1),f(2),f(4),...,f(512),f(1024)f(1), f(2), f(4), ..., f(512), f(1024) since they all equal unity as a result of the rule f(2n)=f(n)f(2n) = f(n)

f is actually a very simple function. Because you know what f(power of 2) is, you then know what f(1+power of 2) is. f(2+ power of 2) is f(2*(1+ another power of 2)) = f(1+power of 2). f(3 + power of 2) = f(1+(2+power of 2)) = 1+f(1+power of 2). Does this suggest a pattern?
Reply 7
Avatar for Smaug123
Smaug123
15
Original post by Khallil
Also, what label would this type of question fall under i.e. calculus, number theory, geometry etc. ?

Hmm. I wouldn't label it much in particular, other than "brainteaser".
Reply 8
Avatar for Dilzo999
Dilzo999
19
Did it :smile:. Took me about 10 minutes though, still unbelievable smaug did it in 30secs but he's in almost every step thread so no surprise :biggrin:.
Reply 9
Avatar for TenOfThem
TenOfThem
18
Original post by Khallil
Can I get a hint as to how to approach this question?

Spoiler


Also, what label would this type of question fall under i.e. calculus, number theory, geometry etc. ?


Numbers and Groups
Original post by Smaug123
Nice puzzle - took me thirty seconds or so :smile:


you going to study maths or something! 30 seconds!! :O
Reply 11
Avatar for Smaug123
Smaug123
15
Original post by ArabianPhoenix
you going to study maths or something! 30 seconds!! :O

I do study maths :smile:

Original post by Dilzo999
Did it :smile:. Took me about 10 minutes though, still unbelievable smaug did it in 30secs but he's in almost every step thread so no surprise :biggrin:.

It feels like quite a STEP-y question. "Here is a weird function. What is it really doing?"
Original post by Smaug123
I do study maths :smile:


It feels like quite a STEP-y question. "Here is a weird function. What is it really doing?"


I had realised that f(n) = sum of digits in binary representation but have you got a rigorous proof?
Reply 13
Avatar for Smaug123
Smaug123
15
Original post by brianeverit
I had realised that f(n) = <thing> but have you got a rigorous proof?

I'd spoiler that, I think.

Spoiler

Reply 14
Avatar for Smaug123
Smaug123
15
Original post by brianeverit
I had realised that f(n) = <thing> but have you got a rigorous proof?

Ah, you wanted a rigorous proof that the answer is what it is, not that f = thing? Here goes:

Spoiler

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you