|
|
| (88 intermediate revisions by 5 users not shown) |
| Line 1: |
Line 1: |
| − | ==Introduction==
| + | wao |
| − | So I failed the AOIME. I don't really want to do any more AIME prep, so I have decided to go do some Oly prep :). Here's some oly notes/favorite problems
| |
| − | | |
| − | ==Disclaimer==
| |
| − | | |
| − | About half of these problems (?) are from the OTIS excerpts. I try to make mines easier to understand though you should probably just read the OTIS excerpts. These notes are to help me learn, though I don't mind if you read them.
| |
| − | | |
| − | ==Inequalities==
| |
| − | Yay! I love inequalities. Clever algebraic manipulation+thereoms is all you need. It all comes from experience though...
| |
| − | | |
| − | ==I.Basics==
| |
| − | | |
| − | AM-GM, Cauchy (Titu's Lemma as well), Muirhead, and Holder's.
| |
| − | These are cool, remember that these should only be used when the inequality is homogenized already.. These are all pretty easy to prove as well.
| |
| − | | |
| − | | |
| − | Example 1:
| |
| − | (Evan Chen) Let <math>a,b,c>0</math> with <math>\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1</math>. Prove that <math>(a+1)(b+1)(c+1) \geq 64</math>
| |
| − | | |
| − | Solution:
| |
| − | We need to try to homogenize this somehow. Plugging in the expression for on the LHS for <math>1</math> won't work. If we try to do something on the left side, we'll still have a degree <math>3>-1</math>. Wait a second, why are they all <math>a+1</math>'s? Let's try to get rid of the <math>a+1</math>'s first. Well, if we add <math>3</math> to both sides of the given condition, we get
| |
| − | | |
| − | <math>\frac{a+1}{a}+\frac{b+1}{b}+\frac{c+1}{c}=4</math>, <math>\frac{(a+1)(b+1)(c+1)}{abc} \geq \frac{64}{27}</math>,
| |
| − | <math>abc \geq 27</math>
| |
| − | | |
| − | By AM-GM.
| |
| − | Obviously the trivial solution <math>(3,3,3)</math> satisfies this, so we haven't made any silly mistakes. We still haven't homogenized, but now the path is clear. Multiplying both sides by
| |
| − | <math>(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})^3=1</math>, we get
| |
| − | | |
| − | <math>\frac{(ab+bc+ac)^3}{(abc)^2} \geq 27</math>, <math>(\frac{ab+bc+ac}{3})^3 \geq (abc)^2</math>, <math>(\frac{ab+bc+ac}{3}) \geq (abc)^{2/3}</math>
| |
| − | | |
| − | Which is true from AM-GM. We shall now introduce Muirhead's...
| |
| − | | |
| − | Example 2:
| |
| − | | |
| − | Let <math>a,b,c>0</math> (Again Evan Chen) and <math>abc=1</math>. Prove that <math>a^2+b^2+c^2 \geq a+b+c</math>.
| |
| − | | |
| − | Solution:
| |
| − | First we homogenize:
| |
| − | | |
| − | <math>a^2+b^2+c^2 \geq (a+b+c)(abc)^{1/3}</math>
| |
| − | | |
| − | Which is true because <math>(2,0,0)</math> majorizes <math>(\frac{4}{3}, \frac{1}{3}, \frac{1}{3})</math>
| |
| − | | |
| − | | |
| − | Cauchy:
| |
| − | | |
| − | Problem 1: (2009 usamo/4): For <math>n \ge 2</math> let <math>a_1</math>, <math>a_2</math>, ..., <math>a_n</math> be positive real numbers such that
| |
| − | <math> (a_1+a_2+ ... +a_n)\left( {1 \over a_1} + {1 \over a_2} + ... +{1 \over a_n} \right) \le \left(n+ {1 \over 2} \right) ^2 </math>
| |
| − | Prove that <math>\text{max}(a_1, a_2, ... ,a_n) \le 4 \text{min}(a_1, a_2, ... , a_n)</math>.
| |
| − | | |
| − | Try to solve this on your own! Very cute problem.
| |
| − | Note that you'll probably only ever need Holder's for <math>3</math> variables...
| |
| − | | |
| − | Example 3 (2004 usamo/5)
| |
| − | | |
| − | Let <math>a</math>, <math>b</math>, and <math>c</math> be positive real numbers. Prove that
| |
| − | <math>(a^5 - a^2 + 3)(b^5 - b^2 + 3)(c^5 - c^2 + 3) \ge (a+b+c)^3</math>.
| |
| − | | |
| − | Solution:
| |
| − | | |
| − | 1. The <math>(a+b+c)</math> is cubed, so we try to use Holder's. The simplest way to do this is just to use <math>(a^3+1+1) . . .</math> on the LHS.
| |
| − | | |
| − | 2. Now all we have to prove is that <math>a^5-a^3-a^2+1 \geq 0</math>, or <math>(a^3-1)(a^2-1) \geq 0</math>.
| |
| − | Now note that if <math>a<1</math>, this is true, if <math>a=1</math>, this is true, and if <math>a>1</math>, this is true as well, and as we have exhausted all cases, we are done.
| |
| − | | |
| − | | |
| − | ==I.More advanced stuff, learn some calculus==
| |
| − | | |
| − | You will need to know derivatives for this part. It's actually quite simple. Derivative=Tangent.
| |
| − | | |
| − | Basically, the derivative of <math>x^n</math> is <math>nx^{n-1}</math>
| |
| − | Adding and other stuff works in the same way.
| |
| − | You also probably need to know
| |
| − | | |
| − | -Product Rule: <math>(fg)'=f'g+fg'</math>
| |
| − | | |
| − | -Quotient Rule: <math>(f/g)'= \frac{g'f-gf'}{g^2}</math>
| |
| − | | |
| − | -Summing: <math>(f+g)'=f'+g'</math>
| |
| − | | |
| − | The second derivative of a function is just applying the derivative twice. A function is convex on an interval if it's second derivative is always positive in that interval. A function is convex if it's second derivative is negative in that interval.
| |
| − | | |
| − | | |
| − | Jensen's inequality says that if <math>f(x)</math> is a convex function in the interval <math>I</math>, for all <math>a_i</math> in <math>I</math>,
| |
| − | <math>\frac{ f(a_1)+f(a_2)+f(a_3)...f(a_n)}{n} \geq f(\frac{a_1+a_2+a_3. . .a_n}{n})</math>
| |
| − | The opposite holds if <math>f(x)</math> is concave.
| |
| − | | |
| − | | |
| − | Karamata's inequality says that if <math>f(x)</math> is convex in the interval <math>I</math>, the sequence <math>(x_n)</math> majorizes <math>(y_n)</math>,, and all <math>x_i, y_i</math> are in <math>I</math>,
| |
| − | <math>f(x_1)+f(x_2)+f(x_3) . . . f(x_n) \geq f(y_1)+f(y_2)+f(y_3). . . f(y_n)</math>
| |
| − | | |
| − | | |
| − | TLT (Tangent Line Trick) is basically where you either
| |
| − | | |
| − | a. take the derivative, and plug in the equality cases or
| |
| − | | |
| − | b. plugging in both equality cases to form a line.
| |
| − | | |
| − | | |
| − | Problem 2: Show that <math>\frac{1}{\sqrt5}+\frac{1}{\sqrt4}+\frac{1}{\sqrt2}>\frac{1}{\sqrt4}+\frac{1}{\sqrt4}+\frac{1}{\sqrt3}</math>
| |
| − | | |
| − | Problem 3: Using Jensen's and Holder's, solve 2001 IMO/2:
| |
| − | Let <math>a,b,c</math> be positive real numbers. Prove <math>\frac{a}{\sqrt{a^{2}+8bc}}+\frac{b}{\sqrt{b^{2}+8ca}}+\frac{c}{\sqrt{c^{2}+8ab}}\ge 1</math>.
| |
| − | | |
| − | Problem 4: (2017 usamo/6)
| |
| − | Find the minimum possible value of
| |
| − | <cmath>\frac{a}{b^3+4}+\frac{b}{c^3+4}+\frac{c}{d^3+4}+\frac{d}{a^3+4},</cmath>
| |
| − | given that <math>a,b,c,d,</math> are nonnegative real numbers such that <math>a+b+c+d=4</math>.
| |
| − | | |
| − | Problem 5: (Japanese MO 1997/6)
| |
| − | Prove that
| |
| − | | |
| − | <math> \frac{\left(b+c-a\right)^{2}}{\left(b+c\right)^{2}+a^{2}}+\frac{\left(c+a-b\right)^{2}}{\left(c+a\right)^{2}+b^{2}}+\frac{\left(a+b-c\right)^{2}}{\left(a+b\right)^{2}+c^{2}}\geq\frac35</math>
| |
| − | | |
| − | for any positive real numbers <math> a</math>, <math> b</math>, <math> c</math>.
| |
| − | | |
| − | ==I.Extra==
| |
| − | | |
| − | Ravi Substitution for triangles. <math>(a,b,c)=(x+y, y+z, x+z)</math>.
| |
| − | | |
| − | Weighted AM-GM (This is kind of dumb imo, just use AM-GM lol)
| |
| − | The weighted form of AM-GM is given by using weighted averages. For example, the weighted arithmetic mean of <math>x</math> and <math>y</math> with <math>3:1</math> is <math>\frac{3x+1y}{3+1}</math> and the geometric is <math>\sqrt[3+1]{x^3y}</math>. (AoPS Wiki)
| |
| − | | |
| − | Problem 6: (1983 imo/6, using Ravi!)
| |
| − | | |
| − | Let <math>a</math>, <math>b</math> and <math>c</math> be the lengths of the sides of a triangle. Prove that
| |
| − | | |
| − | <math>a^2 b(a-b) + b^2 c(b-c) + c^2 (c-a) \geq 0</math>.
| |
| − | | |
| − | Determine when equality occurs.
| |
| − | | |
| − | | |
| − | | |
| − | Inequality Problems:
| |
| − | | |
| − | https://artofproblemsolving.com/wiki/index.php/Category:Olympiad_Inequality_Problems
| |
| − | | |
| − | https://artofproblemsolving.com/wiki/index.php/Category:Olympiad_Algebra_Problems
| |
| − | | |
| − | ==Function Equations==
| |
| − | Oops...I kind of suck at these :P
| |
| − | | |
| − | ~Lcz 6/9/2020 at 12:49 CST
| |
| − | | |
| − | ==F.Intro==
| |
| − | | |
| − | injective: a-1, b-3, c-2, nothing-4
| |
| − | | |
| − | surjective: a-1, b-1, b-2, c-3
| |
| − | | |
| − | bijective: a-1, b-3, c-2
| |
| − | | |
| − | A function <math>f(x)</math> where its domain and range are same is an involution if <math>f(f(x)) = x</math> for every <math>x</math> in its range/domain. This function is bijective.
| |
| − | | |
| − | -Function=anything.
| |
| − | | |
| − | -Symmetry
| |
| − | | |
| − | -Plug in <math>0</math>
| |
| − | | |
| − | -Check for linear/constant solutions first. They are usually the only ones.
| |
| − | | |
| − | -fff trick is pro
| |
| − | | |
| − | -Pointwise trap?!?
| |
| − | | |
| − | -Be aware of your domain/range. (<math>N, Q, Z, C</math>(Probably not))
| |
| − | | |
| − | ==F.Ok these things are sort of cool==
| |
| − | Example 1 (2002 usamo/4):
| |
| − | | |
| − | Let <math>\mathbb{R}</math> be the set of real numbers. Determine all functions <math>f : \mathbb{R} \rightarrow \mathbb{R}</math> such that
| |
| − | | |
| − | <math>f(x^2 - y^2) = xf(x) - yf(y)</math>
| |
| − | | |
| − | for all pairs of real numbers <math>x</math> and <math>y</math>.
| |
| − | | |
| − | Solution:
| |
| − | | |
| − | I claim that the sole solution is <math>f(x)=cx</math> for some constant <math>c</math>.
| |
| − | | |
| − | First note that setting <math>x</math> and <math>y</math> as zero respectively yields <math>f(x^2)=xf(x)</math> and <math>f(-y^2)=-yf(y)</math>. Letting <math>y=x</math> in the second equation means that <math>f</math> is odd.
| |
| − | | |
| − | Now, we can substitute into the original equation our findings:
| |
| − | | |
| − | <math>f(x^2-y^2)=f(x^2)-f(y^2) \implies f(x^2-y^2)+f(y^2)=f(x^2) \implies f(a)+f(b)=f(a+b)</math> where <math>a=x^2-y^2, b=y^2</math>.
| |
| − | | |
| − | Finally,
| |
| − | | |
| − | <math>f(x^2+2x+1)=(x+1)(f(x+1))</math>
| |
| − | | |
| − | <math>\implies f(x^2)+f(2x)+f(1)=(x+1)(f(1))+(x+1)(f(x))</math>
| |
| − | | |
| − | <math>\implies xf(x)+2f(x)+f(1)=(x+1)(f(1))+(x+1)(f(x))</math>
| |
| − | | |
| − | <math>\implies f(x)=xf(1)</math>. Setting <math>f(1)=c</math>, we get the desired.<math>\blacksquare</math>
| |
| − | | |
| − | ==F.They're not that good actually==
| |
| − | | |
| − | Problem 1 (2009 imo/5):
| |
| − | | |
| − | Determine all functions <math>f</math> from the set of positive integers to the set of positive integers such that, for all positive integers <math>a</math> and <math>b</math>, there exists a non-degenerate triangle with sides of lengths
| |
| − | | |
| − | <math>a,f(b)</math> and <math>f(b+f(a)-1)</math>.
| |
| − | | |
| − | This question...is...cool...?
| |
| − | | |
| − | Example 2 (ISL/2015): Determine all functions
| |
| − | | |
| − | <math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math>
| |
| − | | |
| − | with the property that
| |
| − | | |
| − | <cmath>f(x-f(y))=f(f(x))-f(y)-1</cmath>
| |
| − | | |
| − | holds for all <math>x,y\in\mathbb{Z}</math>.
| |
| − | | |
| − | BOGUS Solution:
| |
| − | | |
| − | The answer is <math>f(x)=-1</math> or <math>f(x)=x+1</math>. These clearly work.
| |
| − | | |
| − | Claim: there exists a <math>y</math> such that <math>f(y)=-1</math>.
| |
| − | | |
| − | Proof: set <math>(x,y)=(x, f(x))</math>.
| |
| − | | |
| − | Then <math>f(x+1)=f(f(x))</math> (*) where <math>f(y)=-1</math>. Now <math>f(x)=c</math> for some constant <math>c</math>, or <math>f(x)=x+1</math>.
| |
| − | | |
| − | The former yields <math>c=-1 \implies \boxed{f(x)=-1}</math>, the latter works and yields <math>\boxed{f(x)=x+1}</math>.
| |
| − | | |
| − | | |
| − | Why this is wrong: You can't just assume because <math>f(x)=f(y), x=y</math> or <math>f(x)=c</math>. Remember, a function is anything. Maybe this function is surjective.
| |
| − | | |
| − | Solution (after that step):
| |
| − | | |
| − | Now we plug in <math>(f(x-1), x)</math> (because we know that the <math>f(f(f(x)-1)))</math> will turn into <math>f(x+1)</math>, and therefore will be proving that <math>f(x)</math> is linear).
| |
| − | | |
| − | <math>f(-1)+1= f(f(f(x)-1)))-f(x)</math>
| |
| − | | |
| − | <math>= f(f(x))-f(x)</math> (from (*) on where <math>x</math> is actually <math>f(x)-1</math>.
| |
| − | | |
| − | <math>= f(x+1)-f(x)</math> (follows directly from (*)).
| |
| − | | |
| − | Therefore, this equation is linear.
| |
| − | | |
| − | Now, letting <math>f(x)=kx+c</math>,
| |
| − | | |
| − | From (*), we get
| |
| − | | |
| − | <math>k(x+1)+c = k(kx+c)+c </math>
| |
| − | | |
| − | <math>k(x+1)=k(kx+c).</math>
| |
| − | | |
| − | If <math>k\not=0</math>, then
| |
| − | | |
| − | <math>kx+c=x+1</math>
| |
| − | | |
| − | So <math>\boxed{f(x)=x+1}</math>. Otherwise, <math>f(x)</math> is constant and plugging back into (*), we get the only solution as <math>\boxed{f(x)=-1}</math>
| |
| − | | |
| − | Ay, ok. Heres a semi-recent one.
| |
| − | | |
| − | Problem 2 (2016 usamo/4):
| |
| − | | |
| − | Find all functions <math>f:\mathbb{R}\rightarrow \mathbb{R}</math> such that for all real numbers <math>x</math> and <math>y</math>,<cmath>(f(x)+xy)\cdot f(x-3y)+(f(y)+xy)\cdot f(3x-y)=(f(x+y))^2.</cmath>
| |
| − | | |
| − | Problem 3(One of my favorites, found it in Inter. Alg I think; 1981 imo/6)
| |
| − | | |
| − | The function <math>f(x,y)</math> satisfies
| |
| − | | |
| − | (1) <math>f(0,y)=y+1,</math>
| |
| − | | |
| − | (2) <math>f(x+1,0)=f(x,1),</math>
| |
| − | | |
| − | (3) <math>f(x+1,y+1)=f(x,f(x+1,y)),</math>
| |
| − | | |
| − | for all non-negative integers <math>x,y</math>. Determine <math>f(4,1981)</math>.
| |
| − | | |
| − | Problem 4(cute, 1983 imo/1):
| |
| − | Find all functions <math>f</math> defined on the set of positive reals which take positive real values and satisfy the conditions:
| |
| − | | |
| − | (i) <math>f(xf(y))=yf(x)</math> for all <math>x,y</math>;
| |
| − | | |
| − | (ii) <math>f(x)\to0</math> as <math>x\to \infty</math>.
| |
| − | | |
| − | Problem 5 (1986 imo/5, easy but lots of pitfalls oops):
| |
| − | | |
| − | Find all (if any) functions <math>f</math> taking the non-negative reals onto the non-negative reals, such that
| |
| − | | |
| − | (a) <math>f(xf(y))f(y) = f(x+y)</math> for all non-negative <math>x</math>, <math>y</math>;
| |
| − | | |
| − | (b) <math>f(2) = 0</math>;
| |
| − | | |
| − | (c) <math>f(x) \neq 0</math> for every <math>0 \leq x < 2</math>.
| |
| − | | |
| − | ==F.Extra==
| |
| − | | |
| − | Nothin much
| |
| − | | |
| − | https://artofproblemsolving.com/wiki/index.php/Category:Functional_Equation_Problems
| |
