### Author Topic: A math puzzle  (Read 6660 times)

#### MrPuzzle

• Jr. Member
• Posts: 75
##### A math puzzle
« on: 八月 19, 2004, 11:22:08 am »
It seems everybody is on vacation for the past couple of weeks. The forum is quiet. I hope now that everyone is back, we can see some activities. Here's a math puzzle I find interesting.

------------------

The function f is defined on the set of positive integers and its values are positive integers. Given that f(n+1) > f(f(n)) for all n, prove that f(n) = n for all n.

#### Elixir

• Jr. Member
• Posts: 32
##### A math puzzle
« Reply #1 on: 八月 19, 2004, 06:43:53 pm »

A. The smallest f(n) can only be obtained when n=1, otherwise f(f(n-1)) will give a smaller number.
B. The 2nd smallest f(n) can only be obtained when n<>1, and when f(f(n-1)) is just the smallest number, so, f(n-1)=1. Since 1 is the smallest possible number, it tells us that the smallest number we assumed in A is just 1. Also, since f(n-1)=1=smallest, n=2.
C. The 3rd smallest f(n) can only be obtained when f(f(n-1)) is just the 2nd smallest number  (it cannot be the smallest number, otherwise by the same reasoning in B, n would be 2 and we already know f(2) is the 2nd smallest, not the 3rd), so f(n-1)=2. So, it tell us that the 2nd smallest number we assumed in B is just 2, also, this time, n=3.
.......
Each step i will tell us the (i-1)th smallest number in previous step is just i-1 and the ith smallest number can only be obtained when n=i.

#### sean

• Jr. Member
• Posts: 86
##### 一形式不同的解法
« Reply #2 on: 九月 03, 2004, 02:24:43 pm »

1  It is easy to prove by induction that  f(n)>=k  if  n>=k, for all k>0.
2, Let fk(n)=f(n+k)-k , n>0, k>=0.  We have:
fk(n+1)=f(n+1+k)-k> f(f(n+k))-k
=fk(f(n+k)-k)
=fk(fk(n))

3, For all k>=0, fk(1) must be 1 by the same argument as Elixir's A. That is to say, f(k+1)=k+1  for all k>=0.