Author Topic: A math puzzle  (Read 6622 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.