MathGoldMedalist
Sign InRegister

Olympiad Toolkit

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

Showing 151–166 of 166 toolkits
  1. 151.
    Counting Principles

    Addition Principle

    For mutually exclusive cases, add the numbers of possibilities.

    n1+n2+⋯+nkn_1+n_2+\cdots+n_k

    Multiplication Principle

    For successive choices, multiply the numbers of possibilities.

    n1n2⋯nkn_1n_2\cdots n_k
    Counting choices using the Multiplication Principle

    Complement Principle

    Desired=Total−Undesired\text{Desired}=\text{Total}-\text{Undesired}
  2. 152.
    Permutations

    A permutation is an arrangement of objects in which order matters.

    Arranging All Objects

    n!n!

    Arranging Some of the Objects

    P(n,r)=n!(n−r)!P(n,r)=\frac{n!}{(n-r)!}

    Identical Objects

    n!n1!n2!⋯nk!\frac{n!}{n_1!n_2!\cdots n_k!}
  3. 153.
    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
  4. 154.
    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)
  5. 155.
    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.
  6. 156.
    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}}
  7. 157.
    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}}
  8. 158.
    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}
  9. 159.
    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}}
  10. 160.
    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
  11. 161.
    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)
  12. 162.
    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
  13. 163.
    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
  14. 164.
    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}
  15. 165.
    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}}
  16. 166.
    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