IMO 2013 #5
by Wolstenholme, Oct 28, 2014, 4:29 AM
Let 
be the set of all positive rational numbers. Let 
be a function satisfying the following three conditions:
(i) for all
, 
;
(ii) for all, 
;
(iii) there exists a rational number
such that 
.
Prove that
for all 
.
Proof:
Before I start, I want to discuss motivation (all of the below will be un--rigorous). Basically, property (i) says the function is growing slowly while property (ii) says the function is growing quickly. So what we're eventually going to want to do is assume
or 
for some 
and derive a contradiction. The first thing I noticed when looking at this problem was that after applying property (ii) a bunch of times, we could get 
for all 
. After that I started getting annoyed since if 
could be negative, bad things happened. So then I proved this couldn't occur and the proof basically followed. Without further adieu, here is the proof!
Lemma 1:
Proof: Property (ii) gives
and since 
we get that as desired.
Lemma 2: for all
Proof: Applying Lemma 1 and property (ii) multiple times immediately yields the desired result.
Lemma 3:
for all 
Proof: Assume the contrary, so that
for some 
. Then property (i) gives that 
and since by Lemma 2 we have that 
and 
are positive, we have a contradiction as desired.
Lemma 4:
for all
Proof: Note that Lemma 3 implies that is strictly increasing. Now, assume for the sake of contradiction that there exists an 
such that . Let 
. Then by repeated applications of property (ii) we have that 
for all . Now it's clear that there exist 
such that 
. Then since is strictly increasing we have that 
. But by property (i) 
, contradiction!
Now consider any two. By property (i) we have that 
. But by property (ii) we also have that 
. Therefore 
for all 
as desired.
be the set of all positive rational numbers. Let 
be a function satisfying the following three conditions:(i) for all
, 
;(ii) for all
, 
;(iii) there exists a rational number
such that 
.Prove that
for all 
.Proof:
Before I start, I want to discuss motivation (all of the below will be un--rigorous). Basically, property (i) says the function is growing slowly while property (ii) says the function is growing quickly. So what we're eventually going to want to do is assume
or 
for some 
and derive a contradiction. The first thing I noticed when looking at this problem was that after applying property (ii) a bunch of times, we could get 
for all 
. After that I started getting annoyed since if 
could be negative, bad things happened. So then I proved this couldn't occur and the proof basically followed. Without further adieu, here is the proof!Lemma 1:
Proof: Property (ii) gives
and since 
we get that as desired.Lemma 2:
for all Proof: Applying Lemma 1 and property (ii) multiple times immediately yields the desired result.
Lemma 3:
for all 
Proof: Assume the contrary, so that
for some 
. Then property (i) gives that 
and since by Lemma 2 we have that 
and 
are positive, we have a contradiction as desired.Lemma 4:
for all Proof: Note that Lemma 3 implies that
is strictly increasing. Now, assume for the sake of contradiction that there exists an 
such that . Let 
. Then by repeated applications of property (ii) we have that 
for all . Now it's clear that there exist 
such that 
. Then since is strictly increasing we have that 
. But by property (i) 
, contradiction!Now consider any two
. By property (i) we have that 
. But by property (ii) we also have that 
. Therefore 
for all 
as desired.
August 2016
June 2016