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

User:Lcz

Revision as of 13:56, 12 June 2020 by Lcz (talk | contribs) (→‎ALGEBRA)

Introduction

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.

.

.

.

.

.

.

.

.

.

.

ALGEBRA

Algebra is cool. I'm pretty good at it (by my standards shup smh).

.

.

.

.

.

.

.

.

.

.

A.Before oly...

  B. Problem 1:

Find $x$ if $x+2=5$. 

  B. Problem 2:

Find the sum of all $x$ such that $x^2-12x+234=0$. 

  B. Problem 3 (troll):

Find the sum of all $x$ in $\mathbb{C}$ such that $x^3+3x^2+3x+1=729$ 

  B. Problem 4 (2018 I/6)

Let $N$ be the number of complex numbers $z$ with the properties that $|z|=1$ and $z^{6!}-z^{5!}$ is a real number. Find the remainder when $N$ is divided by $1000$. 

  B. Problem 5 (AOIME/8 sigh...)

Define a sequence recursively by $f_1(x)=|x-1|$ and $f_n(x)=f_{n-1}(|x-n|)$ for integers $n>1$. Find the least value of $n$ such that the sum of the zeros of $f_n$ exceeds $500,000$. 

  B. Problem 6 (AOIME/11 bash-ish?)

Let $P(x) = x^2 - 3x - 7$, and let $Q(x)$ and $R(x)$ be two quadratic polynomials also with the coefficient of $x^2$ equal to $1$. David computes each of the three sums $P + Q$, $P + R$, and $Q + R$ and is surprised to find that each pair of these sums has a common root, and these three common roots are distinct. If $Q(0) = 2$, then $R(0) = \frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$. 

  B. Problem 7 (1984/15):

Determine $w^2+x^2+y^2+z^2$ if

$\frac{x^2}{2^2-1}+\frac{y^2}{2^2-3^2}+\frac{z^2}{2^2-5^2}+\frac{w^2}{2^2-7^2}=1$ $\frac{x^2}{4^2-1}+\frac{y^2}{4^2-3^2}+\frac{z^2}{4^2-5^2}+\frac{w^2}{4^2-7^2}=1$ $\frac{x^2}{6^2-1}+\frac{y^2}{6^2-3^2}+\frac{z^2}{6^2-5^2}+\frac{w^2}{6^2-7^2}=1$ $\frac{x^2}{8^2-1}+\frac{y^2}{8^2-3^2}+\frac{z^2}{8^2-5^2}+\frac{w^2}{8^2-7^2}=1$ 

  B. Problem 8 (2020 I/14):

Let $P(x)$ be a quadratic polynomial with complex coefficients whose $x^2$ coefficient is $1.$ Suppose the equation $P(P(x))=0$ has four distinct solutions, $x=3,4,a,b.$ Find the sum of all possible values of $(a+b)^2.$ 

  B. Problem 9 (HINT: THIS IS GEOMETRY 2006 II/15):

Given that $x, y,$ and $z$ are real numbers that satisfy:

$x = \sqrt{y^2-\frac{1}{16}}+\sqrt{z^2-\frac{1}{16}}$ $y = \sqrt{z^2-\frac{1}{25}}+\sqrt{x^2-\frac{1}{25}}$ $z = \sqrt{x^2 - \frac 1{36}}+\sqrt{y^2-\frac 1{36}}$ and that $x+y+z = \frac{m}{\sqrt{n}},$ where $m$ and $n$ are positive integers and $n$ is not divisible by the square of any prime, find $m+n.$ 

  B. Problem 10 (2011 I/15):

For some integer $m$, the polynomial $x^3 - 2011x + m$ has the three integer roots $a$, $b$, and $c$. Find $|a| + |b| + |c|$. 

  B. Problem 11 (2014 I/13):

The polynomial $P(x)=(1+x+x^2+\cdots+x^{17})^2-x^{17}$ has $34$ complex roots of the form $z_k = r_k[\cos(2\pi a_k)+i\sin(2\pi a_k)], k=1, 2, 3,\ldots, 34,$ with $0 < a_1 \le a_2 \le a_3 \le \cdots \le a_{34} < 1$ and $r_k>0.$ Given that $a_1 + a_2 + a_3 + a_4 + a_5 = m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m+n.$ 

  B. Problem 12 (2007 I/14):

A sequence is defined over non-negative integral indexes in the following way: $a_{0}=a_{1}=3$, $a_{n+1}a_{n-1}=a_{n}^{2}+2007$.

Find the greatest integer that does not exceed $\frac{a_{2006}^{2}+a_{2007}^{2}}{a_{2006}a_{2007}}.$ 

  B. Problem 13 (2007 II/14):

Let $f(x)$ be a polynomial with real coefficients such that $f(0) = 1,$ $f(2)+f(3)=125,$ and for all $x$, $f(x)f(2x^{2})=f(2x^{3}+x).$ Find $f(5).$ 

  B. Problem 14 (Gotta save the easy ones for the end, 2010 I/14):

For each positive integer n, let $f(n) = \sum_{k = 1}^{100} \lfloor \log_{10} (kn) \rfloor$. Find the largest value of $n$ for which $f(n) \le 300$. 

  B. Problem 15 (2021 usamo/6):

Dad and mom are playing outside while you are in a conference call discussing serious matters.

What is $1+2+3+ . . . \infinity$ (Error compiling LaTeX. Unknown error_msg)? 

  B. Problem 16 (For difficulty of 16, 2016 II/15):

For $1 \leq i \leq 215$ let $a_i = \dfrac{1}{2^{i}}$ and $a_{216} = \dfrac{1}{2^{215}}$. Let $x_1, x_2, ..., x_{216}$ be positive real numbers such that $\sum_{i=1}^{216} x_i=1$ and $\sum_{1 \leq i < j \leq 216} x_ix_j = \dfrac{107}{215} + \sum_{i=1}^{216} \dfrac{a_i x_i^{2}}{2(1-a_i)}$. The maximum possible value of $x_2=\dfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

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 $a,b,c>0$ with $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1$. Prove that $(a+1)(b+1)(c+1) \geq 64$

Solution: We need to try to homogenize this somehow. Plugging in the expression for on the LHS for $1$ won't work. If we try to do something on the left side, we'll still have a degree $3>-1$. Wait a second, why are they all $a+1$'s? Let's try to get rid of the $a+1$'s first. Well, if we add $3$ to both sides of the given condition, we get

$\frac{a+1}{a}+\frac{b+1}{b}+\frac{c+1}{c}=4$, $\frac{(a+1)(b+1)(c+1)}{abc} \geq \frac{64}{27}$, $abc \geq 27$

By AM-GM. Obviously the trivial solution $(3,3,3)$ 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 $(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})^3=1$, we get

$\frac{(ab+bc+ac)^3}{(abc)^2} \geq 27$, $(\frac{ab+bc+ac}{3})^3 \geq (abc)^2$, $(\frac{ab+bc+ac}{3}) \geq (abc)^{2/3}$

Which is true from AM-GM. We shall now introduce Muirhead's... 

 Example 2:

Let $a,b,c>0$ (Again Evan Chen) and $abc=1$. Prove that $a^2+b^2+c^2 \geq a+b+c$.

Solution: First we homogenize:

$a^2+b^2+c^2 \geq (a+b+c)(abc)^{1/3}$

Which is true because $(2,0,0)$ majorizes $(\frac{4}{3}, \frac{1}{3}, \frac{1}{3})$


Cauchy: 

  Problem 1: (2009 usamo/4):

For $n \ge 2$ let $a_1$, $a_2$, ..., $a_n$ be positive real numbers such that $(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$ Prove that $\text{max}(a_1, a_2, ... ,a_n) \le 4 \text{min}(a_1, a_2, ... , a_n)$.

Try to solve this on your own! Very cute problem. Note that you'll probably only ever need Holder's for $3$ variables... 

  Example 3 (2004 usamo/5)

Let $a$, $b$, and $c$ be positive real numbers. Prove that $(a^5 - a^2 + 3)(b^5 - b^2 + 3)(c^5 - c^2 + 3) \ge (a+b+c)^3$.

Solution:

1. The $(a+b+c)$ is cubed, so we try to use Holder's. The simplest way to do this is just to use $(a^3+1+1) . . .$ on the LHS.

2. Now all we have to prove is that $a^5-a^3-a^2+1 \geq 0$, or $(a^3-1)(a^2-1) \geq 0$. Now note that if $a<1$, this is true, if $a=1$, this is true, and if $a>1$, 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. 

  The derivative of $x^n$ is $nx^{n-1}$

Adding and other stuff works in the same way. You also probably need to know 

  -Product Rule: $(fg)'=f'g+fg'$

  -Quotient Rule: $(f/g)'= \frac{g'f-gf'}{g^2}$

  -Summing: $(f+g)'=f'+g'$

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 $f(x)$ is a convex function in the interval $I$, for all $a_i$ in $I$, 
  $\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})$

The opposite holds if $f(x)$ is concave. 


  Karamata's inequality says that if $f(x)$ is convex in the interval $I$, the sequence $(x_n)$ majorizes $(y_n)$,, and all $x_i, y_i$ are in $I$,
  $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)$



  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 $\frac{1}{\sqrt5}+\frac{1}{\sqrt4}+\frac{1}{\sqrt2}>\frac{1}{\sqrt4}+\frac{1}{\sqrt4}+\frac{1}{\sqrt3}$ 

  Problem 3: Using Jensen's and Holder's, solve 2001 IMO/2:

Let $a,b,c$ be positive real numbers. Prove $\frac{a}{\sqrt{a^{2}+8bc}}+\frac{b}{\sqrt{b^{2}+8ca}}+\frac{c}{\sqrt{c^{2}+8ab}}\ge 1$. 

  Problem 4: (2017 usamo/6)

Find the minimum possible value of \[\frac{a}{b^3+4}+\frac{b}{c^3+4}+\frac{c}{d^3+4}+\frac{d}{a^3+4},\] given that $a,b,c,d,$ are nonnegative real numbers such that $a+b+c+d=4$. 

  Problem 5: (Japanese MO 1997/6)

Prove that

$\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$

for any positive real numbers $a$, $b$, $c$.

I.Extra

  Ravi Substitution for triangles. $(a,b,c)=(x+y, y+z, x+z)$.

  Problem 6: (1983 imo/6, using Ravi!)

Let $a$, $b$ and $c$ be the lengths of the sides of a triangle. Prove that

$a^2 b(a-b) + b^2 c(b-c) + c^2 (c-a) \geq 0$.

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 $f(x)$ where its domain and range are same is an involution if $f(f(x)) = x$ for every $x$ in its range/domain. This function is bijective.

-Function=anything.

-Symmetry

-Plug in $0$

-Check for linear/constant solutions first. They are usually the only ones.

-fff trick is pro

-Pointwise trap?!?

-Be aware of your domain/range. ($R, Q, Z, C$(Probably not))

F.Ok these things are sort of cool

  Example 1 (2002 usamo/4):

Let $\mathbb{R}$ be the set of real numbers. Determine all functions $f : \mathbb{R} \rightarrow \mathbb{R}$ such that

$f(x^2 - y^2) = xf(x) - yf(y)$

for all pairs of real numbers $x$ and $y$.

Solution:

I claim that the sole solution is $f(x)=cx$ for some constant $c$.

First note that setting $x$ and $y$ as zero respectively yields $f(x^2)=xf(x)$ and $f(-y^2)=-yf(y)$. Letting $y=x$ in the second equation means that $f$ is odd.

Now, we can substitute into the original equation our findings:

$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)$ where $a=x^2-y^2, b=y^2$.

Finally,

$f(x^2+2x+1)=(x+1)(f(x+1))$

$\implies f(x^2)+f(2x)+f(1)=(x+1)(f(1))+(x+1)(f(x))$

$\implies xf(x)+2f(x)+f(1)=(x+1)(f(1))+(x+1)(f(x))$

$\implies f(x)=xf(1)$. Setting $f(1)=c$, we get the desired.$\blacksquare$

F.They're not that cool actually

  Problem 1 (2009 imo/5):

Determine all functions $f$ from the set of positive integers to the set of positive integers such that, for all positive integers $a$ and $b$, there exists a non-degenerate triangle with sides of lengths

$a,f(b)$ and $f(b+f(a)-1)$.

This question...is...cool...? 

  Example 2 (ISL/2015): Determine all functions

$f:\mathbb{Z}\rightarrow\mathbb{Z}$

with the property that

\[f(x-f(y))=f(f(x))-f(y)-1\]

holds for all $x,y\in\mathbb{Z}$.

BOGUS Solution:

The answer is $f(x)=-1$ or $f(x)=x+1$. These clearly work.

Claim: there exists a $y$ such that $f(y)=-1$.

Proof: set $(x,y)=(x, f(x))$.

Then $f(x+1)=f(f(x))$ (*) where $f(y)=-1$. Now $f(x)=c$ for some constant $c$, or $f(x)=x+1$.

The former yields $c=-1 \implies \boxed{f(x)=-1}$, the latter works and yields $\boxed{f(x)=x+1}$.


Why this is wrong: You can't just assume because $f(x)=f(y), x=y$ or $f(x)=c$. Remember, a function is anything. Maybe this function is surjective.

Solution (after that step):

Now we plug in $(f(x-1), x)$ (because we know that the $f(f(f(x)-1)))$ will turn into $f(x+1)$, and therefore will be proving that $f(x)$ is linear).

$f(-1)+1= f(f(f(x)-1)))-f(x)$

$= f(f(x))-f(x)$ (from (*) on where $x$ is actually $f(x)-1$.

$= f(x+1)-f(x)$ (follows directly from (*)).

Therefore, this equation is linear.

Now, letting $f(x)=kx+c$,

From (*), we get

$k(x+1)+c = k(kx+c)+c$

$k(x+1)=k(kx+c).$

If $k\not=0$, then

$kx+c=x+1$

So $\boxed{f(x)=x+1}$. Otherwise, $f(x)$ is constant and plugging back into (*), we get the only solution as $\boxed{f(x)=-1}$

Ay, ok. Heres a semi-recent one. 

  Problem 2 (2016 usamo/4):

Find all functions $f:\mathbb{R}\rightarrow \mathbb{R}$ such that for all real numbers $x$ and $y$,\[(f(x)+xy)\cdot f(x-3y)+(f(y)+xy)\cdot f(3x-y)=(f(x+y))^2.\] 

  Problem 3(One of my favorites, found it in Inter. Alg I think; 1981 imo/6)

The function $f(x,y)$ satisfies

(1) $f(0,y)=y+1,$

(2) $f(x+1,0)=f(x,1),$

(3) $f(x+1,y+1)=f(x,f(x+1,y)),$

for all non-negative integers $x,y$. Determine $f(4,1981)$. 

  Problem 4(cute, 1983 imo/1):

Find all functions $f$ defined on the set of positive reals which take positive real values and satisfy the conditions:

(i) $f(xf(y))=yf(x)$ for all $x,y$;

(ii) $f(x)\to0$ as $x\to \infty$. 

  Problem 5 (1986 imo/5, easy but lots of pitfalls oops):

Find all (if any) functions $f$ taking the non-negative reals onto the non-negative reals, such that

(a) $f(xf(y))f(y) = f(x+y)$ for all non-negative $x$, $y$;

(b) $f(2) = 0$;

(c) $f(x) \neq 0$ for every $0 \leq x < 2$.

F.Extra

Nothin much

https://artofproblemsolving.com/wiki/index.php/Category:Functional_Equation_Problems

MONSTROUS Functional Equations

Ok we're not going to talk about these

Hopefully they don't appear on usa(j)mo next year

otherwise i'm screwed lol

.

.

.

.

.

.

.

.

Combonatorics

.

.

.

.

.

.

-;

This will be a big chapter because I have no idea what the categories of combo are.

Yo I'm trash at this stuff. I'm trash at everything tbh. Let's give it a try, shall we?

C.Basics

We're pretty much only going to be working with Expected value and pigeonhole principle here, which corresponds to about 25%(a lot less) of olympiad combo problems.

First of all, we will always denote expected value as $\mathbb{E}$. Denote several events $e_1, e_2, e_3, . . . e_n$ and their probabilities as $p_1, p_2, p_3, . . . p_n$. Then 

  $\mathbb{E}=\sum_{i=1}^{n} e_ip_i$.

Next, there's this cool (I think so) property of the expected value.

Say the average number of cookies someone in this world has ate is $9.7823489138728394$. Then there exists a person that has ate at least $10$ cookies, and also a person who ate at most $9$ cookies. It seems simple, but it's pretty powerful. 

  Pigeonhole principle says that if you have $a$ pigeonholes and $b$ pigeons, there must exist a pigeonhole with at least ceiling($\frac{b}{a}$) pigeons.

This follows directly from our previous claim.

C.This stuff is pretty easy

  Example 1 (AoPS):

In his spare time, Richard Rusczyk shuffles a standard deck of 52 playing cards. He then turns the cards up one by one from the top of the deck until the third ace appears. If the expected (average) number of cards Richard will turn up is $m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m+n.$

Solution:

The four aces divide the deck into $5$ parts, and the expected number of cards in each of them is $\frac{48}{5}$. Therefore the answer is $\frac{48}{5}+3=\frac{63}{5} \implies \boxed{068}$ 

  Example 2 (1987 imo/1):

Let $p_{n}(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^{n}k p_{n}(k)=n!$.

Solution:

Look at the summation. It's actually just the expected number of fixed points, multiplied by the number of permutations, or $n!$.

Because every integer has a $\frac{(n-1)!}{n!}=\frac{1}{n}$ chance of being a fixed point, the expected number of fixed points is $1$, and multiplying by $n!$, we see that the requested sum is indeed $n!$. 

  Problem 1 (Easy Pigeonhole! 1972 imo/1):

Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum. 

  Problem 2 (another easy Pigeonhole, 1976 usamo/1):

(a) Suppose that each square of a $4\times 7$ chessboard is colored either black or white. Prove that with any such coloring, the board must contain a rectangle (formed by the horizontal and vertical lines of the board such as the one outlined in the figure) whose four distinct unit corner squares are all of the same color.

(b) Exhibit a black-white coloring of a $4\times 6$ board in which the four corner squares of every rectangle, as described above, are not all of the same color. 

  Problem 3 (Pigeonhole mastery lol, 2012 usamo/2):

A circle is divided into $432$ congruent arcs by $432$ points. The points are colored in four colors such that some $108$ points are colored Red, some $108$ points are colored Green, some $108$ points are colored Blue, and the remaining $108$ points are colored Yellow. Prove that one can choose three points of each color in such a way that the four triangles formed by the chosen points of the same color are congruent. 

  Problem 4 (Get out your combinatorics identities, 1981 imo/2):

Let $1 \le r \le n$ and consider all subsets of $r$ elements of the set $\{ 1, 2, \ldots , n \}$. Each of these subsets has a smallest member. Let $F(n,r)$ denote the arithmetic mean of these smallest numbers; prove that

$F(n,r) = \frac{n+1}{r+1}.$ 

  Problem 5 (1998 imo/2):

In a competition, there are $a$ contestants and $b$ judges, where $b \geq 3$ is an odd integer. Each judge rates each contestant as either “pass” or “fail”. Suppose $k$ is a number such that, for any two judges, their ratings coincide for at most $k$ contestants. Prove that $\frac{k}{a} \geq \frac{b-1}{2b}$

Now this stuff is kind of hard

  Problem 6 (Construction! 2014 imo/5):

For each positive integer $n$, the Bank of Cape Town issues coins of denomination $\tfrac{1}{n}$. Given a finite collection of such coins (of not necessarily different denominations) with total value at most $99+\tfrac{1}{2}$, prove that it is possible to split this collection into $100$ or fewer groups, such that each group has total value at most $1$. 

  Problem 7 (More construction! 2016 imo/2):

Find all integers $n$ for which each cell of $n \times n$ table can be filled with one of the letters $I,M$ and $O$ in such a way that:

in each row and each column, one third of the entries are $I$, one third are $M$ and one third are $O$; and

in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are $I$, one third are $M$ and one third are $O$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=User:Lcz&oldid=125246"