How Many Values Can It Attain?
Let f be a function from the positive integers to the positive integers such that f ( m + n ) + 2 > f ( m ) + f ( f ( n ) ) for all positive integers m , n . Find the last three digits of the sum of all possible values of f ( 2 0 1 4 ) .
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
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
I think functions like
f ( 3 t ) = f ( 3 t + 1 ) = 3 t + 1
f ( 3 t + 2 ) = 3 t + 2
for some t ∈ N ∪ { 0 }
would satisfy the conditons given in the question and violate the criteria f ( n ) ≤ 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.
f ( 1 ) = 1
P r o o f .
L e t f ( 1 ) = z . C l e a r l y z ∈ N . A s s u m e z > 1
f ( m + 1 ) − f ( m ) > f ( f ( 1 ) ) − 2 ∀ m ∈ N ⟹ ∑ 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
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
0 > ( z − 2 ) ( f ( z ) − 1 )
B y o u r a s s u m p t i o n 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 .
⟹ z ≥ 3
⟹ f ( z ) < 1
C o n t r a d i c t i o n
f ( 1 ) = 1
It is easy to see the function f is non-decreasing.
Claim: f ( n ) ≤ n for all n
Assume for contradiction that for some n we have that 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 and f ( 2 n ) ≥ 2 n + 2 k .
Repeating this argument sufficiently often we can find an N such that f ( N ) = N + r where r > n
Since f ( N + r ) + 2 > f ( r ) + f ( f ( N ) ) = f ( r ) + f ( N + r ) and we have f ( r ) < 2 , so f ( r ) = 1 . Because f ( n ) is non-decreasing and r > n we must have f ( n ) ≤ f ( r ) = 1 , so f ( n ) = 1 .
But this is a contradiction, because we defined n to be such that f ( n ) > n .
We hence have that f ( n ) ≤ n for all n .
It is easy to verify that any sequence of the form 1 , 1 , 1 , … 1 , 2 , 3 , 4 , … satisfies the condition. So f ( 2 0 0 1 4 ) can take any value between 1 and 2014.