Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1993 USAMO Problems/Problem 3

Revision as of 23:25, 13 April 2012 by Danielguo94 (talk | contribs) (→‎Solution)

Problem 3

Consider functions $f : [0, 1] \rightarrow \Re$ which satisfy

     (i)$f(x)\ge0$ for all $x$ in $[0, 1]$,
     (ii)$f(1) = 1$,
     (iii)     $f(x) + f(y) \le f(x + y)$ whenever $x$, $y$, and $x + y$ are all in $[0, 1]$.

Find, with proof, the smallest constant $c$ such that

$f(x) \le cx$

for every function $f$ satisfying (i)-(iii) and every $x$ in $[0, 1]$.

Solution

My claim: $c\ge2$


Lemma 1) $f\left(\left(\frac{1}{2}\right)^n\right)\le\left(\frac{1}{2}\right)^n$ for $n\in \mathbb{Z}, n\ge0$

For $n=0$, $f(1)=1$ (ii)

Assume that it is true for $n-1$, then $f\left(\left(\frac{1}{2}\right)^{n}\right)+f\left(\left(\frac{1}{2}\right)^{n}\right)\le f\left(\left(\frac{1}{2}\right)^{n-1}\right)\le \left(\frac{1}{2}\right)^{n-1}$

$f\left(\left(\frac{1}{2}\right)^{n}\right)\le \left(\frac{1}{2}\right)^{n}$

By principle of induction, lemma 1 is proven.


Lemma 2) For any $x$, $\left(\frac{1}{2}\right)^{n+1}<x\le\left(\frac{1}{2}\right)^n\le1$ and $n\in \mathbb{Z}$, $f(x)\le\left(\frac{1}{2}\right)^n$.

$f(x)+f\left(\left(\frac{1}{2}\right)^n-x\right)\le f\left(\left(\frac{1}{2}\right)^{n}\right)\le \left(\frac{1}{2}\right)^{n}$ (lemma 1 and (iii) )

$f(x)\le\left(\frac{1}{2}\right)^n$ (because $f\left(\left(\frac{1}{2}\right)^n-x\right)\ge0$ (i) )


$_\forall 0\le x\le 1$, $\left(\frac{1}{2}\right)^{n-1}\ge2x\ge \left(\frac{1}{2}\right)^n\ge f(x)$. Thus, $c=2$ works.


Let's look at a function $g(x)=\left\{\begin{array}{ll}0&0\le x\le \frac{1}{2};\\1&\frac{1}{2}<x\le1;\\\end{array}\right$ (Error compiling LaTeX. Unknown error_msg)

It clearly have property (i) and (ii). For $0\le x\le\frac{1}{2}$ and WLOG let $x\le y$, $f(x)+f(y)=0+f(y)\le f(y)$

For $\frac{1}{2}< x\le 1$, $x+y>1$. Thus, property (iii) holds too. Thus $g(x)$ is one of the legit function.


$\lim_{x\rightarrow\frac{1}{2}^+} cx \ge \lim_{x\rightarrow\frac{1}{2}^+} g(x)=1$

$\frac{1}{2}c>1$

$c>2$ but approach to $2$ when $x$ is extremely close to $\frac{1}{2}$ from the right side.

$\mathbb{Q.E.D}$

Resources

1993 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1993_USAMO_Problems/Problem_3&oldid=46316"