1993 USAMO Problems/Problem 3: Difference between revisions

Revision as of 12:29, 4 July 2013

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

Discussion on AoPS/MathLinks

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

@@ Line 63: / Line 63: @@
 {{USAMO box|year=1993|num-b=2|num-a=4}}
 * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=356413#p356413 Discussion on AoPS/MathLinks]
+{{MAA Notice}}

Page

Toolbox

Search

1993 USAMO Problems/Problem 3: Difference between revisions

Revision as of 12:29, 4 July 2013

Problem 3

Solution

Resources