Difference between revisions of "User:Lcz"
(→Now this stuff is kind of hard) |
(→I.Basics) |
||
Line 135: | Line 135: | ||
==I.Basics== | ==I.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> | ||
+ | |||
+ | 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 positive reals <math>(x_n), (a_n), (b_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>, | ||
+ | |||
+ | (\[\sum_{\text{cyc}} {a_1}^3)(\[\sum_{\text{cyc}} {a_2}^3)(\[\sum_{\text{cyc}} {a_3}^3) <math>\geq (a_1b_1c_1+a_2b_2c_2+a_3b_3c_3)^3 | ||
+ | |||
+ | 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. | ||
Example 1: | Example 1: | ||
− | (Evan Chen) Let <math>a,b,c>0< | + | (Evan Chen) Let </math>a,b,c>0<math> with </math>\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1<math>. Prove that </math>(a+1)(b+1)(c+1) \geq 64<math> |
Solution: | Solution: | ||
− | We need to try to homogenize this somehow. Plugging in the expression for on the LHS for <math>1< | + | We need to try to homogenize this somehow. Plugging in the expression for on the LHS for </math>1<math> won't work. If we try to do something on the left side, we'll still have a degree </math>3>-1<math>. Wait a second, why are they all </math>a+1<math>'s? Let's try to get rid of the </math>a+1<math>'s first. Well, if we add </math>3<math> to both sides of the given condition, we get |
− | <math>\frac{a+1}{a}+\frac{b+1}{b}+\frac{c+1}{c}=4< | + | </math>\frac{a+1}{a}+\frac{b+1}{b}+\frac{c+1}{c}=4<math>, </math>\frac{(a+1)(b+1)(c+1)}{abc} \geq \frac{64}{27}<math>, |
− | <math>abc \geq 27< | + | </math>abc \geq 27<math> |
By AM-GM. | By AM-GM. | ||
− | Obviously the trivial solution <math>(3,3,3)< | + | Obviously the trivial solution </math>(3,3,3)<math> satisfies this, so we haven't made any silly mistakes. We still haven't homogenized, but now the path is clear. Multiplying both sides by |
− | <math>(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})^3=1< | + | </math>(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})^3=1<math>, we get |
− | <math>\frac{(ab+bc+ac)^3}{(abc)^2} \geq 27< | + | </math>\frac{(ab+bc+ac)^3}{(abc)^2} \geq 27<math>, </math>(\frac{ab+bc+ac}{3})^3 \geq (abc)^2<math>, </math>(\frac{ab+bc+ac}{3}) \geq (abc)^{2/3}<math> |
Which is true from AM-GM. We shall now introduce Muirhead's... | Which is true from AM-GM. We shall now introduce Muirhead's... | ||
Line 159: | Line 191: | ||
Example 2: | Example 2: | ||
− | Let <math>a,b,c>0< | + | Let </math>a,b,c>0<math> (Again Evan Chen) and </math>abc=1<math>. Prove that </math>a^2+b^2+c^2 \geq a+b+c<math>. |
Solution: | Solution: | ||
First we homogenize: | First we homogenize: | ||
− | <math>a^2+b^2+c^2 \geq (a+b+c)(abc)^{1/3}< | + | </math>a^2+b^2+c^2 \geq (a+b+c)(abc)^{1/3}<math> |
− | Which is true because <math>(2,0,0)< | + | Which is true because </math>(2,0,0)<math> majorizes </math>(\frac{4}{3}, \frac{1}{3}, \frac{1}{3})<math> |
Line 173: | Line 205: | ||
Problem 1: (2009 usamo/4): | Problem 1: (2009 usamo/4): | ||
− | For <math>n \ge 2< | + | 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> (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)< | + | Prove that </math>\text{max}(a_1, a_2, ... ,a_n) \le 4 \text{min}(a_1, a_2, ... , a_n)<math>. |
Try to solve this on your own! Very cute problem. | Try to solve this on your own! Very cute problem. | ||
− | |||
Example 3 (2004 usamo/5) | Example 3 (2004 usamo/5) | ||
− | Let <math>a< | + | 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>(a^5 - a^2 + 3)(b^5 - b^2 + 3)(c^5 - c^2 + 3) \ge (a+b+c)^3<math>. |
Solution: | Solution: | ||
− | 1. The <math>(a+b+c)< | + | 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< | + | 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< | + | Now note that if </math>a<1<math>, this is true, if </math>a=1<math>, this is true, and if </math>a>1$, this is true as well, and as we have exhausted all cases, we are done. |
==I.More advanced stuff, learn some calculus== | ==I.More advanced stuff, learn some calculus== |
Revision as of 10:57, 13 June 2020
Contents
- 1 Introduction
- 2 Disclaimer
- 3 ALGEBRA
- 4 A.Before oly...
- 5 Inequalities
- 6 I.Basics
- 7 I.More advanced stuff, learn some calculus
- 8 I.Problems
- 9 I.Extra
- 10 Function Equations
- 11 F.Intro
- 12 F.Ok these things are sort of cool
- 13 F.They're not that cool actually
- 14 F.Problems
- 15 F.Extra
- 16 MONSTROUS Functional Equations
- 17 COMBINATORICS
- 18 C.Before oly
- 19 C.Basics
- 20 C.This stuff is pretty easy
- 21 C.oof
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 if
.
B. Problem 2:
Find the sum of all such that
.
B. Problem 3 (troll):
Find the sum of all in
such that
B. Problem 4 (2018 I/6)
Let be the number of complex numbers
with the properties that
and
is a real number. Find the remainder when
is divided by
.
B. Problem 5 (AOIME/8 sigh...)
Define a sequence recursively by and
for integers
. Find the least value of
such that the sum of the zeros of
exceeds
.
B. Problem 6 (AOIME/11 bash-ish?)
Let , and let
and
be two quadratic polynomials also with the coefficient of
equal to
. David computes each of the three sums
,
, and
and is surprised to find that each pair of these sums has a common root, and these three common roots are distinct. If
, then
, where
and
are relatively prime positive integers. Find
.
B. Problem 7 (1984/15):
Determine if
B. Problem 8 (2020 I/14):
Let be a quadratic polynomial with complex coefficients whose
coefficient is
Suppose the equation
has four distinct solutions,
Find the sum of all possible values of
B. Problem 9 (HINT: THIS IS GEOMETRY 2006 II/15):
Given that and
are real numbers that satisfy:
and that
where
and
are positive integers and
is not divisible by the square of any prime, find
B. Problem 10 (2011 I/15):
For some integer , the polynomial
has the three integer roots
,
, and
. Find
.
B. Problem 11 (2014 I/13):
The polynomial has
complex roots of the form
with
and
Given that
where
and
are relatively prime positive integers, find
B. Problem 12 (2007 I/14):
A sequence is defined over non-negative integral indexes in the following way: ,
.
Find the greatest integer that does not exceed
B. Problem 13 (2007 II/14):
Let be a polynomial with real coefficients such that
and for all
,
Find
B. Problem 14 (Gotta save the easy ones for the end, 2010 I/14):
For each positive integer n, let . Find the largest value of
for which
.
B. Problem 15 (2021 usamo/6):
Dad and mom are playing outside while you are in a conference call discussing serious matters.
What is ?
B. Problem 16 (For difficulty of 16, 2016 II/15):
For let
and
. Let
be positive real numbers such that
and
. The maximum possible value of
, where
and
are relatively prime positive integers. Find
.
Inequalities
Yay! I love inequalities. Clever algebraic manipulation+thereoms is all you need. It all comes from experience though...
I.Basics
Note that the set is
.
. It is "symmetric".
. It is "cyclic".
AM-GM says that for nonnegative reals, their Arithmetic Mean is
their Geometric Mean.
.
Cauchy's Inequality says that for nonnegative reals,
![]()
Titu's lemma follows directly from Cauchy, it says for the same variables,
We say a setmajorizes
if
(a) the sum of the elements are the same.
(b) the elements are in decreasing order.
(c) the leftmost sums ofare
those of
.
For example, majorizes
and
majorizes
.
Muirhead's Inequality says that for positive reals, where
majorizes
,
Holder's Inequality (for, you'll probably only need it for
, plus this is the "basics" chapter anyway...) says that
for positive reals ,
(\[\sum_{\text{cyc}} {a_1}^3)(\[\sum_{\text{cyc}} {a_2}^3)(\[\sum_{\text{cyc}} {a_3}^3) $\geq (a_1b_1c_1+a_2b_2c_2+a_3b_3c_3)^3
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.
Example 1:
(Evan Chen) Let$ (Error compiling LaTeX. Unknown error_msg)a,b,c>0\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1
(a+1)(b+1)(c+1) \geq 64
1
3>-1
a+1
a+1
3
\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
(3,3,3)
(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})^3=1
\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$ (Error compiling LaTeX. Unknown error_msg)a,b,c>0abc=1
a^2+b^2+c^2 \geq a+b+c$.
Solution:
First we homogenize:$ (Error compiling LaTeX. Unknown error_msg)a^2+b^2+c^2 \geq (a+b+c)(abc)^{1/3}(2,0,0)
(\frac{4}{3}, \frac{1}{3}, \frac{1}{3})$Cauchy:
Problem 1: (2009 usamo/4):
For$ (Error compiling LaTeX. Unknown error_msg)n \ge 2a_1
a_2
a_n
(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
\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.
Example 3 (2004 usamo/5)
Let$ (Error compiling LaTeX. Unknown error_msg)ab
c
(a^5 - a^2 + 3)(b^5 - b^2 + 3)(c^5 - c^2 + 3) \ge (a+b+c)^3$.
Solution:
1. The$ (Error compiling LaTeX. Unknown error_msg)(a+b+c)(a^3+1+1) . . .$on the LHS.
2. Now all we have to prove is that$ (Error compiling LaTeX. Unknown error_msg)a^5-a^3-a^2+1 \geq 0(a^3-1)(a^2-1) \geq 0
a<1
a=1
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 ofis
![]()
Adding and other stuff works in the same way. You also probably need to know
-Product Rule:![]()
-Quotient Rule:![]()
-Summing:![]()
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 ifis a convex function in the interval
, for all
in
,
![]()
The opposite holds if is concave.
Karamata's inequality says that ifis convex in the interval
, the sequence
majorizes
,, and all
are in
,
![]()
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
Problem 3: Using Jensen's and Holder's, solve 2001 IMO/2:
Let be positive real numbers. Prove
.
Problem 4: (2017 usamo/6)
Find the minimum possible value of
given that
are nonnegative real numbers such that
.
Problem 5: (Japanese MO 1997/6)
Prove that
for any positive real numbers ,
,
.
I.Problems
Problem 6 (2011 usamo/1):
Let ,
,
be positive real numbers such that
. Prove that
Problem 7 (1974 usamo/2):
Prove that if ,
, and
are positive real numbers, then
Problem 8 (1995 imo/2):
Let be positive real numbers such that
. Prove that
Problem 9 (2000 imo/2):
Let be positive real numbers so that
. Prove that
.
Problem 10 (2003 usamo/5):
Let ,
,
be positive real numbers. Prove that
Problem 11 (2001 usamo/3):
Let and satisfy
Show that
Problem 12 (2012 usajmo/3):
Let ,
,
be positive real numbers. Prove that
Problem 13 (2005 imo/3):
Let be three positive reals such that
. Prove that
Problem 14 (2003 imo shortlist/A6. cough.):
Let be a positive integer and let
,
be two sequences of positive real numbers. Suppose
is a sequence of positive real numbers such that
for all
.
Let . Prove that
I.Extra
Ravi Substitution for triangles..
Problem 15: (1983 imo/6, using Ravi!)
Let ,
and
be the lengths of the sides of a triangle. Prove that
.
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 functionwhere its domain and range are same is an involution if
for every
in its range/domain. This function is bijective.
-Function=anything.
-Symmetry
-Plug in
-Check for linear/constant solutions first. They are usually the only ones.
-fff trick is pro
-Pointwise trap?!?
-Be aware of your domain/range. ((Probably not))
F.Ok these things are sort of cool
Example 1 (2002 usamo/4):
Let be the set of real numbers. Determine all functions
such that
for all pairs of real numbers and
.
Solution:
I claim that the sole solution is for some constant
.
First note that setting and
as zero respectively yields
and
. Letting
in the second equation means that
is odd.
Now, we can substitute into the original equation our findings:
where
.
Finally,
. Setting
, we get the desired.
F.They're not that cool actually
Problem 1 (2009 imo/5):
Determine all functions from the set of positive integers to the set of positive integers such that, for all positive integers
and
, there exists a non-degenerate triangle with sides of lengths
and
.
This question...is...cool...?
Example 2 (ISL/2015): Determine all functions
with the property that
holds for all .
BOGUS Solution:
The answer is or
. These clearly work.
Claim: there exists a such that
.
Proof: set .
Then (*) where
. Now
for some constant
, or
.
The former yields , the latter works and yields
.
Why this is wrong: You can't just assume because or
. Remember, a function is anything. Maybe this function is surjective.
Solution (after that step):
Now we plug in (because we know that the
will turn into
, and therefore will be proving that
is linear).
(from (*) on where
is actually
.
(follows directly from (*)).
Therefore, this equation is linear.
Now, letting ,
From (*), we get
If , then
So . Otherwise,
is constant and plugging back into (*), we get the only solution as
Ay, ok. Heres a semi-recent one.
Problem 2 (2016 usamo/4):
Find all functions such that for all real numbers
and
,
Problem 3(One of my favorites, found it in Inter. Alg I think; 1981 imo/6)
The function satisfies
(1)
(2)
(3)
for all non-negative integers . Determine
.
Problem 4(cute, 1983 imo/1):
Find all functions defined on the set of positive reals which take positive real values and satisfy the conditions:
(i) for all
;
(ii) as
.
Problem 5 (1986 imo/5, easy but lots of pitfalls oops):
Find all (if any) functions taking the non-negative reals onto the non-negative reals, such that
(a) for all non-negative
,
;
(b) ;
(c) for every
.
F.Problems
Problem 6 (1993 usamo/3):
Consider functions which satisfy
(i) for all
in
,
(ii)
,
(iii)
whenever
,
, and
are all in
.
Find, with proof, the smallest constant
such that
for every function
satisfying (i)-(iii) and every
in
.
Problem 7 (2015 usajmo/4):
Find all functions such that
for all rational numbers
that form an arithmetic progression. (
is the set of all rational numbers.)
Problem 8 (2015 imo/5):
Let be the set of real numbers. Determine all functions
:
satisfying the equation
for all real numbers and
.
Problem 9 (POINTWISE TRAP!!! 2014 usamo/2):
Let be the set of integers. Find all functions
such that
for all
with
.
Problem 10 (woah casework, 2012 usamo/4):
Find all functions (where
is the set of positive integers) such that
for all positive integers
and such that
divides
for all distinct positive integers
,
.
Problem 11 (2012 imo/4, misplaced i think):
Find all functions such that, for all integers
and
that satisfy
, the following equality holds:
Problem 12 (2011 imo/3):
Let be a real-valued function defined on the set of real numbers that satisfies
for all real numbers
and
. Prove that
for all
.
Problem 13 (This was the first oly FE question I solved. That's why it's last :P 2010 imo/1):
Find all function such that for all
the following equality holds
where is greatest integer not greater than
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
.
.
.
.
.
.
.
.
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?
C.Before oly
B. Problem 1
How many ways can people stand in a line?
B. Problem 2
How many ways can people stand in a circle?
B. Problem 3
How many ways can you choose indistinguishable cupcakes from
of them?
B. Problem 4
How many ways can you choose distinguishable cupcakes from
of them?
B. Problem 5 (2015 I/5):
In a drawer Sandy has pairs of socks, each pair a different color. On Monday Sandy selects two individual socks at random from the
socks in the drawer. On Tuesday Sandy selects
of the remaining
socks at random and on Wednesday two of the remaining
socks at random. The probability that Wednesday is the first day Sandy selects matching socks is
, where
and
are relatively prime positive integers, Find
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?
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?
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 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
be the maximum possible number of points in a growing path, and let
be the number of growing paths consisting of exactly
points. Find
.
B. Problem 11 (2020 I/9):
Let be the set of positive integer divisors of
Three numbers are chosen independently and at random with replacement from the set
and labeled
and
in the order they are chosen. The probability that both
divides
and
divides
is
where
and
are relatively prime positive integers. Find
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 , where
and
are relatively prime positive integers. Find
.
B. Problem 13 (2020 I/7):
A club consisting of men and
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
member or as many as
members. Let
be the number of such committees that can be formed. Find the sum of the prime numbers that divide
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 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
is divided by
.
B. Problem 16 (All combo is easy, sorry. 2011 II/14):
There are permutations
of
such that for
,
divides
for all integers
with
. Find the remainder when
is divided by
.
B. Problem 17 (2017 I/7, the only combo question I've ever liked on the AIME):
For nonnegative integers and
with
, let
. Let
denote the sum of all
, where
and
are nonnegative integers with
. Find the remainder when
is divided by
.
B. CHALLENGE PROBLEM 18 (2021 usajmo/6):
Find
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 . Denote several events
and their probabilities as
. Then
.
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 . Then there exists a person that has ate at least
cookies, and also a person who ate at most
cookies. It seems simple, but it's pretty powerful.
Pigeonhole principle says that if you havepigeonholes and
pigeons, there must exist a pigeonhole with at least ceiling(
) 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 where
and
are relatively prime positive integers, find
Solution:
The four aces divide the deck into parts, and the expected number of cards in each of them is
. Therefore the answer is
Example 2 (1987 imo/1):
Let be the number of permutations of the set
which have exactly
fixed points. Prove that
.
Solution:
Look at the summation. It's actually just the expected number of fixed points, multiplied by the number of permutations, or .
Because every integer has a chance of being a fixed point, the expected number of fixed points is
, and multiplying by
, we see that the requested sum is indeed
.
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 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 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 congruent arcs by
points. The points are colored in four colors such that some
points are colored Red, some
points are colored Green, some
points are colored Blue, and the remaining
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 and consider all subsets of
elements of the set
. Each of these subsets has a smallest member. Let
denote the arithmetic mean of these smallest numbers; prove that
Problem 5 (Well, it's trivial. Prove it! 2003 imo/1):
is the set
. Show that for any subset
of
with
elements we can find
distinct elements
of
, such that the sets
are all pairwise disjoint.
Problem 6 (1998 imo/2):
In a competition, there are contestants and
judges, where
is an odd integer. Each judge rates each contestant as either “pass” or “fail”. Suppose
is a number such that, for any two judges, their ratings coincide for at most
contestants. Prove that
C.oof
Problem 6 (Construction! 2014 imo/5):
For each positive integer , the Bank of Cape Town issues coins of denomination
. Given a finite collection of such coins (of not necessarily different denominations) with total value at most
, prove that it is possible to split this collection into
or fewer groups, such that each group has total value at most
.
Problem 7 (More construction! 2016 imo/2):
Find all integers for which each cell of
table can be filled with one of the letters
and
in such a way that:
in each row and each column, one third of the entries are , one third are
and one third are
; and
in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are , one third are
and one third are
.