Very interesting problem that puzzles me


by jdp
Tags: interesting, puzzles
jdp
jdp is offline
#1
Feb5-13, 08:36 PM
P: 3
One of my friends showed me this problem and I've been thinking about it all day. It's something like if f(2x) is equal to f(f(y)) and that f(2y) + 1 is f(2y +1) and f(0) is 0, what is f(n). It seems very maclaurin esque to me but... anyway... first post and pretty nice problem. Would love help figuring this beast out.
Phys.Org News Partner Mathematics news on Phys.org
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Simon Bridge
Simon Bridge is offline
#2
Feb5-13, 09:54 PM
Homework
Sci Advisor
HW Helper
Thanks ∞
PF Gold
Simon Bridge's Avatar
P: 11,070
Number them:
1. f(2x)=f(f(y))
2. f(2y)+1=f(2y+1)
3. f(0)=0

guessing: x,y,n are integers?
are x and y specific numbers or is just any arbitrary number?
i.e. does this also hold: ##f(2x+1)=f(2x)+1## ?

If so then I'd start from the observations:

#1 tells you f(f(n))=f(some even number).
#2 (with #3) tells you that if n is odd, then f(n)=f(n-1)+1
jfgobin
jfgobin is offline
#3
Feb6-13, 12:25 PM
P: 90
That looks weird. Are you sure there isn't something missing?

By #3, [itex]f(0)=0[/itex], using [itex]y=0[/itex], by #2, [itex]f(1)=1[/itex]. Using [itex]2y=1[/itex] and #2 again, [itex]f(2)=2[/itex], and so forth.

So at least for [itex]x \in \mathbb{N}[/itex], [itex]f(x)=x[/itex].

pwsnafu
pwsnafu is offline
#4
Feb6-13, 04:13 PM
Sci Advisor
P: 779

Very interesting problem that puzzles me


I think OP's problem is the following:

Find ##f : \mathbb{N} \to \mathbb{N}## satisfying
  1. ##f(0) = 0##,
  2. For each ##k \in \mathbb{N}## we have ##f(2k) = f(f(k))##,
  3. For each ##k \in \mathbb{N}## we have ##f(2k+1) = f(2k) + 1##.

At the very least it prevents the trivial solution.

Note: I'm including 0 in the naturals for this problem.
jdp
jdp is offline
#5
Feb6-13, 07:33 PM
P: 3
Yes, I clarified. Exactly like this. I just don't know where to start
Simon Bridge
Simon Bridge is offline
#6
Feb6-13, 08:24 PM
Homework
Sci Advisor
HW Helper
Thanks ∞
PF Gold
Simon Bridge's Avatar
P: 11,070
Have you had a play with the relations, looking at different numbers?

Using pwsnafu's formulation in post #4:

If ##f^{-1}\big ( f(k)\big )=k## is the inverse function in action,
then, from #2:
##f^{-1}\big ( f(2k)\big ) = f^{-1}\big ( f(f(k)\big ) \\ \Rightarrow f(k)=2k##
But that does not fit the other clues.

Notice: 2k is always even, 2k+1 is always odd.
... so the clues are telling you what happens in the case of odd or even n.

This is how you go about exploring mathematical relations - you end up making a list of things that the relations are telling you.
It's important that you get used to this process - after a bit you spot a pattern that looks likely and you set out to prove it.

eg.
What happens when you apply the formula to k=0?
What is f(f(2k))? f(f(2k+1))?
HallsofIvy
HallsofIvy is online now
#7
Feb7-13, 09:48 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,895
Quote Quote by pwsnafu View Post
I think OP's problem is the following:

Find ##f : \mathbb{N} \to \mathbb{N}## satisfying
  1. ##f(0) = 0##,
  2. For each ##k \in \mathbb{N}## we have ##f(2k) = f(f(k))##,
  3. For each ##k \in \mathbb{N}## we have ##f(2k+1) = f(2k) + 1##.

At the very least it prevents the trivial solution.

Note: I'm including 0 in the naturals for this problem.
Start by doing the obvious calculations. 1 is odd: 1= 2(0)+ 1 so f(1)= f(2(0)+ 1)= f(2(0))+ 1= f(0)+ 1= 1. 2 is even: 2= 2(1) so f(2)= f(f(1))= f(1)= 1. 3 is odd: 3= 2(1)+ 1 so f(3)= f(2(1)+ 1)= f(2(1))+ 1= f(2)+ 1= 1+ 1= 2. 4 is even: 4= 2(2) so f(4)= f(2(2))= f(f(2))= f(1)= 1. 5 is odd: 5= 2(2)+ 1 so f(5)= f(2(2)+ 1)= f(2(2))+ 1= f(4)+ 1= 1+ 1= 2.

You should be able to see a very easy pattern for f(n) when n is even and for f(n) when n is odd. And then use "proof by induction" to show that you are correct.


Register to reply

Related Discussions
Interesting problem, I almost got it right. Introductory Physics Homework 1
Inductance problem, puzzles professors Classical Physics 2
interesting problem Differential Equations 5
interesting problem General Math 18
Interesting Problem General Math 9