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

Difference between revisions of "1993 USAMO Problems/Problem 3"

m (Created page with '== Problem 3== Consider functions <math>f : [0, 1] \rightarrow \Re</math> which satisfy <table><tr> <td>     </td><td>(i)</td><td><math>f(x)\ge0</math> …')
 
(→‎Solution)
Line 19: Line 19:
 
== Solution==
 
== Solution==
  
−
Being typed up now-- 07:01 pm EDT 4/22
+
My claim: <math>c\ge2</math>
 +
 
 +
<br/>
 +
<b>Lemma 1</b>) <math>f\left(\left(\frac{1}{2}\right)^n\right)\le\left(\frac{1}{2}\right)^n</math> for <math>n\in \mathbb{Z}, n\ge0</math>
 +
 
 +
For <math>n=0</math>, <math>f(1)=1</math> (ii)
 +
 
 +
Assume that it is true for <math>n-1</math>, then <math>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}</math>
 +
 
 +
<math>f\left(\left(\frac{1}{2}\right)^{n}\right)\le \left(\frac{1}{2}\right)^{n}</math>
 +
 
 +
By principle of induction, <b>lemma 1 is proven</b>.
 +
 
 +
<br/>
 +
<b>Lemma 2</b>) For any <math>x</math>, <math>\left(\frac{1}{2}\right)^{n+1}<x\le\left(\frac{1}{2}\right)^n\le1</math> and <math>n\in \mathbb{Z}</math>, <math>f(x)\le\left(\frac{1}{2}\right)^n</math>.
 +
 
 +
<math>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}</math> (lemma 1 and (iii) )
 +
 
 +
<math>f(x)\le\left(\frac{1}{2}\right)^n</math> (because <math>f\left(\left(\frac{1}{2}\right)^n-x\right)\ge0</math> (i) )
 +
 
 +
<br/>
 +
 
 +
<math>_\forall 0\le x\le 1</math>, <math> \left(\frac{1}{2}\right)^{n-1}\ge2x\ge \left(\frac{1}{2}\right)^n\ge f(x)</math>. Thus, <math>c=2</math> works.
 +
 
 +
<br/>
 +
 
 +
Let's look at a function <math>g(x)=\left\{\begin{array}{ll}0&0\le x\le \frac{1}{2};\\1&\frac{1}{2}<x\le1;\\\end{array}\right </math>
 +
 
 +
It clearly have property (i) and (ii). For <math>0\le x\le\frac{1}{2}</math> and WLOG let <math>x\le y</math>, <math>f(x)+f(y)=0+f(y)\le f(y)</math>
 +
 
 +
For <math>\frac{1}{2}< x\le 1</math>, <math>x+y>1</math>. Thus, property (iii) holds too. Thus <math>g(x)</math> is one of the legit function.
 +
 
 +
<br/>
 +
 
 +
<math>\lim_{x\rightarrow\frac{1}{2}^+} cx \ge \lim_{x\rightarrow\frac{1}{2}^+} g(x)=1</math>
 +
 
 +
<math>\frac{1}{2}c>1</math>
 +
 
 +
<math>c>2</math> but approach to <math>2</math> when <math>x</math> is extremly close to <math>\frac{1}{2}</math> from the right side.
 +
 
 +
<P align="right"><math>\mathbb{Q.E.D}</math></P>
  
 
== Resources ==
 
== Resources ==

Revision as of 18:26, 22 April 2010

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

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 extremly 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=34371"