MathGoldMedalist
Sign InRegister

Olympiad Toolkit

A growing collection of essential formulas, identities, and techniques for mathematical olympiad problem solving.

Showing 151–164 of 164 toolkits
  1. 151.
    Combinations

    A combination is a selection of objects in which order does not matter.

    (nr)=n!r!(n−r)!\binom{n}{r}=\frac{n!}{r!(n-r)!}

    The notation (nr)\binom{n}{r} is read as “n choose r”.

    Symmetry Identity

    (nr)=(nn−r)\binom{n}{r}=\binom{n}{n-r}

    Choosing the objects to include is equivalent to choosing the objects to exclude.

    Pascal's Identity

    (nr)=(n−1r)+(n−1r−1)\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}

    Faster Calculation

    (107)=(103)=10⋅9⋅83⋅2⋅1=120\binom{10}{7}=\binom{10}{3}=\frac{10\cdot9\cdot8}{3\cdot2\cdot1}=120
  2. 152.
    Probability

    Probability measures how likely an event is to occur.

    0≤P(A)≤10\le P(A)\le1

    Sample Space and Events

    The sample space SS is the set of all possible outcomes, and an event AA is a collection of outcomes from the sample space.

    Equally Likely Outcomes

    P(A)=∣A∣∣S∣P(A)=\frac{|A|}{|S|}

    Complement

    P(Ac)=1−P(A)P(A^c)=1-P(A)

    Probability of A or B

    P(A∪B)=P(A)+P(B)−P(A∩B)P(A\cup B)=P(A)+P(B)-P(A\cap B)

    Independent Events

    P(A∩B)=P(A)P(B)P(A\cap B)=P(A)P(B)
  3. 153.
    Square-Root Long-Division Algorithm

    A step-by-step algorithm for finding square roots by grouping digits into pairs, subtracting squares, and determining each successive digit.

    Square-root long-division algorithm illustrated with 4047 and 954.
  4. 154.
    Optimization by Equalization

    For two nonnegative numbers with a fixed sum, their product increases and the sum of their squares decreases as the numbers become closer together.

    Moving two numbers closer together while keeping their sum fixed.
    a+b=S⟹ab≤S24\boxed{a+b=S\Longrightarrow ab\le\frac{S^2}{4}}
  5. 155.
    Sperner's Theorem

    The maximum size of an antichain of subsets of an n-element set is

    (n⌊n/2⌋)\boxed{\binom{n}{\lfloor n/2\rfloor}}
  6. 156.
    Radical Expressions

    If x and y are nonnegative integers, d is squarefree, and

    x+y=kd,\sqrt{x}+\sqrt{y}=k\sqrt{d},

    then for some nonnegative integers a and b,

    x=da2,y=db2,a+b=k\boxed{x=da^2,\quad y=db^2,\quad a+b=k}
  7. 157.
    Invariants

    An invariant is a quantity or property that remains unchanged throughout a process.

    I(S0)=I(S1)=I(S2)=⋯I(S_0)=I(S_1)=I(S_2)=\cdots

    If the initial and target configurations have different invariant values, the target is impossible to reach.

    I(initial)≠I(target)⟹impossible\boxed{I(\text{initial})\ne I(\text{target})\Longrightarrow\text{impossible}}
  8. 158.
    Rational and Irrational Numbers

    A rational number can be written as

    ab,a,b∈Z,b≠0.\frac ab,\qquad a,b\in\mathbb Z,\quad b\ne0.

    A real number that cannot be written in this form is irrational.

    37, 0, 0.125⏟Rational2, π⏟Irrational\underbrace{\frac37,\ 0,\ 0.125}_{\text{Rational}}\qquad\underbrace{\sqrt2,\ \pi}_{\text{Irrational}}
    xxyyx+yx+yxyxy
    RationalRationalRationalRational
    RationalIrrationalIrrationalMay be either
    IrrationalIrrationalMay be eitherMay be either
  9. 159.
    Mathematical Induction

    Mathematical induction proves statements for every integer in a specified range using a base case and an inductive step.

    Base Case

    P(n0)P(n_0)

    Inductive Step

    P(k)⟹P(k+1)P(k)\Longrightarrow P(k+1)

    Extensions include strong induction, step-size induction, binary induction, and Cauchy induction.

    Four quadrants with the original missing cell and a central L-shaped tromino (16.3.png)
  10. 160.
    Fibonacci Numbers

    The Fibonacci sequence starts with 0 and 1, and each subsequent term is the sum of the previous two.

    F0=0,F1=1,Fn+2=Fn+1+FnF_0=0,\quad F_1=1,\quad F_{n+2}=F_{n+1}+F_n
    0, 1, 1, 2, 3, 5, 8, 13, 21,…0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ldots
    nn0011223344556677
    FnF_n001111223355881313
  11. 161.
    Nonnegative Squares

    Every real square is nonnegative. This helps prove inequalities and find minimum values.

    x2≥0(x∈R)x^2\ge0\qquad(x\in\mathbb{R})
    a2+b2−2ab=(a−b)2≥0a^2+b^2-2ab=(a-b)^2\ge0
    x2−6x+13=(x−3)2+4≥4x^2-6x+13=(x-3)^2+4\ge4
  12. 162.
    Stewart's Theorem
    Stewart's Theorem in triangle ABC, where AD = d, BD = m, DC = n, AB = c, and AC = b.
    a(d2+mn)=mb2+nc2\boxed{a(d^2+mn)=mb^2+nc^2}
  13. 163.
    Incenter of a Triangle

    The incenter is the intersection of the three internal angle bisectors of a triangle.

    Triangle ABC with incenter I and its incircle of radius r.
    r=[ABC]s\boxed{r=\frac{[ABC]}{s}}
  14. 164.
    Approximations and Bounds
    π=3.14159…\pi=3.14159\ldots
    2=1.41421…\sqrt{2}=1.41421\ldots
    3=1.73205…\sqrt{3}=1.73205\ldots
    e=2.71828…e=2.71828\ldots