Monday, August 8, 2011

More maths from IMO 2011

Last week I was looking for something on Google. The reason I can't remember what I was looking for is the IMO website (International Mathematical Olympiad) that "accidently" was returned in the search results. So I stuck on resolving one of the exercises for ... 3 days!!!

The problem that attracted my attention was number 3 from IMO 2011:

For any function ƒ:R→R that satisfies:

ƒ(x+y)≤y⋅ƒ(x)+ƒ(ƒ(x)), for ∀x,y∈R

prove that ƒ(x)=0, for all x≤0.

Here is the solution. Few inequalities that will be used later first:

- y=0 ⇒ ƒ(x)≤ƒ(ƒ(x)) (1)

- x=0 ⇒ ƒ(y)≤y⋅ƒ(0)+ƒ(ƒ(0)) ≡ ƒ(x)≤x⋅ƒ(0)+(ƒ(0)) (2)

- ƒ(0)=ƒ(x+(-x))≤-x⋅ƒ(x)+ƒ(ƒ(x)) ≡ ƒ(0)+x⋅ƒ(x)≤ƒ(ƒ(x)) (3)

- ƒ(ƒ(x))=ƒ(x+ƒ(x)-x)≤[ƒ(x)-x]⋅ƒ(x)+ƒ(ƒ(x)) ≡ [ƒ(x) - x]⋅ƒ(x)≥0 (4)

Let's note ƒ(0)=c and rewrite/expand the above expressions:

- from (1) ⇒ c≤ƒ(c) (1A)

- from (2) ⇒ ƒ(x)≤x⋅c+ƒ(c) (2A)

- from (3) ⇒ c+x⋅ƒ(x)≤ƒ(ƒ(x)) (3A)

- from (1) and (2A) ⇒ ƒ(x)≤ƒ(ƒ(x))≤ƒ(x)⋅c+ƒ(c) or ƒ(x)≤ƒ(x)⋅c+ƒ(c) (5)

- from (5), if x=c ⇒ ƒ(c)⋅c≥0 (6)

All these are true for ∀x∈R. Let's prove that c=0.

1. First of all, let's suppose c<0.

From (6) ⇒ ƒ(c)≤0.

From (5) ⇒ ƒ(x)⋅[1-c]≤ƒ(c)≤0. 1–c>1, from which we have ƒ(x)⋅[1-c]≤0 ≡ ƒ(x)≤0, for ∀x∈R.

From (4) and because ƒ(x)≤0 ⇒ ƒ(x)–x≤0 ≡ ƒ(x)≤x, for ∀x∈R. Considering this and (1A) ⇒ c≤ƒ(c)≤c ⇒ ƒ(c)=c.

From (3A) and x=c ⇒ c+c⋅ƒ(c)<ƒ(ƒ(c)) ≡ c+c2≤c ≡ c2≤0 ⇒ c=0 - contradiction.

2. Let's suppose c>0.

From (1A) ⇒ 0<c≤ƒ(c).

From (2A) we have ƒ(x)≤x⋅c+ƒ(c), where x⋅c+ƒ(c) is a line with positive "c" as a coefficient (i.e. increasing line). This means that for ∀x≤-ƒ(c)⁄c ⇒ ƒ(x)≤x⋅c+ƒ(c)≤0 (*).

From (4) and (*) ⇒ ƒ(x)–x≤0 for ∀x≤-ƒ(c)⁄c or ƒ(x)≤x ≤-ƒ(c)⁄c (again, for ∀x≤-ƒ(c)⁄c). But because ƒ(x)≤-ƒ(c)⁄c ⇒ ƒ(ƒ(x))≤-ƒ(c)⁄c (**).

From (3A) and (**) ⇒ c+x⋅ƒ(x)≤ƒ(ƒ(x))≤-ƒ(c)⁄c, for ∀x≤-ƒ(c)⁄c. Both "c" and ƒ(c) are positive ⇒ x⋅ƒ(x)≤-[ƒ(c)⁄c]–c≤0 or x⋅ƒ(x)≤0 for ∀x≤-ƒ(c)⁄c. Because x is negative and (from (*)) ƒ(x) is negative ⇒ x⋅ƒ(x)≥0. So, 0≤x⋅ƒ(x)≤0, for ∀x≤-ƒ(c)⁄c. This is possible only if ƒ(x)=0, for ∀x≤-ƒ(c)⁄c (***).

From (*) and (***) ⇒ 0=ƒ(x)≤x⋅c+ƒ(c)≤0, for ∀x≤-ƒ(c)⁄c, which has sense only if c=0 - contradiction.

We proved that c=0 and ƒ(0)=0. As a result:

- from (2A) ⇒ ƒ(x)≤x⋅c+ƒ(c)=0 ≡ ƒ(x)≤0, for ∀x∈ R (2B).

- from (3A) ⇒ x⋅ƒ(x)≤ƒ(ƒ(x)), for ∀x∈R (3B).

From (2B) ⇒ for ∀x≤0, x⋅ƒ(x)≥0.

From (3B) ⇒ 0≤x⋅ƒ(x)≤ƒ(ƒ(x)), for ∀x≤0.

But ƒ(x)≤0 always (2B). So must be ƒ(ƒ(x))≤0 ⇒ 0≤x⋅ƒ(x)≤ƒ(ƒ(x))≤0, for ∀x≤0. From this ⇒ ƒ(x) = 0, for ∀x≤0.

Love this stuff :)