How Many Values Can It Attain?

Algebra Level 5

Let f f be a function from the positive integers to the positive integers such that f ( m + n ) + 2 > f ( m ) + f ( f ( n ) ) f(m+n) + 2 > f(m) + f(f(n)) for all positive integers m , n . m,n. Find the last three digits of the sum of all possible values of f ( 2014 ) . f(2014).

Details and assumptions

  • The inequality is strict.
  • This problem is not original.
  • A typo has been fixed. Sorry for the inconvenience.


The answer is 105.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

David Vaccaro
Jul 17, 2014

It is easy to see the function f f is non-decreasing.

Claim: f ( n ) n f(n)\leq n for all n n

Assume for contradiction that for some n n we have that f ( n ) = n + k , k > 0 f(n)=n+k, k>0

Now f ( 2 n ) + 2 > f ( n ) + f ( f ( n ) ) = n + k + f ( n + k ) = n + k + f ( n ) + f ( f ( k ) ) = 2 n + 2 k + f ( f ( k ) ) 2 n + 2 k + 1 f(2n)+2>f(n)+f(f(n))=n+k+f(n+k)\\=n+k+f(n)+f(f(k))\\=2n+2k+f(f(k))\\\geq 2n+2k+1 and f ( 2 n ) 2 n + 2 k f(2n)\geq 2n+2k .

Repeating this argument sufficiently often we can find an N N such that f ( N ) = N + r f(N)=N+r where r > n r>n

Since f ( N + r ) + 2 > f ( r ) + f ( f ( N ) ) = f ( r ) + f ( N + r ) f(N+r)+2>f(r)+f(f(N))= f(r)+f(N+r) and we have f ( r ) < 2 f(r)<2 , so f ( r ) = 1 f(r)=1 . Because f ( n ) f(n) is non-decreasing and r > n r>n we must have f ( n ) f ( r ) = 1 f(n)\leq f(r)=1 , so f ( n ) = 1 f(n)=1 .

But this is a contradiction, because we defined n n to be such that f ( n ) > n f(n)>n .

We hence have that f ( n ) n f(n)\leq n for all n n .

It is easy to verify that any sequence of the form 1 , 1 , 1 , 1 , 2 , 3 , 4 , 1,1,1,\dots 1,2,3,4,\dots satisfies the condition. So f ( 20014 ) f(20014) can take any value between 1 and 2014.

Hari Govind
Jun 28, 2014

given the inequality holds for the set of all positive integers. Therefore we cant find any m+n such that m+n=1 therefore we set f(1)=1 now working accordingly we can see that the function is same as equality function hence the last three digits is that of the sum of all numbers till 2014

Hey can you describe in detail your solution. For example how did you show that

f ( n ) n n N f(n) \leq n \hspace{1cm} \forall n \in \mathbb{N}

I think functions like

f ( 3 t ) = f ( 3 t + 1 ) = 3 t + 1 f(3t)=f(3t+1)=3t+1

f ( 3 t + 2 ) = 3 t + 2 f(3t+2)=3t+2

for some t N { 0 } t \in \mathbb{N} \cup \{0\}

would satisfy the conditons given in the question and violate the criteria f ( n ) n f(n) \leq n . This is can be done for any number not just 3, thus f(n) can also take values like n+1 as shown in the above example.

Sushant Vijayan - 6 years, 11 months ago

Log in to reply

It must read

*for any t N { 0 } t \in \mathbb{N} \cup \{0\}

Sushant Vijayan - 6 years, 11 months ago

f ( 1 ) = 1 f(1)=1

P r o o f . Proof.

L e t f ( 1 ) = z . C l e a r l y z N . A s s u m e z > 1 \hspace{1.48cm} Let\, f(1)=z. Clearly\, z \in \mathbb{N}.Assume\, z>1

f ( m + 1 ) f ( m ) > f ( f ( 1 ) ) 2 m N \hspace{1cm}f(m+1)-f(m)>f(f(1))-2\hspace{1cm} \forall m \in \mathbb{N} m = 1 m = z 1 f ( m + 1 ) f ( m ) > ( z 1 ) ( f ( z ) 2 ) \implies \sum _{m=1} ^{m=z-1} f(m+1)-f(m)>(z-1)(f(z)-2)

T h e s u m i s a t e l e s c o p i c s e r i e s . N o t i n g t h i s w e g e t The\,sum\,is\,a\,telescopic\,series.Noting\,this\, we \,get

f ( z ) z > ( z 1 ) ( f ( z ) 1 ) \hspace{1cm}f(z)-z>(z-1)(f(z)-1)

R e w r i t i n g t h i s i n e q u a l i t y w e g e t Rewriting\,this\,inequality\,we\,get

0 > ( z 2 ) ( f ( z ) 1 ) \hspace{1cm}0>(z-2)(f(z)-1)

B y o u r a s s u m p t i o n z > 1 By\,our\,assumption\,z>1

T h e a b o v e i n e q u a l i t y i s s t r i c t w h i c h m e a n s z 2. The\, above\, inequality\, is\, strict\, which\, means\, z\neq 2.

z 3 \implies z\geq 3

f ( z ) < 1 \implies f(z)<1

C o n t r a d i c t i o n Contradiction

f ( 1 ) = 1 \boxed{f(1)=1}

Sushant Vijayan - 6 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...