Click here to Skip to main content
Click here to Skip to main content
Technical Blog

Tagged as

More maths from IMO 2011

, 9 Aug 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
Solution to a Math problem.

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 Smile | :)

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

rtybase
Software Developer (Senior) Snappli Ltd.
United Kingdom United Kingdom
My name is Ruslan Ciurca. Currently I am a Software Developer at snappli.com.

Comments and Discussions

 
Suggestionneed formatting PinmemberShahriar Iqbal Chowdhury9-Aug-12 22:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.141015.1 | Last Updated 10 Aug 2012
Article Copyright 2012 by rtybase
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid