Author |
Topic: Function (Read 754 times) |
|
Grisha_Perelman
Newbie
Gender: 
Posts: 17
|
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.
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
 |
Re: Function
« Reply #1 on: Feb 22nd, 2007, 7:10am » |
 Quote  Modify
|
I don't have it yet, but it is interesting to note that if f has this property, then so does f[2] = f f, and more generally f[2^k].
|
| « Last Edit: Feb 22nd, 2007, 7:11am by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Function
« Reply #2 on: Feb 22nd, 2007, 8:07am » |
Quote Modify
|
And even f[2k]
|
|
IP Logged |
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Function
« Reply #3 on: Feb 22nd, 2007, 1:47pm » |
Quote Modify
|
on Feb 22nd, 2007, 7:10am, Icarus wrote:| I if f has this property, then so does f[2] = ff, and more generally f[2^k]. |
|
Your statement is, of course, incorrect.
In fact, one can prove that the solution is unique.
|
|
IP Logged |
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Function
« Reply #4 on: Feb 22nd, 2007, 1:48pm » |
Quote Modify
|
on Feb 22nd, 2007, 8:07am, Grimbal wrote:
Your statement is, of course, incorrect.
In fact, one can prove that the solution is unique.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Function
« Reply #5 on: Feb 22nd, 2007, 2:06pm » |
Quote Modify
|
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!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Function
« Reply #6 on: Feb 22nd, 2007, 3:05pm » |
Quote Modify
|
on Feb 22nd, 2007, 2:06pm, 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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Function
« Reply #7 on: Feb 22nd, 2007, 3:15pm » |
Quote Modify
|
Yes it is. Calculate out what f(f(n)) is, please, before responding again.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Function
« Reply #8 on: Feb 22nd, 2007, 3:16pm » |
Quote Modify
|
Maybe f and ff are necessarily equal?
|
|
IP Logged |
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Function
« Reply #10 on: Feb 22nd, 2007, 3:59pm » |
Quote Modify
|
on Feb 22nd, 2007, 3:16pm, JohanC wrote:Maybe f and ff are necessarily equal?
|
|
That's a very good observation/question! Proof?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Function
« Reply #11 on: Feb 22nd, 2007, 4:07pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grisha_Perelman
Newbie
Gender:
Posts: 17
|
|
Re: Function
« Reply #12 on: Feb 22nd, 2007, 4:20pm » |
Quote Modify
|
on Feb 22nd, 2007, 4:07pm, 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Function
« Reply #13 on: Feb 22nd, 2007, 4:43pm » |
Quote Modify
|
(*) 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Function
« Reply #14 on: Feb 22nd, 2007, 6:15pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Function
« Reply #15 on: Feb 22nd, 2007, 7:34pm » |
Quote Modify
|
on Feb 22nd, 2007, 4:20pm, 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.
|
| « Last Edit: Feb 22nd, 2007, 7:35pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Function
« Reply #16 on: Mar 6th, 2007, 11:44am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print