|
|
| (62 intermediate revisions by 4 users not shown) |
| Line 1: |
Line 1: |
| − | ==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. (There aren't that many examples, sorry.)
| |
| | | | |
| − | Edit (7/2/2020): This thing is getting big, woah
| |
| − |
| |
| − | ==ALGEBRA==
| |
| − |
| |
| − | Algebra is cool. I'm pretty good at it (by my standards shup smh).
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | ===Before oly...===
| |
| − |
| |
| − | B. Problem 1:
| |
| − |
| |
| − | Find <math>x</math> if <math>x+2=5</math>.
| |
| − |
| |
| − | B. Problem 2:
| |
| − |
| |
| − | Find the sum of all <math>x</math> such that <math>x^2-12x+234=0</math>.
| |
| − |
| |
| − | B. Problem 3 (troll):
| |
| − |
| |
| − | Find the sum of all <math>x</math> in <math>\mathbb{C}</math> such that <math>x^3+3x^2+3x+1=729</math>
| |
| − |
| |
| − | B. Problem 4 (2018 I/6)
| |
| − |
| |
| − | Let <math>N</math> be the number of complex numbers <math>z</math> with the properties that <math>|z|=1</math> and <math>z^{6!}-z^{5!}</math> is a real number. Find the remainder when <math>N</math> is divided by <math>1000</math>.
| |
| − |
| |
| − | B. Problem 5 (AOIME/8 sigh...)
| |
| − |
| |
| − | Define a sequence recursively by <math>f_1(x)=|x-1|</math> and <math>f_n(x)=f_{n-1}(|x-n|)</math> for integers <math>n>1</math>. Find the least value of <math>n</math> such that the sum of the zeros of <math>f_n</math> exceeds <math>500,000</math>.
| |
| − |
| |
| − | B. Problem 6 (AOIME/11 bash-ish?)
| |
| − |
| |
| − | Let <math>P(x) = x^2 - 3x - 7</math>, and let <math>Q(x)</math> and <math>R(x)</math> be two quadratic polynomials also with the coefficient of <math>x^2</math> equal to <math>1</math>. David computes each of the three sums <math>P + Q</math>, <math>P + R</math>, and <math>Q + R</math> and is surprised to find that each pair of these sums has a common root, and these three common roots are distinct. If <math>Q(0) = 2</math>, then <math>R(0) = \frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>.
| |
| − |
| |
| − | B. Problem 7 (1984/15):
| |
| − |
| |
| − | Determine <math>w^2+x^2+y^2+z^2</math> if
| |
| − |
| |
| − | <math>\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</math>
| |
| − | <math>\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</math>
| |
| − | <math>\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</math>
| |
| − | <math>\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</math>
| |
| − |
| |
| − | B. Problem 8 (2020 I/14):
| |
| − |
| |
| − | Let <math>P(x)</math> be a quadratic polynomial with complex coefficients whose <math>x^2</math> coefficient is <math>1.</math> Suppose the equation <math>P(P(x))=0</math> has four distinct solutions, <math>x=3,4,a,b.</math> Find the sum of all possible values of <math>(a+b)^2.</math>
| |
| − |
| |
| − | B. Problem 9 (HINT: THIS IS GEOMETRY 2006 II/15):
| |
| − |
| |
| − | Given that <math>x, y,</math> and <math>z</math> are real numbers that satisfy:
| |
| − |
| |
| − | <math>x = \sqrt{y^2-\frac{1}{16}}+\sqrt{z^2-\frac{1}{16}}</math>
| |
| − | <math>y = \sqrt{z^2-\frac{1}{25}}+\sqrt{x^2-\frac{1}{25}}</math>
| |
| − | <math>z = \sqrt{x^2 - \frac 1{36}}+\sqrt{y^2-\frac 1{36}}</math>
| |
| − | and that <math>x+y+z = \frac{m}{\sqrt{n}},</math> where <math>m</math> and <math>n</math> are positive integers and <math>n</math> is not divisible by the square of any prime, find <math>m+n.</math>
| |
| − |
| |
| − | B. Problem 10 (2011 I/15):
| |
| − |
| |
| − | For some integer <math>m</math>, the polynomial <math>x^3 - 2011x + m</math> has the three integer roots <math>a</math>, <math>b</math>, and <math>c</math>. Find <math>|a| + |b| + |c|</math>.
| |
| − |
| |
| − | B. Problem 11 (2014 I/13):
| |
| − |
| |
| − | The polynomial <math>P(x)=(1+x+x^2+\cdots+x^{17})^2-x^{17}</math> has <math>34</math> complex roots of the form <math>z_k = r_k[\cos(2\pi a_k)+i\sin(2\pi a_k)], k=1, 2, 3,\ldots, 34,</math> with <math>0 < a_1 \le a_2 \le a_3 \le \cdots \le a_{34} < 1</math> and <math>r_k>0.</math> Given that <math>a_1 + a_2 + a_3 + a_4 + a_5 = m/n,</math> where <math>m</math> and <math>n</math> are relatively prime positive integers, find <math>m+n.</math>
| |
| − |
| |
| − | B. Problem 12 (2007 I/14):
| |
| − |
| |
| − | A sequence is defined over non-negative integral indexes in the following way: <math>a_{0}=a_{1}=3</math>, <math>a_{n+1}a_{n-1}=a_{n}^{2}+2007</math>.
| |
| − |
| |
| − | Find the greatest integer that does not exceed <math>\frac{a_{2006}^{2}+a_{2007}^{2}}{a_{2006}a_{2007}}.</math>
| |
| − |
| |
| − | B. Problem 13 (2007 II/14):
| |
| − |
| |
| − | Let <math>f(x)</math> be a polynomial with real coefficients such that <math>f(0) = 1,</math> <math>f(2)+f(3)=125,</math> and for all <math>x</math>, <math>f(x)f(2x^{2})=f(2x^{3}+x).</math> Find <math>f(5).</math>
| |
| − |
| |
| − | B. Problem 14 (Gotta save the easy ones for the end, 2010 I/14):
| |
| − |
| |
| − | For each positive integer n, let <math>f(n) = \sum_{k = 1}^{100} \lfloor \log_{10} (kn) \rfloor</math>. Find the largest value of <math>n</math> for which <math>f(n) \le 300</math>.
| |
| − |
| |
| − | B. Problem 15 (2021 usamo/6):
| |
| − |
| |
| − | Dad and mom are playing outside while you are in a conference call discussing serious matters.
| |
| − |
| |
| − | What is <math>1+2+3+ . . . \infty</math>?
| |
| − |
| |
| − | B. Problem 16 (For difficulty of 16, 2016 II/15):
| |
| − |
| |
| − | For <math>1 \leq i \leq 215</math> let <math>a_i = \dfrac{1}{2^{i}}</math> and <math>a_{216} = \dfrac{1}{2^{215}}</math>. Let <math>x_1, x_2, ..., x_{216}</math> be positive real numbers such that <math>\sum_{i=1}^{216} x_i=1</math> and <math>\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)}</math>. The maximum possible value of <math>x_2=\dfrac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m+n</math>.
| |
| − |
| |
| − | B. Problem 17 (2014 usamo/1):
| |
| − |
| |
| − | Let <math>a,b,c,d</math> be real numbers such that <math>b-d \ge 5</math> and all zeros <math>x_1, x_2, x_3,</math> and <math>x_4</math> of the polynomial <math>P(x)=x^4+ax^3+bx^2+cx+d</math> are real. Find the smallest value the product <math>(x_1^2+1)(x_2^2+1)(x_3^2+1)(x_4^2+1)</math> can take.
| |
| − |
| |
| − | B. Problem 18 (1985 usamo/1):
| |
| − |
| |
| − | Determine whether or not there are any positive integral solutions of the simultaneous equations
| |
| − | \begin{align*}x_1^2+x_2^2+\cdots+x_{1985}^2&=y^3,\\
| |
| − | x_1^3+x_2^3+\cdots+x_{1985}^3&=z^2\end{align*}with distinct integers <math>x_1</math>, <math>x_2</math>, <math>\ldots</math>, <math>x_{1985}</math>.
| |
| − |
| |
| − | B. Problem 19 (1994 usamo/4):
| |
| − |
| |
| − | Let <math>\, a_1, a_2, a_3, \ldots \,</math> be a sequence of positive real numbers satisfying <math>\, \sum_{j = 1}^n a_j \geq \sqrt {n} \,</math> for all <math>\, n \geq 1</math>. Prove that, for all <math>\, n \geq 1, \,</math>
| |
| − |
| |
| − | <cmath>\sum_{j = 1}^n a_j^2 > \frac {1}{4} \left( 1 + \frac {1}{2} + \cdots + \frac {1}{n} \right).</cmath>
| |
| − |
| |
| − | B. Problem 20 (THIS COUNTS AS ALGEBRA 1996 usamo/1):
| |
| − |
| |
| − | Prove that the average of the numbers <math>n\sin n^{\circ}\; (n = 2,4,6,\ldots,180)</math> is <math>\cot 1^\circ</math>.
| |
| − |
| |
| − | ==Inequalities==
| |
| − | Yay! I love inequalities. Clever algebraic manipulation+thereoms is all you need. It all comes from experience though...
| |
| − |
| |
| − | ===Basics===
| |
| − |
| |
| − | Note that the set <math>(a_n)</math> is <math>(a_1, a_2, a_3, . . . a_n)</math>.
| |
| − |
| |
| − | <cmath>\sum_{\text{sym}} a^2b </cmath> <math>=a^2b+a^2c+b^2a+b^2c+c^2a+c^2b</math>. It is "symmetric".
| |
| − |
| |
| − | <cmath>\sum_{\text{cyc}} a^2b </cmath> <math>=a^2b+b^2c+c^2a</math>. It is "cyclic".
| |
| − | AM-GM says that for nonnegative reals <math>(a_n)</math>, their Arithmetic Mean is <math>\geq</math> their Geometric Mean.
| |
| − | <math>\frac{a_1+a_2+a_3 . . . a_n}{n} \geq \sqrt[n]{a_1a_2a_3 . . . a_n}</math>.
| |
| − |
| |
| − | Cauchy's Inequality says that for nonnegative reals <math>(a_n), (b_n)</math>,
| |
| − | <math>({a_1}^2+{a_2}^2+{a_3}^2+ . . . {a_n}^2)({b_1}^2+{b_2}^2+{b_3}^2+ . . . {b_n}^2) \geq (a_1b_1+a_2b_2+a_3b_3 . . . a_nb_n)^2</math>
| |
| − | Equality holds when <math>\frac{a_i}{b_i}</math> is constant for all <math>i</math>.
| |
| − |
| |
| − | Titu's lemma follows directly from Cauchy, it says for the same variables, <cmath>\frac{ a_1^2 } { b_1 } + \frac{ a_2 ^2 } { b_2 } + \cdots + \frac{ a_n ^2 } { b_n } \geq \frac{ (a_1 + a_2 + \cdots+ a_n ) ^2 } { b_1 + b_2 + \cdots+ b_n }.</cmath>
| |
| − |
| |
| − | We say a set <math>(a_n)</math> majorizes <math>(b_n)</math> if
| |
| − | (a) the sum of the elements are the same.
| |
| − | (b) the elements are in decreasing order.
| |
| − | (c) the leftmost sums of <math>(a_n)</math> are <math>\geq</math> those of <math>(b_n)</math>.
| |
| − |
| |
| − | For example, <math>(24,9,2)</math> majorizes <math>(20, 8, 7)</math> and <math>(5,1,1)</math> majorizes <math>(4,3,0)</math>.
| |
| − |
| |
| − | Muirhead's Inequality says that for reals <math>(a_n), (b_n)</math> and nonnegative reals <math>(x_n)</math>, where <math>(a_n)</math> majorizes <math>(b_n)</math>,
| |
| − | <cmath>\sum_{\text{sym}} {x_1}^{a_1}{x_2}^{a_2}\cdots {x_n}^{a_n}\geq \sum_{\text{sym}} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}</cmath>
| |
| − |
| |
| − | Holder's Inequality (for <math>3</math>, you'll probably only need it for <math>3</math>, plus this is the "basics" chapter anyway...) says that
| |
| − | for positive reals <math>(a_n), (b_n), (c_n)</math>,
| |
| − | <math>(a_1^3+b_1^3+c_1^3)(a_2^3+b_2^3+c_2^3)(a_3^3+b_3^3+c_3^3) \geq (a_1b_1c_1+a_2b_2c_2+a_3b_3c_3)^3</math>
| |
| − |
| |
| − | These are cool, but remember that these should only be used when the inequality is homogenized already.. These are all pretty easy to prove as well (with the help of the trivial inequality, but because it is trivial, we didn't include it here.)
| |
| − |
| |
| − | Weighted Power Mean says that for positive reals <math>(a_n)</math> and ("weights") <math>(w_n)</math> that sum to <math>1</math>,
| |
| − | if <math>r=0</math>,
| |
| − | <cmath>P(r)=a_1^{w_1} a_2^{w_2} a_3^{w_3} . . . a_n^{w_n}</cmath>
| |
| − | if <math>r \neq 0</math>,
| |
| − | <cmath>P(r)=(w_1a_1^r+w_2a_2^r+w_3a_3^r . . . +w_na_n^r)^{\frac{1}{r}}</cmath>
| |
| − | If <math>r>s</math>, <math>P(r) \geq P(s)</math> with equality if and only if all the <math>a_i</math> are equal.
| |
| − |
| |
| − | Example 1:
| |
| − |
| |
| − | Prove that <math>(a+b+c)^3 \geq a^3+b^3+c^3+24abc</math>
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | Expand everything. Canceling terms, you should get <math>3\sum_{sym} a^2b \geq 18abc</math> This is true by muirhead's on <math>(2,1,0)</math> and <math>(1,1,1)</math> or by AM-GM
| |
| − |
| |
| − | Example 2 (2001 imo/2):
| |
| − |
| |
| − | Let <math>a,b,c</math> be positive real numbers. Prove that <math>\frac{a}{\sqrt{a^{2}+8bc}}+\frac{b}{\sqrt{b^{2}+8ca}}+\frac{c}{\sqrt{c^{2}+8ab}}\ge 1</math>.
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | By Holder's, <math>\left(\sum_{cyc}\frac{a}{\sqrt{a^{2}+8bc}}\right)\left(\sum_{cyc}\frac{a}{\sqrt{a^{2}+8bc}}\right)\left(\sum_{cyc} a(a^{2}+8bc)\right)\ge (a+b+c)^{3}</math>. Now we need to prove <math>(a+b+c)^3 \geq a^3+b^3+c^3+24abc</math> but this is the same as the previous question.
| |
| − |
| |
| − | Example 3 (Creds. to Evan Chen):
| |
| − |
| |
| − | If <math>abc=1</math>, prove that <math>a^2+b^2+c^2 \geq a+b+c</math>.
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | We have never encountered something where the degrees aren't the same, or there is a condition on the variables. Put the two together! If we multiply the right hand side by <math>(abc)^{\frac{1}{3}}</math>, it will make both sides equal degree. Now we want to prove that <math>a^2+b^2+c^2 \geq \sum_{cyc} a^{\frac{4}{3}} b^{\frac{1}{3}} c^{\frac{1}{3}}</math>. This is muirhead's on <math>(2,0,0)</math> and <math>(\frac{4}{3}, \frac{1}{3}, \frac{1}{3})</math>, but what about the condition? It's gone. In fact, <math>abc</math> could be anything at this point. If we multiply <math>a,b,</math> and <math>c</math> by <math>k</math>, the inequality becomes <math>(k^2)(a^2+b^2+c^2) \geq (k^2)(\sum_{cyc} a^{\frac{4}{3}} b^{\frac{1}{3}} c^{\frac{1}{3}})</math>, and we can just divide both sides by <math>k^2</math>! This is essentially the idea of [homogenizing]. Since there are now no conditions, it is a normal inequality and we are done by muirhead's.
| |
| − |
| |
| − | Problem 1:
| |
| − |
| |
| − | Prove that <math>(a+b)(b+c)(c+a) \geq 8abc</math>.
| |
| − |
| |
| − | Problem 2 (Evan Chen?):
| |
| − |
| |
| − | Find the minimum possible value of <math>\frac{ab}{c}+\frac{bc}{a}+\frac{ca}{b}</math> if <math>a^2+b^2+c^2=1</math>.
| |
| − |
| |
| − | Example 4 (1981 imo/1):
| |
| − |
| |
| − | <math>P</math> is a point inside a given triangle <math>ABC</math>. <math>D, E, F</math> are the feet of the perpendiculars from <math>P</math> to the lines <math>BC, CA, AB</math>, respectively. Find all <math>P</math> for which
| |
| − |
| |
| − | <math>\frac{BC}{PD} + \frac{CA}{PE} + \frac{AB}{PF}</math>
| |
| − |
| |
| − | is least.
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | Note that <math>BC \cdot PD + CA \cdot PE + AB \cdot PF</math> is <math>2[ABC]</math> and is thus constant. By Cauchy,
| |
| − |
| |
| − | <math>{(BC \cdot PD + CA \cdot PE + AB \cdot PF) \left(\frac{BC}{PD} + \frac{CA}{PE} + \frac{AB}{PF} \right) \ge ( BC + CA + AB )^2}</math>,
| |
| − |
| |
| − | with equality when <math>PD^2=PE^2=PF^2</math>, or <math>PD=PE=PF</math>, or <math>P</math> is the incenter.
| |
| − |
| |
| − | Problem 3: (Cauchy, 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>.
| |
| − |
| |
| − | Example 5 (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.
| |
| − |
| |
| − | ===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 <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, 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>.
| |
| − |
| |
| − | ===Problems===
| |
| − |
| |
| − | Problem 6 (2011 usamo/1):
| |
| − |
| |
| − | Let <math>a</math>, <math>b</math>, <math>c</math> be positive real numbers such that <math>a^2 + b^2 + c^2 + (a + b + c)^2 \le 4</math>. Prove that<cmath>\frac{ab + 1}{(a + b)^2} + \frac{bc + 1}{(b + c)^2} + \frac{ca + 1}{(c + a)^2} \ge 3.</cmath>
| |
| − |
| |
| − | Problem 7 (1974 usamo/2):
| |
| − |
| |
| − | Prove that if <math>a</math>, <math>b</math>, and <math>c</math> are positive real numbers, then
| |
| − |
| |
| − | <math>a^ab^bc^c\ge (abc)^{(a+b+c)/3}</math>
| |
| − |
| |
| − | Problem 8 (1995 imo/2):
| |
| − |
| |
| − | Let <math>a, b, c</math> be positive real numbers such that <math>abc = 1</math>. Prove that<cmath>\frac{1}{a^3(b+c)} + \frac{1}{b^3(c+a)} + \frac{1}{c^3(a+b)} \geq \frac{3}{2}.</cmath>
| |
| − |
| |
| − | Problem 9 (2000 imo/2):
| |
| − |
| |
| − | Let <math> a, b, c</math> be positive real numbers so that <math> abc = 1</math>. Prove that
| |
| − | <math>(a-1+\frac{1}{b})(b-1+\frac{1}{c})(c-1+\frac{1}{a}) \leq -1</math>.
| |
| − |
| |
| − | Problem 10 (2003 usamo/5):
| |
| − |
| |
| − | Let <math>a</math>, <math>b</math>, <math>c</math> be positive real numbers. Prove that
| |
| − |
| |
| − | <math>\dfrac{(2a + b + c)^2}{2a^2 + (b + c)^2} + \dfrac{(2b + c + a)^2}{2b^2 + (c + a)^2} + \dfrac{(2c + a + b)^2}{2c^2 + (a + b)^2} \le 8.</math>
| |
| − |
| |
| − | Problem 11 (2001 usamo/3):
| |
| − |
| |
| − | Let <math>a, b, c \geq 0</math> and satisfy
| |
| − |
| |
| − | <math>a^2 + b^2 + c^2 + abc = 4.</math>
| |
| − | Show that
| |
| − |
| |
| − | <math>0 \le ab + bc + ca - abc \leq 2.</math>
| |
| − |
| |
| − | Problem 12 (2012 usajmo/3):
| |
| − |
| |
| − | Let <math>a</math>, <math>b</math>, <math>c</math> be positive real numbers. Prove that<cmath>\frac{a^3 + 3b^3}{5a + b} + \frac{b^3 + 3c^3}{5b + c} + \frac{c^3 + 3a^3}{5c + a} \ge \frac{2}{3} (a^2 + b^2 + c^2).</cmath>
| |
| − |
| |
| − | Problem 13 (2005 imo/3):
| |
| − |
| |
| − | Let <math>x,y,z</math> be three positive reals such that <math>xyz\geq 1</math>. Prove that
| |
| − | <cmath> \frac { x^5-x^2 }{x^5+y^2+z^2} + \frac {y^5-y^2}{x^2+y^5+z^2} + \frac {z^5-z^2}{x^2+y^2+z^5} \geq 0 . </cmath>
| |
| − |
| |
| − | Problem 14 (2003 imo shortlist/A6. cough.):
| |
| − |
| |
| − | Let <math>n</math> be a positive integer and let <math>(x_1,\ldots,x_n)</math>, <math>(y_1,\ldots,y_n)</math> be two sequences of positive real numbers. Suppose <math>(z_2,\ldots,z_{2n})</math> is a sequence of positive real numbers such that <math>z_{i+j}^2 \geq x_iy_j</math> for all <math>1\le i,j \leq n</math>.
| |
| − |
| |
| − | Let <math>M=\max\{z_2,\ldots,z_{2n}\}</math>. Prove that
| |
| − | <math>\frac{M+z_2+\dots+z_{2n}}{2n})^2 \geq \frac{x_1+\dots+x_n}{n} (\frac{y_1+\dots+y_n}{n}).</math>
| |
| − |
| |
| − | ===Extra===
| |
| − |
| |
| − | Ravi Substitution for triangles. <math>(a,b,c)=(x+y, y+z, x+z)</math>.
| |
| − |
| |
| − | Problem 15: (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
| |
| − |
| |
| − | ===Basics===
| |
| − |
| |
| − | injective: a-1, b-3, c-2, nothing-4 (There are more "things mapped to" in the range)
| |
| − | surjective: a-1, b-1, b-2, c- (more "things mapped to" in the domain)
| |
| − | bijective: a-1, b-3, c-2 (1-1)
| |
| − |
| |
| − | (I have no excersises, but let's just say this is one): 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. Prove that this function is bijective.
| |
| − |
| |
| − | -Function=anything. (HINT: IT DOESNT HAVE TO BE A POLYNOMIAL)
| |
| − |
| |
| − | -Symmetry (switch x and y)
| |
| − |
| |
| − | -Plug in <math>(0,0)</math>, <math>(1,1)</math>, <math>(0,y)</math>, <math>(x,0)</math>, <math>(1,y)</math>, <math>(x,1)</math>, <math>f(x),x)</math>, etc.. first
| |
| − |
| |
| − | -Check for linear/constant solutions first. They are usually the only ones.
| |
| − |
| |
| − | -<math>fff</math> trick: if <math>f(f(x))=x+1</math>, <math>f(f(f(x)))=f(x+1)=f(x)+1</math> by using the inner two <math>f</math>'s, and the outer two.
| |
| − |
| |
| − | -Pointwise trap!!!!!! If <math>x(f(x))=x^2</math>, this does NOT mean that <math>f(x)=x, -x</math> for all <math>x</math>. Remember, function=anything and you could have <math>f(a)=a</math>, <math>f(b)=-b</math> for some <math>(a,b)</math>. The most common way to get rid of this is just by doing <math>f(a)=a</math>, <math>f(b)=-b</math>, and then show that this leads to a contradiction.
| |
| − |
| |
| − | -Be aware of your domain/range. (<math>\mathbb{R}, \mathbb{Q}, \mathbb{Z}, \mathbb{C}</math>(Probably not)). For example, "Cauchy Functional Equation" Changes a LOT when we go from <math>\mathbb{Q} -> \mathbb{Q}</math> to <math>\mathbb{R} -> \mathbb{R}</math>.
| |
| − |
| |
| − | ===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>
| |
| − |
| |
| − |
| |
| − | 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>.
| |
| − |
| |
| − | ===Problems===
| |
| − |
| |
| − | Problem 6 (1993 usamo/3):
| |
| − |
| |
| − | Consider functions <math>f : [0, 1] \rightarrow \mathbb{R}</math> which satisfy
| |
| − |
| |
| − | (i) <math>f(x)\ge0</math> for all <math>x</math> in <math>[0, 1]</math>,
| |
| − | (ii) <math>f(1) = 1</math>,
| |
| − | (iii) <math>f(x) + f(y) \le f(x + y)</math> whenever <math>x</math>, <math>y</math>, and <math>x + y</math> are all in <math>[0, 1]</math>.
| |
| − | Find, with proof, the smallest constant <math>c</math> such that
| |
| − |
| |
| − | <math>f(x) \le cx</math>
| |
| − | for every function <math>f</math> satisfying (i)-(iii) and every <math>x</math> in <math>[0, 1]</math>.
| |
| − |
| |
| − | Problem 7 (2015 usajmo/4):
| |
| − |
| |
| − | Find all functions <math>f:\mathbb{Q}\rightarrow\mathbb{Q}</math> such that<cmath>f(x)+f(t)=f(y)+f(z)</cmath>for all rational numbers <math>x<y<z<t</math> that form an arithmetic progression. (<math>\mathbb{Q}</math> is the set of all rational numbers.)
| |
| − |
| |
| − | Problem 8 (2015 imo/5):
| |
| − |
| |
| − | Let <math>\mathbb{R}</math> be the set of real numbers. Determine all functions <math>f</math>:<math>\mathbb{R}\rightarrow\mathbb{R}</math> satisfying the equation
| |
| − |
| |
| − | <math>f(x+f(x+y))+f(xy) = x+f(x+y)+yf(x)</math>
| |
| − |
| |
| − | for all real numbers <math>x</math> and <math>y</math>.
| |
| − |
| |
| − | Problem 9 (POINTWISE TRAP!!! 2014 usamo/2):
| |
| − |
| |
| − | Let <math>\mathbb{Z}</math> be the set of integers. Find all functions <math>f : \mathbb{Z} \rightarrow \mathbb{Z}</math> such that<cmath>xf(2f(y)-x)+y^2f(2x-f(y))=\frac{f(x)^2}{x}+f(yf(y))</cmath>for all <math>x, y \in \mathbb{Z}</math> with <math>x \neq 0</math>.
| |
| − |
| |
| − | Problem 10 (woah casework, 2012 usamo/4):
| |
| − |
| |
| − | Find all functions <math>f : \mathbb{Z}^+ \to \mathbb{Z}^+</math> (where <math>\mathbb{Z}^+</math> is the set of positive integers) such that <math>f(n!) = f(n)!</math> for all positive integers <math>n</math> and such that <math>m - n</math> divides <math>f(m) - f(n)</math> for all distinct positive integers <math>m</math>, <math>n</math>.
| |
| − |
| |
| − | Problem 11 (2012 imo/4, misplaced i think):
| |
| − |
| |
| − | Find all functions <math>f: \mathbb{Z} \to \mathbb{Z}</math> such that, for all integers <math>a, b,</math> and <math>c</math> that satisfy <math>a + b+ c = 0</math>, the following equality holds:<cmath>f(a)^2 + f(b)^2 + f(c)^2 = 2f(a)f(b) + 2f(b)f(c) + 2f(c)f(a).</cmath>
| |
| − |
| |
| − | Problem 12 (2011 imo/3):
| |
| − |
| |
| − | Let <math>f: \mathbb R \to \mathbb R</math> be a real-valued function defined on the set of real numbers that satisfies<cmath>f(x + y) \le yf(x) + f(f(x))</cmath>for all real numbers <math>x</math> and <math>y</math>. Prove that <math>f(x) = 0</math> for all <math>x \le 0</math>.
| |
| − |
| |
| − | Problem 13 (This was the first oly FE question I solved. That's why it's last :P 2010 imo/1):
| |
| − |
| |
| − | Find all function <math>f:\mathbb{R}\rightarrow\mathbb{R}</math> such that for all <math>x,y\in\mathbb{R}</math> the following equality holds
| |
| − |
| |
| − | <math>f(\left\lfloor x\right\rfloor y)=f(x)\left\lfloor f(y)\right\rfloor</math>
| |
| − |
| |
| − | where <math>\left\lfloor a\right\rfloor</math> is greatest integer not greater than <math>a.</math>
| |
| − |
| |
| − | ===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 (The pro ETHAN LIU says I don't even have to learn these :D)
| |
| − |
| |
| − | Hopefully they don't appear on usa(j)mo next year
| |
| − |
| |
| − | otherwise i'm screwed lol
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | ==COMBINATORICS==
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | .
| |
| − |
| |
| − | ;-;
| |
| − |
| |
| − | 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?
| |
| − |
| |
| − | ===Before oly===
| |
| − |
| |
| − | B. Problem 1
| |
| − |
| |
| − | How many ways can <math>5</math> people stand in a line?
| |
| − |
| |
| − | B. Problem 2
| |
| − |
| |
| − | How many ways can <math>5</math> people stand in a circle?
| |
| − |
| |
| − | B. Problem 3
| |
| − |
| |
| − | How many ways can you choose <math>3</math> indistinguishable cupcakes from <math>7</math> of them?
| |
| − |
| |
| − | B. Problem 4
| |
| − |
| |
| − | How many ways can you choose <math>3</math> distinguishable cupcakes from <math>7</math> of them?
| |
| − |
| |
| − | B. Problem 5 (2015 I/5):
| |
| − |
| |
| − | In a drawer Sandy has <math>5</math> pairs of socks, each pair a different color. On Monday Sandy selects two individual socks at random from the <math>10</math> socks in the drawer. On Tuesday Sandy selects <math>2</math> of the remaining <math>8</math> socks at random and on Wednesday two of the remaining <math>6</math> socks at random. The probability that Wednesday is the first day Sandy selects matching socks is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers, Find <math>m+n</math>
| |
| − |
| |
| − | B. Problem 6 (2015 10A/22):
| |
| − |
| |
| − | Eight people are sitting around a circular table, each holding a fair coin. All eight people flip their coins and those who flip heads stand while those who flip tails remain seated. What is the probability that no two adjacent people will stand?
| |
| − |
| |
| − | <math>\textbf{(A)}\dfrac{47}{256}\qquad\textbf{(B)}\dfrac{3}{16}\qquad\textbf{(C) }\dfrac{49}{256}\qquad\textbf{(D) }\dfrac{25}{128}\qquad\textbf{(E) }\dfrac{51}{256}</math>
| |
| − |
| |
| − | B. Problem 7 (2013 10A/24):
| |
| − |
| |
| − | Central High School is competing against Northern High School in a backgammon match. Each school has three players, and the contest rules require that each player play two games against each of the other school's players. The match takes place in six rounds, with three games played simultaneously in each round. In how many different ways can the match be scheduled?
| |
| − |
| |
| − | <math>\textbf{(A)}\ 540\qquad\textbf{(B)}\ 600\qquad\textbf{(C)}\ 720\qquad\textbf{(D)}\ 810\qquad\textbf{(E)}\ 900</math>
| |
| − |
| |
| − | B. Problem 8 (1988/10):
| |
| − |
| |
| − | A convex polyhedron has for its faces 12 squares, 8 regular hexagons, and 6 regular octagons. At each vertex of the polyhedron one square, one hexagon, and one octagon meet. How many segments joining vertices of the polyhedron lie in the interior of the polyhedron rather than along an edge or a face?
| |
| − |
| |
| − | B. Problem 9 (1997/10):
| |
| − |
| |
| − | Every card in a deck has a picture of one shape - circle, square, or triangle, which is painted in one of the three colors - red, blue, or green. Furthermore, each color is applied in one of three shades - light, medium, or dark. The deck has 27 cards, with every shape-color-shade combination represented. A set of three cards from the deck is called complementary if all of the following statements are true:
| |
| − |
| |
| − | i. Either each of the three cards has a different shape or all three of the card have the same shape.
| |
| − |
| |
| − | ii. Either each of the three cards has a different color or all three of the cards have the same color.
| |
| − |
| |
| − | iii. Either each of the three cards has a different shade or all three of the cards have the same shade.
| |
| − |
| |
| − | How many different complementary three-card sets are there?
| |
| − |
| |
| − | B. Problem 10 (2008 II/10):
| |
| − |
| |
| − | In a <math>4 \times 4</math> graph of points each a unit away from it's nearest neighbor, define a growing path to be a sequence of distinct points of the array with the property that the distance between consecutive points of the sequence is strictly increasing. Let <math>m</math> be the maximum possible number of points in a growing path, and let <math>r</math> be the number of growing paths consisting of exactly <math>m</math> points. Find <math>mr</math>.
| |
| − |
| |
| − | B. Problem 11 (2020 I/9):
| |
| − |
| |
| − | Let <math>S</math> be the set of positive integer divisors of <math>20^9.</math> Three numbers are chosen independently and at random with replacement from the set <math>S</math> and labeled <math>a_1,a_2,</math> and <math>a_3</math> in the order they are chosen. The probability that both <math>a_1</math> divides <math>a_2</math> and <math>a_2</math> divides <math>a_3</math> is <math>\tfrac{m}{n},</math> where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m.</math>
| |
| − |
| |
| − | B. Problem 12 (2011 II/12):
| |
| − |
| |
| − | Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate from another country be <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>.
| |
| − |
| |
| − | B. Problem 13 (2020 I/7):
| |
| − |
| |
| − | A club consisting of <math>11</math> men and <math>12</math> women needs to choose a committee from among its members so that the number of women on the committee is one more than the number of men on the committee. The committee could have as few as <math>1</math> member or as many as <math>23</math> members. Let <math>N</math> be the number of such committees that can be formed. Find the sum of the prime numbers that divide <math>N.</math>
| |
| − |
| |
| − | B. Problem 14 (this question sucks, that's why it's here. AOIME/9):
| |
| − |
| |
| − | While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.
| |
| − |
| |
| − | B. Problem 15 (2012 II/14):
| |
| − |
| |
| − | In a group of nine people each person shakes hands with exactly two of the other people from the group. Let <math>N</math> be the number of ways this handshaking can occur. Consider two handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. Find the remainder when <math>N</math> is divided by <math>1000</math>.
| |
| − |
| |
| − | B. Problem 16 (All combo is easy, sorry. 2011 II/14):
| |
| − |
| |
| − | There are <math>N</math> permutations <math>(a_{1}, a_{2}, ... , a_{30})</math> of <math>1, 2, \ldots, 30</math> such that for <math>m \in \left\{{2, 3, 5}\right\}</math>, <math>m</math> divides <math>a_{n+m} - a_{n}</math> for all integers <math>n</math> with <math>1 \leq n < n+m \leq 30</math>. Find the remainder when <math>N</math> is divided by <math>1000</math>.
| |
| − |
| |
| − | B. Problem 17 (2017 I/7, the only combo question I've ever liked on the AIME):
| |
| − |
| |
| − | For nonnegative integers <math>a</math> and <math>b</math> with <math>a + b \leq 6</math>, let <math>T(a, b) = \binom{6}{a} \binom{6}{b} \binom{6}{a + b}</math>. Let <math>S</math> denote the sum of all <math>T(a, b)</math>, where <math>a</math> and <math>b</math> are nonnegative integers with <math>a + b \leq 6</math>. Find the remainder when <math>S</math> is divided by <math>1000</math>.
| |
| − |
| |
| − | B. CHALLENGE PROBLEM 18 (2021 usajmo/6):
| |
| − |
| |
| − | Find <math>(\binom{33478293652874789324082988729347895769465312438698074}{174073247580238490758958739601257694})(107918163081-69^6)</math>
| |
| − |
| |
| − | B. Problem 19 (I guess this is combo??? ISL 2012/C1):
| |
| − |
| |
| − | Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers <math>x</math> and <math>y</math> such that <math>x>y</math> and <math>x</math> is to the left of <math>y</math>, and replaces the pair <math>(x,y)</math> by either <math>(y+1,x)</math> or <math>(x-1,x)</math>. Prove that she can perform only finitely many such iterations.
| |
| − |
| |
| − | B. Problem 20 (Is this combo though? usojmo 1):
| |
| − |
| |
| − | Let <math>n \geq 2</math> be an integer. Carl has <math>n</math> books arranged on a bookshelf. Each book has a height and a width. No two books have the same height, and no two books have the same width. Initially, the books are arranged in increasing order of height from left to right. In a move, Carl picks any two adjacent books where the left book is wider and shorter than the right book, and swaps their locations. Carl does this repeatedly until no further moves are possible. Prove that regardless of how Carl makes his moves, he must stop after a finite number of moves, and when he does stop, the books are sorted in increasing order of width from left to right.
| |
| − |
| |
| − | ===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 <math>\mathbb{E}</math>. Denote several events <math>e_1, e_2, e_3, . . . e_n</math> and their probabilities as <math>p_1, p_2, p_3, . . . p_n</math>. Then
| |
| − |
| |
| − | <math>\mathbb{E}=\sum_{i=1}^{n} e_ip_i</math>.
| |
| − |
| |
| − | 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 <math>9.7823489138728394</math>. Then there exists a person that has ate at least <math>10</math> cookies, and also a person who ate at most <math>9</math> cookies. It seems simple, but it's pretty powerful.
| |
| − |
| |
| − | Pigeonhole principle says that if you have <math>a</math> pigeonholes and <math>b</math> pigeons, there must exist a pigeonhole with at least ceiling(<math>\frac{b}{a}</math>) pigeons.
| |
| − |
| |
| − | This follows directly from our previous claim.
| |
| − |
| |
| − | Combo identities: You should probably know all of these from AIME...
| |
| − |
| |
| − | Ok. More advanced stuff, a.k.a. "Greedy" Algorithm:
| |
| − |
| |
| − | Repeat until you can't anymore
| |
| − |
| |
| − | (Well, that's basically it. Just do a thing like "If this thing is <math>3m</math>, make it into a <math>2m</math> and a <math>m</math>. Repeat until you can't anymore.)
| |
| − |
| |
| − | You'll actually need Jensen's Inequality a lot here, watch out!
| |
| − |
| |
| − | Counting in two ways. Prove that they are equal. Solve the problem . . . ?!?!?
| |
| − |
| |
| − | (That's pretty much all of olympiad combinatorics, for real. A bunch of random strategies! Innovative.)
| |
| − |
| |
| − | ===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 <math>m/n,</math> where <math>m</math> and <math>n</math> are relatively prime positive integers, find <math>m+n.</math>
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | The four aces divide the deck into <math>5</math> parts, and the expected number of cards in each of them is <math>\frac{48}{5}</math>. Therefore the answer is <math>\frac{48}{5}+3=\frac{63}{5} \implies \boxed{068}</math>
| |
| − |
| |
| − | Example 2 (2014 AIME I/15):
| |
| − |
| |
| − | For all positive integers <math>x</math>, let
| |
| − | <cmath>
| |
| − | f(x)=\begin{cases}1 &\mbox{if }x = 1\\ \frac x{10} &\mbox{if }x\mbox{ is divisible by 10}\\ x+1 &\mbox{otherwise}\end{cases}
| |
| − | </cmath>and define a sequence as follows: <math>x_1=x</math> and <math>x_{n+1}=f(x_n)</math> for all positive integers <math>n</math>. Let <math>d(x)</math> be the smallest <math>n</math> such that <math>x_n=1</math>. (For example, <math>d(100)=3</math> and <math>d(87)=7</math>.) Let <math>m</math> be the number of positive integers <math>x</math> such that <math>d(x)=20</math>. Find the sum of the distinct prime factors of <math>m</math>.
| |
| − |
| |
| − | Solution (Ripoff of AoPS Wiki, ik ik):
| |
| − |
| |
| − | This is equivalent of doing two operations, <math>(A) -1</math> and <math>(B) *10</math> <math>19</math> times, and seeing how many integers we can reach in this way. Note the first operation must be a <math>B</math>, so now we have <math>18</math> operations, starting at <math>10</math>.
| |
| − |
| |
| − | The first <math>9</math> operations: there are <math>2^9-1=511</math> in this case, since we can not have all <math>A</math>'s. Since we did at least <math>1 B</math> in the first <math>9</math> operations, it follows that we are now above <math>20</math>, so we do not need to worry about going back to <math>1</math> anymore.
| |
| − |
| |
| − | The last <math>9</math> operations: <math>2^9=512</math>. So far we have <math>(2^9)(2^9-1)=2^{18}-2^9</math> sequences.
| |
| − |
| |
| − | However, there is still more! If we have <math>10</math> or more <math>A</math>'s in a row, then the number was once divisible by <math>10</math>, but we didn't use any <math>B</math>'s, contradiction. There are <math>8</math> places to put our <math>BAAAAAAAAAA</math>, and <math>2^7</math> ways to label the other places. Thus our total is <math>2^{18}-2^{9}-2^{10}=(2^9-3)(2^9)=(509)(2^9)</math>, where <math>509</math> is prime. <math>509+2=\boxed{511}</math>.
| |
| − |
| |
| − | Example 3 (1987 imo/1):
| |
| − |
| |
| − | Let <math>p_{n}(k)</math> be the number of permutations of the set <math>\{1,2,3,\ldots,n\}</math> which have exactly <math>k</math> fixed points. Prove that <math>\sum_{k=0}^{n}k p_{n}(k)=n!</math>.
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | Look at the summation. It's actually just the expected number of fixed points, multiplied by the number of permutations, or <math>n!</math>.
| |
| − |
| |
| − | Because every integer has a <math>\frac{(n-1)!}{n!}=\frac{1}{n}</math> chance of being a fixed point, the expected number of fixed points is <math>1</math>, and multiplying by <math>n!</math>, we see that the requested sum is indeed <math>n!</math>.
| |
| − |
| |
| − | 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 <math>4\times 7</math> 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 <math>4\times 6</math> 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 <math>432</math> congruent arcs by <math>432</math> points. The points are colored in four colors such that some <math>108</math> points are colored Red, some <math>108</math> points are colored Green, some <math>108</math> points are colored Blue, and the remaining <math>108</math> 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 <math>1 \le r \le n</math> and consider all subsets of <math>r</math> elements of the set <math>\{ 1, 2, \ldots , n \}</math>. Each of these subsets has a smallest member. Let <math>F(n,r)</math> denote the arithmetic mean of these smallest numbers; prove that
| |
| − |
| |
| − | <math>F(n,r) = \frac{n+1}{r+1}.</math>
| |
| − |
| |
| − | Problem 5 (Well, it's trivial. Prove it! 2003 imo/1):
| |
| − |
| |
| − | <math>S</math> is the set <math>\{1, 2, 3, \dots ,1000000\}</math>. Show that for any subset <math>A</math> of <math>S</math> with <math>101</math> elements we can find <math>100</math> distinct elements <math>x_i</math> of <math>S</math>, such that the sets <math>\{a + x_i \mid a \in A\}</math> are all pairwise disjoint.
| |
| − |
| |
| − | Problem 6 (1998 imo/2):
| |
| − |
| |
| − | In a competition, there are <math>a</math> contestants and <math>b</math> judges, where <math>b \geq 3</math> is an odd integer. Each judge rates each contestant as either “pass” or “fail”. Suppose <math>k</math> is a number such that, for any two judges, their ratings coincide for at most <math>k</math> contestants. Prove that <math>\frac{k}{a} \geq \frac{b-1}{2b}</math>
| |
| − |
| |
| − | ===Problems-oof===
| |
| − |
| |
| − | Problem 7 (Construction! 2014 imo/5):
| |
| − |
| |
| − | For each positive integer <math>n</math>, the Bank of Cape Town issues coins of denomination <math>\tfrac{1}{n}</math>. Given a finite collection of such coins (of not necessarily different denominations) with total value at most <math>99+\tfrac{1}{2}</math>, prove that it is possible to split this collection into <math>100</math> or fewer groups, such that each group has total value at most <math>1</math>.
| |
| − |
| |
| − | Problem 8 (cough. 2016 imo/2):
| |
| − |
| |
| − | Find all integers <math>n</math> for which each cell of <math>n \times n</math> table can be filled with one of the letters <math>I,M</math> and <math>O</math> in such a way that:
| |
| − |
| |
| − | in each row and each column, one third of the entries are <math>I</math>, one third are <math>M</math> and one third are <math>O</math>; and
| |
| − |
| |
| − | in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are <math>I</math>, one third are <math>M</math> and one third are <math>O</math>.
| |
| − |
| |
| − | Problem 9 (I don't feel like putting this farther up. 2017 IMO/1):
| |
| − |
| |
| − | For each integer <math>a_0 > 1</math>, define the sequence <math>a_0, a_1, a_2, \ldots</math> for <math>n \geq 0</math> as
| |
| − | <cmath>a_{n+1} =
| |
| − | \begin{cases}
| |
| − | \sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer,} \\
| |
| − | a_n + 3 & \text{otherwise.}
| |
| − | \end{cases}
| |
| − | </cmath>Determine all values of <math>a_0</math> such that there exists a number <math>A</math> such that <math>a_n = A</math> for infinitely many values of <math>n</math>.
| |
| − |
| |
| − | Problem 10 (Cool!!! 2013 usajmo/2):
| |
| − |
| |
| − | Each cell of an <math>m\times n</math> board is filled with some nonnegative integer. Two numbers in the filling are said to be adjacent if their cells share a common side. (Note that two numbers in cells that share only a corner are not adjacent). The filling is called a garden if it satisfies the following two conditions:
| |
| − |
| |
| − | (i) The difference between any two adjacent numbers is either <math>0</math> or <math>1</math>.
| |
| − |
| |
| − | (ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to <math>0</math> .
| |
| − |
| |
| − | Determine the number of distinct gardens in terms of <math>m</math> and <math>n</math> .
| |
| − |
| |
| − | Problem 11 (This is literally trivial :P 2005 imo/2):
| |
| − |
| |
| − | Let <math>a_1,a_2,\ldots</math> be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer <math>n</math> the numbers <math>a_1,a_2,\ldots,a_n</math> leave <math>n</math> different remainders upon division by <math>n</math>.
| |
| − |
| |
| − | Prove that every integer occurs exactly once in the sequence <math>a_1,a_2,\ldots</math>.
| |
| − |
| |
| − | Problem 12 (Induction. 2010 usamo/2):
| |
| − |
| |
| − | There are <math>n</math> students standing in a circle, one behind the other. The students have heights <math>h_1 < h_2 < \ldots < h_n</math>. If a student with height <math>h_k</math> is standing directly behind a student with height <math>h_{k-2}</math> or less, the two students are permitted to switch places. Prove that it is not possible to make more than <math>\binom{n}{3}</math> such switches before reaching a position in which no further switches are possible.
| |
| − |
| |
| − | Problem 13 (Not even that hard, seriously. 2014 imo/6):
| |
| − |
| |
| − | A set of lines in the plane is in <math>\textit{general position}</math> if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite are; we call these its <math>\textit{finite regions}</math>. Prove that for all sufficiently large <math>n</math>, in any set of <math>n</math> lines in general position it is possible to colour at least <math>\sqrt{n}</math> of the lines blue in such a way that none of its finite regions has a completely blue boundary.
| |
| − |
| |
| − |
| |
| − | Problem 14 (2020 usojmo/1. trivial):
| |
| − |
| |
| − | Let <math>n \geq 2</math> be an integer. Carl has <math>n</math> books arranged on a bookshelf. Each book has a height and a width. No two books have the same height, and no two books have the same width. Initially, the books are arranged in increasing order of height from left to right. In a move, Carl picks any two adjacent books where the left book is wider and shorter than the right book, and swaps their locations. Carl does this repeatedly until no further moves are possible. Prove that regardless of how Carl makes his moves, he must stop after a finite number of moves, and when he does stop, the books are sorted in increasing order of width from left to right.
| |
| − |
| |
| − | Problem 15 (2020 usojmo/3):
| |
| − |
| |
| − | An empty <math>2020 \times 2020 \times 2020</math> cube is given, and a <math>2020 \times 2020</math> grid of square unit cells is drawn on each of its six faces. A [i]beam[/i] is a <math>1 \times 1 \times 2020</math> rectangular prism. Several beams are placed inside the cube subject to the following conditions:
| |
| − |
| |
| − | - The two <math>1 \times 1</math> faces of each beam coincide with unit cells lying on opposite faces of the cube. (Hence, there are <math>3 \cdot {2020}^2</math> possible positions for a beam.)
| |
| − |
| |
| − | - No two beams have intersecting interiors.
| |
| − |
| |
| − | - The interiors of each of the four <math>1 \times 2020</math> faces of each beam touch either a face of the cube or the interior of the face of another beam.
| |
| − |
| |
| − | What is the smallest positive number of beams that can be placed to satisfy these conditions?
| |
| − |
| |
| − | Problem 16 (2020 usojmo/5):
| |
| − |
| |
| − | Suppose that <math>(a_1,b_1),</math> <math>(a_2,b_2),</math> <math>\dots,</math> <math>(a_{100},b_{100})</math> are distinct ordered pairs of nonnegative integers. Let <math>N</math> denote the number of pairs of integers <math>(i,j)</math> satisfying <math>1\leq i<j\leq 100</math> and <math>|a_ib_j-a_jb_i|=1</math>. Determine the largest possible value of <math>N</math> over all possible choices of the <math>100</math> ordered pairs.
| |
| − |
| |
| − | ==Number Theory==
| |
| − |
| |
| − | Ok, I'm not sure of my skill level here... Number Theory is pretty easy, right?
| |
| − |
| |
| − | https://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/olympiad-number-theory.pdf (Highly recommended)
| |
| − |
| |
| − | ===Before Oly===
| |
| − |
| |
| − | B. Problem 1:
| |
| − |
| |
| − | What is <math>13</math> mod <math>5</math>?
| |
| − |
| |
| − | B. Problem 2:
| |
| − |
| |
| − | Chicken nuggets at McDonald's come in packs of <math>5</math> and <math>8</math>. What is the largest number of chicken nuggets you can not buy?
| |
| − |
| |
| − | B. Problem 3:
| |
| − |
| |
| − | Find the last two digits of <math>2^42</math>.
| |
| − |
| |
| − | B. Problem 4 (Classic):
| |
| − |
| |
| − | Find <math>2^{3^{4^{5^{6^{7}}}}}</math> mod <math>1000</math>.
| |
| − |
| |
| − | B. Problem 5 (2020 AOIME/1):
| |
| − |
| |
| − | Find the number of ordered pairs of positive integers <math>(m,n)</math> such that <math>{m^2n = 20 ^{20}}</math>.
| |
| − |
| |
| − | B. Problem 6 (2020 AOIME/5):
| |
| − |
| |
| − | For each positive integer <math>n</math>, let <math>f(n)</math> be the sum of the digits in the base-four representation of <math>n</math> and let <math>g(n)</math> be the sum of the digits in the base-eight representation of <math>f(n)</math>. For example, <math>f(2020) = f(133210_{\text{four}}) = 10 = 12_{\text{eight}}</math>, and <math>g(2020) = \text{the digit sum of }12_{\text{eight}} = 3</math>. Let <math>N</math> be the least value of <math>n</math> such that the base-sixteen representation of <math>g(n)</math> cannot be expressed using only the digits <math>0</math> through <math>9</math>. Find the remainder when <math>N</math> is divided by <math>1000</math>.
| |
| − |
| |
| − | B. Problem 7 (2020 AOIME/6):
| |
| − |
| |
| − | Define a sequence recursively by <math>t_1 = 20</math>, <math>t_2 = 21</math>, and<cmath>t_n = \frac{5t_{n-1}+1}{25t_{n-2}}</cmath>for all <math>n \ge 3</math>. Then <math>t_{2020}</math> can be written as <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime positive integers. Find <math>p+q</math>.
| |
| − |
| |
| − | B. Problem 8 (2020 AOIME/10):
| |
| − |
| |
| − | Find the sum of all positive integers <math>n</math> such that when <math>1^3+2^3+3^3+\cdots +n^3</math> is divided by <math>n+5</math>, the remainder is <math>17</math>.
| |
| − |
| |
| − | B. Problem 9 (2018 10B/19):
| |
| − |
| |
| − | Joey and Chloe and their daughter Zoe all have the same birthday. Joey is <math>1</math> year older than Chloe, and Zoe is exactly <math>1</math> year old today. Today is the first of the <math>9</math> birthdays on which Chloe's age will be an integral multiple of Zoe's age. What will be the sum of the two digits of Joey's age the next time his age is a multiple of Zoe's age?
| |
| − |
| |
| − | B. Problem 10 (2018 10A/25):
| |
| − |
| |
| − | For a positive integer <math>n</math> and nonzero digits <math>a</math>, <math>b</math>, and <math>c</math>, let <math>A_n</math> be the <math>n</math>-digit integer each of whose digits is equal to <math>a</math>; let <math>B_n</math> be the <math>n</math>-digit integer each of whose digits is equal to <math>b</math>, and let <math>C_n</math> be the <math>2n</math>-digit (not <math>n</math>-digit) integer each of whose digits is equal to <math>c</math>. What is the greatest possible value of <math>a + b + c</math> for which there are at least two values of <math>n</math> such that <math>C_n - B_n = A_n^2</math>?
| |
| − |
| |
| − | B. Problem 11 (2016 II/11):
| |
| − |
| |
| − | For positive integers <math>N</math> and <math>k</math>, define <math>N</math> to be <math>k</math>-nice if there exists a positive integer <math>a</math> such that <math>a^{k}</math> has exactly <math>N</math> positive divisors. Find the number of positive integers less than <math>1000</math> that are neither <math>7</math>-nice nor <math>8</math>-nice.
| |
| − |
| |
| − | B. Problem 12 (2014 I/8):
| |
| − |
| |
| − | The positive integers <math>N</math> and <math>N^2</math> both end in the same sequence of four digits <math>abcd</math> when written in base <math>10</math>, where digit <math>a</math> is not zero. Find the three-digit number <math>abc</math>.
| |
| − |
| |
| − | B. Problem 13 (2011 I/11):
| |
| − |
| |
| − | Let <math>R</math> be the set of all possible remainders when a number of the form <math>2^n</math>, <math>n</math> a nonnegative integer, is divided by <math>1000</math>. Let <math>S</math> be the sum of the elements in <math>R</math>. Find the remainder when <math>S</math> is divided by <math>1000</math>.
| |
| − |
| |
| − | B. Problem 14 (2010 I/12):
| |
| − |
| |
| − | Let <math>m \ge 3</math> be an integer and let <math>S = \{3,4,5,\ldots,m\}</math>. Find the smallest value of <math>m</math> such that for every partition of <math>S</math> into two subsets, at least one of the subsets contains integers <math>a</math>, <math>b</math>, and <math>c</math> (not necessarily distinct) such that <math>ab = c</math>.
| |
| − |
| |
| − | Note: a partition of <math>S</math> is a pair of sets <math>A</math>, <math>B</math> such that <math>A \cap B = \emptyset</math>, <math>A \cup B = S</math>.
| |
| − |
| |
| − | B. Problem 15 (2006 I/13):
| |
| − |
| |
| − | For each even positive integer <math>x</math>, let <math>g(x)</math> denote the greatest power of 2 that divides <math>x.</math> For example, <math>g(20)=4</math> and <math>g(16)=16.</math> For each positive integer <math>n,</math> let <math>S_n=\sum_{k=1}^{2^{n-1}}g(2k).</math> Find the greatest integer <math>n</math> less than 1000 such that <math>S_n</math> is a perfect square.
| |
| − |
| |
| − |
| |
| − | B. Problem 16 (2006 II/14):
| |
| − |
| |
| − | Let <math>S_n</math> be the sum of the reciprocals of the non-zero digits of the integers from <math>1</math> to <math>10^n</math> inclusive. Find the smallest positive integer <math>n</math> for which <math>S_n</math> is an integer.
| |
| − |
| |
| − | B. Problem 17 (2008 II/15):
| |
| − |
| |
| − | Find the largest integer <math>n</math> satisfying the following conditions:
| |
| − |
| |
| − | (i) <math>n^2</math> can be expressed as the difference of two consecutive cubes
| |
| − |
| |
| − | (ii) <math>2n + 79</math> is a perfect square.
| |
| − |
| |
| − | B. Problem 18 (2021 usajmo/3):
| |
| − |
| |
| − | What is <math>85317422151*2121212121212121^{6934209748359420}</math> mod <math>69</math>? Specify how you got your answer. Write at least <math>3</math> essays on all aspects of the Measles morbillivirus as well.
| |
| − |
| |
| − | B. Problem 19 (1959 imo/1):
| |
| − |
| |
| − | Prove that the fraction <math>\frac{21n+4}{14n+3}</math> is irreducible for every natural number <math>n</math>.
| |
| − |
| |
| − | B. Problem 20 (1975 imo/4):
| |
| − |
| |
| − | When <math>4444^{4444}</math> is written in decimal notation, the sum of its digits is <math>A</math>. Let <math>B</math> be the sum of the digits of <math>A</math>. Find the sum of the digits of <math>B</math>. (<math>A</math> and <math>B</math> are written in decimal notation.)
| |
| − |
| |
| − | ==Exponents==
| |
| − |
| |
| − | ===Basics of NT===
| |
| − |
| |
| − | If <math>a=kb+r</math>, for some integer <math>a,k,r</math>, and positive integer <math>b</math>, then we can say <math>a \equiv r \pmod{b}</math>. We can add, subtract, and multiply in the mods.
| |
| − |
| |
| − | Perfect squares can never be <math>2 \pmod{3}</math>. <math>1,4,9,16,25,36,49,64 . . . </math> corresponds to <math>1,1,0,1,1,0,1,1,0, . . .</math>. Notice how they repeat every <math>3</math>, as all <math>1,4,7,10 . . . </math> are <math>1 \pmod{3}</math>, so since we can multiply, they will all be <math>1*1 \equiv 1 \pmod{3}</math>. Similarly, all of <math>2,5,8,11 . . .</math> will be <math>2 \pmod{3}</math>, so their squares will be <math>2*2 \equiv 4 \equiv 1 \pmod{3}</math>.
| |
| − |
| |
| − | (Exercise): Prove that no squares are congruent to <math>2 \pmod{4}</math> or <math>3 \pmod{4}</math>.
| |
| − |
| |
| − | Chinese remainder theorem (CRT) states that for relatively prime <math>b_i</math>, the congruences
| |
| − | <math>x \equiv a_1 \pmod{b_1}</math>
| |
| − | <math>x \equiv a_2 \pmod{b_2}</math>
| |
| − | <math>x \equiv a_3 \pmod{b_3}</math>
| |
| − | ...
| |
| − | <math>x \equiv a_n \pmod{b_n}</math>
| |
| − | has congruence for <math>x</math>, and it is <math>\pmod{b_1b_2b_3 . . . b_n}</math>.
| |
| − |
| |
| − | ===Orders===
| |
| − |
| |
| − | <math>\phi(n)</math> (totient of n) is the number positive integers less than <math>n</math> that are relatively prime to <math>n</math>.
| |
| − |
| |
| − | Immediately from PIE,
| |
| − |
| |
| − | if <math>n =p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}</math> where the <math>p_i</math> are distinct primes, <cmath>\phi(n)= n\left(1-\frac{1}{p_1} \right) \left(1-\frac{1}{p_2} \right)\cdots \left(1-\frac{1}{p_m}\right).</cmath>
| |
| − |
| |
| − | Euler's Totient Theorem states that if <math>a</math> and <math>n</math> are relatively prime positive integers, then <math>a^{\phi(n)}</math> is <math>1 \pmod{n}</math>.
| |
| − |
| |
| − | A direct result is Fermat's Little Theorem, which states that if <math>m</math> is prime, <math>a^{m-1}</math> is <math>1 \pmod{m}</math>.
| |
| − |
| |
| − | The order of an integer <math>a</math> modulo a prime <math>p</math> is the smallest positive integer <math>e</math> such that <math>a^e</math> is <math>1</math> <math>\pmod{p}</math>.
| |
| − |
| |
| − | Primitive Roots: Let <math>p</math> be a prime. Then there exists a residue <math>m</math> such that <math>m</math> has order <math>p-1</math>.
| |
| − |
| |
| − | Example 1 (2016 HMMT Feb. Team/2):
| |
| − |
| |
| − | For positive integers <math>n</math>, let <math>c_n</math> be the smallest positive integer for which <math>n^{c_n}-1</math> is divisible by <math>210</math>, if such a positive integer exists, and <math>c_n = 0</math> otherwise. What is <math>c_1 + c_2 + . . . + c_{210}</math>?
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | <math>c_n</math> is nonzero if and only if <math>c_n</math> is relatively prime to <math>210</math>, so we'll only consider those numbers.
| |
| − |
| |
| − | The orders modulo <math>2,3,5,7</math> are <math>(1), (1,2), (1,4,4,2), (1,3,6,3,6,2)</math>, respectively. Now we compute the LCM, picking one from each of them (noting that by Chinese Remainder Theorem, they each generate a unique number). For <math>5</math> and <math>7</math>, we make a table.
| |
| − |
| |
| − | Adding them all up, we get <math>161</math>. This is for orders of <math>1</math> for each of modulo <math>2</math> and <math>3</math>. If we have a order of <math>2</math> for modulo <math>3</math>, in the first row we change the <math>(1,3,3)</math> to a <math>(2,6,6)</math>, adding <math>7</math>, so the total is <math>161*2+7=\boxed{329}</math>.
| |
| − |
| |
| − | Problem 1:
| |
| − |
| |
| − | Find all positive integers <math>n</math> such that <math>n</math> divides <math>2^n-1</math>.
| |
| − |
| |
| − | Problem 2 (ISL 2000 A1):
| |
| − |
| |
| − | Determine all positive integers <math> n\geq 2</math> that satisfy the following condition: for all <math> a</math> and <math> b</math> relatively prime to <math>n</math> we have <cmath>a \equiv b \pmod n\qquad\text{if and only if}\qquad ab\equiv 1 \pmod n.</cmath>
| |
| − |
| |
| − | Problem 3 (Fermat's Christmas Theorem):
| |
| − |
| |
| − | Let <math>a</math> and <math>b</math> be positive integers, and let <math>p \equiv 3 \pmod{4}</math> be a prime. Suppose <math>p</math> divides <math>n = a^2 + b^2</math>. Prove that <math>p</math> divides both <math>a</math> and <math>b</math>.
| |
| − |
| |
| − | ===LTE===
| |
| − |
| |
| − | Define <math>v_p(n)</math> for prime <math>p</math> and positive integer <math>n</math> to be the highest power of <math>p</math> dividing <math>n</math>. For example, <math>v_2(192)=6</math>.
| |
| − |
| |
| − | LTE lemma (Lifting The Exponent) says that if <math>a</math> and <math>b</math> are both <math>m \pmod{p}</math>, <math>m \neq 0</math>,
| |
| − | If <math>p \neq 2</math>, <math>v_p(a^n-b^n)=v_p(a-b)+v_p(n)</math>.
| |
| − | If <math>p=2</math> and <math>n</math> is odd, <math>v_2(a^n-b^n)=v_2(a-b)</math>. If <math>n</math> is even, <math>v_p(a^n-b^n)=v_p(a-b)+v_p(a+b)+v_p(n)-1</math>.
| |
| − |
| |
| − | The proofs are left as an exercise. Just expand <math>a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b . . . b^{n-1})</math>.
| |
| − |
| |
| − | Zsigmondy theorem:
| |
| − | (i) For any sequence <math>c_n=a^n-b^n</math> (<math>a>b \geq 1</math>, <math>a</math> and <math>b</math> are relatively prime), there exists a prime <math>p|c</math> such that <math>p</math> is not a factor of any other terms of the terms before <math>a_m</math> in the sequence with the exception of <math>2^6-1^6</math>, <math>n=2</math>, and <math>a+b</math> is a power of <math>2</math>.
| |
| − | (ii) For any sequence <math>c_n=a^n+b^n</math>, the same holds but the exceptions are <math>2^3+1^3=9</math>.
| |
| − |
| |
| − | Example 1 (2018 I/11 -showcasing the power):
| |
| − |
| |
| − | Find the least positive integer <math>n</math> such that when <math>3^n</math> is written in base <math>143</math>, its two right-most digits in base <math>143</math> are <math>01</math>.
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | By inspection, all <math>5|n</math> are <math>1 \pmod{121}</math>. Now, all <math>3|n</math> are <math>1 \pmod{13}</math>. Using LTE, <cmath>v_p(27^{n}-1^{n})=v_p(26)+v_p(n)=1+v_p(n) \implies 13|n</cmath>. <math>13*3*5=\boxed{195}</math>.
| |
| − |
| |
| − | Problem 4 (2020 I/12, similar flavor...):
| |
| − |
| |
| − | Let <math>n</math> be the least positive integer for which <math>149^n-2^n</math> is divisible by <math>3^3\cdot5^5\cdot7^7.</math> Find the number of positive integer divisors of <math>n.</math>
| |
| − |
| |
| − | Problem 5 (2008 tst/4):
| |
| − |
| |
| − | Prove that for no integer <math> n</math> is <math> n^7 + 7</math> a perfect square.
| |
| − |
| |
| − | Example 2 (1991 isl/18?):
| |
| − |
| |
| − | Find the highest degree <math> k</math> of <math> 1991</math> for which <math> 1991^k</math> divides the number<cmath> 1990^{1991^{1992}} + 1992^{1991^{1990}}.</cmath>
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | -<math> 1991 = 11 \times 181</math>
| |
| − |
| |
| − | -<math>1990^{1991^{1992}} + 1992^{1991^{1990}}= (1990^{1991^{2}})^{1991^{1990}} - ( - 1992)^{1991^{1990}}.</math>
| |
| − |
| |
| − | -Since <math>(1990^{1991^{2}}) - ( - 1992) = 1991 [(\sum_{i = 0}^{1991^{2} - 1}( - 1990)^{i}) + 1]</math> is divisible by <math>1991</math> but not <math>1991^2</math>, by LTE (On <math>11</math> and <math>181</math>) <math>k=\boxed{1991}</math>
| |
| − |
| |
| − | Problem 6 (2016 usamo/2):
| |
| − |
| |
| − | Prove that for any positive integer <math>k</math>,<cmath>(k^2)!\cdot\prod_{j=0}^{k-1}\frac{j!}{(j+k)!}</cmath>is an integer.
| |
| − |
| |
| − | Problem 7 (1990 imo/3):
| |
| − |
| |
| − | Determine all integers <math>n \geq 1</math> such that <math>\frac{2^n+1}{n^2}</math> is an integer.
| |
| − |
| |
| − | Problem 8 (2000 imo/5):
| |
| − |
| |
| − | Does there exist a positive integer <math> n</math> such that <math> n</math> has exactly <math>2000</math> prime divisors and <math> n</math> divides <math> 2^n + 1</math>?
| |
| − |
| |
| − | Problem 9 (ISL 2014/N5):
| |
| − |
| |
| − | Find all triples <math>(p, x, y)</math> consisting of a prime number <math>p</math> and two positive integers <math>x</math> and <math>y</math> such that <math>x^{p -1} + y</math> and <math>x + y^ {p -1}</math> are both powers of <math>p</math>.
| |
| − |
| |
| − | ===Other NT===
| |
| − |
| |
| − | Example 1 (ISL 2007/N5):
| |
| − |
| |
| − | Find all surjective functions <math> f: \mathbb{N} \to \mathbb{N}</math> such that for every <math> m,n \in \mathbb{N}</math> and every prime <math> p,</math> the number <math> f(m + n)</math> is divisible by <math> p</math> if and only if <math> f(m) + f(n)</math> is divisible by <math> p</math>.
| |
| − |
| |
| − | Solution:
| |
| − |
| |
| − | -Assume <math>p|f(1)</math>. Then, if <math>p|f(k)</math>, <math>p|f(k+1)</math> by the given. By induction, this holds for all <math>n</math>, but <math>f</math> is surjective, contradiction <math>\implies</math> <math>f(1)=1</math>. (1)
| |
| − |
| |
| − | -Assume <math>m>n</math> and <math>p|f(m)-f(n)</math>. By subjectivity, there exists a <math>k</math> such that <math>p|f(m)+f(k)</math>. Thus <math>p|f(n)+f(k)</math> as well, so <math>p| f(m+k)</math> and <math>p|f(n+k)</math>. Now we have <math>p|f(m+k)=f(m-n+n+k)</math>, so <math>p|f(m-n)+f(n+k) \implies p|f(m-n)</math>. Therefore <math>p|f(m)-f(n) \implies p|f(m-n)</math>. (2)
| |
| − |
| |
| − | -Assume <math>f(a)=f(b), a>b</math>. Choose a prime <math>p>f(a-b)</math>. Since <math>p|0=f(a)-f(b)</math>, (2) means <math>p|f(a-b)</math>, contradiction. Thus <math>f</math> is injective (3)
| |
| − |
| |
| − | -Assume <math>p|f(n+1)-f(n)</math> for some prime <math>p</math>. By (1), (2), <math>p|1</math>, contradiction <math>\implies |f(n+1)-f(n)|=1</math> (4).
| |
| − |
| |
| − | By (1), <math>f(1)=1</math>. By (4), <math>f(2)=2</math>. Since <math>f</math> is actually bijective by (3), this means that <math>\boxed{f(n)=n}</math> (works)is the only solution. <math>\blacksquare</math>
| |
| − |
| |
| − | Example 2 (usajmo 2011/1):
| |
| − |
| |
| − | Find all positive integers <math>n</math> for which <math>2^n + 12^n + 2011^n</math> is a perfect square.
| |
| − |
| |
| − | -If <math>n</math> is even, taking modulo <math>3</math> results in the expression being <math>2 \pmod{3}</math>, contradiction. Thus <math>n</math> is odd.
| |
| − |
| |
| − | -If <math>n > 1</math> is odd, then the expression is <math>3 \pmod{4}</math>, contradiction.
| |
| − |
| |
| − | -If <math>n=1</math>, the expression is <math>2025=45^2</math>, so the only solution is <math>\boxed{n=1}</math>.
| |
| − |
| |
| − | ==Appendix A. Induction==
| |
| − |
| |
| − | Induction:
| |
| − |
| |
| − | Show that an event <math>P(n)</math> is true for the [base case] (most likely when <math>n=1</math>).
| |
| − |
| |
| − | Assume that <math>P(n)</math> is true for <math>n=k</math> (This is called the [inductive hypothesis]). Then, show that it is true for <math>n=k+1</math> (This is called the [inductive step]). Since it was true for <math>n=1</math>, it is also true for <math>n=2</math>, <math>n=3</math>, . . . and so we are done.
| |
| − |
| |
| − | Strong induction:
| |
| − |
| |
| − | Again show that an event <math>P(n)</math> is true for the base case.
| |
| − |
| |
| − | Then, assume that <math>P(n)</math> is true for <math>1,2,3 . . . k</math>. Then show that it is true for <math>k+1</math>. Since it was true for <math>1</math>, it is true for <math>2</math>, <math>3</math> (because <math>1</math> and <math>2</math> are true), and so on, so we are done again.
| |
| − |
| |
| − | Example 1:
| |
| − |
| |
| − | Prove that <math>1+2+3+ . . . n=\frac{n(n+1)}{2}</math> for all <math>n \in \mathbb{N}</math>.
| |
| − |
| |
| − | Solution (Induction):
| |
| − |
| |
| − | (Base Case): <math>\frac{1(2)}{2}=1</math>
| |
| − |
| |
| − | (Inductive Hypothesis): Now assume <math>1+2+3+ . . . k=\frac{k(k+1)}{2}</math> for some <math>k</math>.
| |
| − |
| |
| − | (Inductive Step): Then, by the inductive hypothesis, <math>1+2+3+ . . . k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}</math>.
| |
| − |
| |
| − | (This might be optional, still do it of course): By the principle of mathematical induction, we are done.
| |
| − |
| |
| − | Example 2 (Fundamental Theorem of Arithmetic):
| |
| − |
| |
| − | Every integer <math>n \geq 2</math> can be written uniquely as the product of prime numbers.
| |
| − |
| |
| − | Solution (Strong Induction):
| |
| − |
| |
| − | (Base Case): This is clearly true for <math>n=2</math>.
| |
| − |
| |
| − | (Inductive Hypothesis): Now assume that it is true for <math>n=2,3,4, . . . k</math>.
| |
| − |
| |
| − | (Inductive Step): If <math>k+1</math> is prime, we are done. If <math>k+1</math> is not prime, it has a smallest prime factor, which we will denote as <math>p</math>. Then <math>k+1=pN</math> for some <math>N</math>. Then, since <math>N \in 2,3,4, . . . k</math>, it can be expressed as the product of prime numbers and therefore <math>k+1=pN</math> can also be expressed as the product of prime numbers, and we are done by Strong Induction.
| |
| − |
| |
| − | Problem 1:
| |
| − |
| |
| − | Prove that <math>1^2+2^2+3^2 . . . n^2=\frac{(n)(n+1)(2n+1)}{6}</math>.
| |
| − |
| |
| − | ==Appendix B. Hints==
| |
| − |
| |
| − | All the pro people do this, so lets do it
| |
| − |
| |
| − | ~Lcz 6/24/2020, 4:26 PM CST
| |
| − |
| |
| − | Wait actually this is going to be hard. Maybe later
| |
| − |
| |
| − | ~Lcz 7/3/2020, 9:07 AM CST
| |
