wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Function
        
(Message started by: Grisha_Perelman on Feb 21st, 2007, 7:24pm)
Title: Function
Post by Grisha_Perelman on Feb 21st, 2007, 7:24pm
Find all functions f:N->N such that f(n+1)=f(f(n))+1 for all n in N.

Note: N = {1,2,...} is,  of course, the set of natural numbers.
Title: Re: Function
Post by Icarus on Feb 22nd, 2007, 7:10am
I don't have it yet, but it is interesting to note that if f has this property, then so does f[2] = fhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/smallcirc.giff, and more generally f[2^k].
Title: Re: Function
Post by Grimbal on Feb 22nd, 2007, 8:07am
And even f[2k]
Title: Re: Function
Post by Grisha_Perelman on Feb 22nd, 2007, 1:47pm

on 02/22/07 at 07:10:34, Icarus wrote:
I if f has this property, then so does f[2] = fhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/smallcirc.giff, and more generally f[2^k].


Your statement is, of course, incorrect.
In fact, [hide]one can prove that the solution is unique.[/hide]
Title: Re: Function
Post by Grisha_Perelman on Feb 22nd, 2007, 1:48pm

on 02/22/07 at 08:07:06, Grimbal wrote:
And even f[2k]


Your statement is, of course, incorrect.
In fact, [hide]one can prove that the solution is unique.[/hide]
Title: Re: Function
Post by Icarus on Feb 22nd, 2007, 2:06pm
To the contrary - both of our statements are correct (I actually started to publish Grimbal's version but foolishly confused myself into thinking only the powers of 2 worked instead of all even "exponents").

Think about it. You know what the solution is. Try it out!
Title: Re: Function
Post by Grisha_Perelman on Feb 22nd, 2007, 3:05pm

on 02/22/07 at 14:06:03, Icarus wrote:
Think about it. You know what the solution is. Try it out!


Yes, i know what the unique solution f is and f  \dot f is not the solution.
If you could write a proof of your claim I would be able to show you where you go wrong.
Title: Re: Function
Post by Icarus on Feb 22nd, 2007, 3:15pm
Yes it is. Calculate out what f(f(n)) is, please, before responding again.
Title: Re: Function
Post by JohanC on Feb 22nd, 2007, 3:16pm
Maybe f and fhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/smallcirc.giff are necessarily equal?
Title: Re: Function
Post by Grisha_Perelman on Feb 22nd, 2007, 3:58pm

on 02/22/07 at 15:15:39, Icarus wrote:
Yes it is.

Yes, you are right. Sorry.
Title: Re: Function
Post by Grisha_Perelman on Feb 22nd, 2007, 3:59pm

on 02/22/07 at 15:16:34, JohanC wrote:
Maybe f and fhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/smallcirc.giff are necessarily equal?


That's a very good observation/question! Proof?
Title: Re: Function
Post by Icarus on Feb 22nd, 2007, 4:07pm
It happens to me regularly. I'm so sure of what I know that I fail to check if I'm missing something.

For the record, the calculation I did was

f( f(n+1) ) = f( f(f(n))+1 ) = f(f( f(f(n)) ))+1.

However, since one solution of the problem is obvious, I knew exactly why my calculation didn't contradict your claim of uniqueness.

Finding the solution is easy. Proving the uniqueness, I'm still working on.
Title: Re: Function
Post by Grisha_Perelman on Feb 22nd, 2007, 4:20pm

on 02/22/07 at 16:07:14, Icarus wrote:
Proving the uniqueness, I'm still working on.


I now wonder if it's possible to construct a uniqueness proof using JohanC's observation, which would be different from the proof I have.

P.S. I should have posted this problem to Math thread, but i'm here recently and I thought putnam one is for putnam only and not math in general.
Title: Re: Function
Post by Eigenray on Feb 22nd, 2007, 4:43pm
(*)  f(n+1) = f2(n) + 1.

As noted, if f satisfies (*), then f2 does too.

Claim: f is surjective.

Note that if y=f(x) is in the range of f, then y-1 = f2(x) is also in the range of f.  So either f is surjective or its range is a finite interval [1, M].  Then M is not in the range of f2, otherwise if M=f2(x), then M+1=f(x+1), contradiction.  But then f2 also satisfies (*) and has a strictly smaller range, leading to a contradiction by infinite descent.

Claim: f is injective.

Suppose f(x) = f(y), with x < y.  Then f(x+1) = f2(x)+1 = f2(y)+1 = f(y+1).  So if y=x+r, say, we find inductively f(n+r) = f(n) for all n>x, i.e., f is eventually periodic.  In particular, its range is finite, contradiction.

Claim: if f(n)=n for some n, then f(x)=x for all x.

Proof: Let n be the smallest n such that f(n)=n, and assume for a contradiction that n>1.  Since f(n+1) = f2(n) + 1 = n+1, we have f(x)=x for all x in [n, $infty$).  Since f is a bijection, it must act as a permutation of the interval [1, n-1].  But n = f(n) = f2(n-1) + 1, so f2 fixes n-1.  By assumption, f doesn't fix n-1, which means that f contains a cycle of order 2, so its order as a permutation is even.

But fk(n+1) = f2k(n) + 1, so if f2k(n) = n for all n in [1, n-1], then fk(n) = n for all n in [2, n-1]; since it's a permutation, we have fk(1)=1 as well.  So if f2k is the identity, so is fk.  But this means the order of f is odd, a contradiction.

I'll work on it some more later.
Title: Re: Function
Post by Eigenray on Feb 22nd, 2007, 6:15pm
The above implies that f is a bijection of N consisting of cycles all of the same length.  But most of this is unnecessary.  I need only that f is surjective, and that if f(1)=1, then f(n)=n for all n.

Since f is surjective, pick k with f(k)=1.  If k>1, then

1 = f(k) = f((k-1)+1) = f2(k-1) + 1 > 1,

a contradiction.  So k=1, i.e., f(1)=1, and therefore f(n)=n for all n.
Title: Re: Function
Post by Icarus on Feb 22nd, 2007, 7:34pm

on 02/22/07 at 16:20:03, Grisha_Perelman wrote:
P.S. I should have posted this problem to Math thread, but i'm here recently and I thought putnam one is for putnam only and not math in general.


Don't worry about that. There are pure math problems scattered throughout the easy, medium, and hard forums. The question of what should go in the "Putnam" forum as opposed to the others is something we don't have a good answer to. This site has long since grown beyond its original intentions.


And thanks for the problem. It was nice.
Title: Re: Function
Post by Aryabhatta on Mar 6th, 2007, 11:44am
This reminds of an old IMO problem (i believe it was IMO 1977)

the condition there was f(n+1) > f(f(n)) for all n (f being defined on naturals and mapping to naturals)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board