MathGoldMedalist
Sign InRegister

Olympiad Toolkit

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

  1. 1.
    Sum of the first n integers
    1+2+⋯+n=n(n+1)21+2+\cdots+n=\frac{n(n+1)}{2}
  2. 2.
    Sum of squares
    12+22+⋯+n2=n(n+1)(2n+1)61^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}
  3. 3.
    Sum of cubes
    13+23+⋯+n3=(n(n+1)2)21^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2
  4. 4.
    Geometric series
    1+r+r2+⋯+rn=rn+1−1r−11+r+r^2+\cdots+r^n=\frac{r^{n+1}-1}{r-1}
    ∣r∣<1:1+r+r2+⋯=11−r|r|<1:\quad 1+r+r^2+\cdots=\frac{1}{1-r}
  5. 5.
    Telescoping series
    11⋅2+12⋅3+⋯+1n(n+1)=(1−12)+⋯+(1n−1n+1)=1−1n+1\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{1}{n(n+1)}=\left(1-\frac{1}{2}\right)+\cdots+\left(\frac{1}{n}-\frac{1}{n+1}\right)=1-\frac{1}{n+1}
  6. 6.
    Square of a sum
    (a+b)2=a2+2ab+b2(a+b)^2=a^2+2ab+b^2
  7. 7.
    Square of a difference
    (a−b)2=a2−2ab+b2(a-b)^2=a^2-2ab+b^2
  8. 8.
    Cube of a sum
    (a+b)3=a3+3a2b+3ab2+b3(a+b)^3=a^3+3a^2b+3ab^2+b^3
  9. 9.
    Cube of a difference
    (a−b)3=a3−3a2b+3ab2−b3(a-b)^3=a^3-3a^2b+3ab^2-b^3
  10. 10.
    Difference of squares
    a2−b2=(a−b)(a+b)a^2-b^2=(a-b)(a+b)
  11. 11.
    Difference of cubes
    a3−b3=(a−b)(a2+ab+b2)a^3-b^3=(a-b)(a^2+ab+b^2)
  12. 12.
    Sum of cubes (factored)
    a3+b3=(a+b)(a2−ab+b2)a^3+b^3=(a+b)(a^2-ab+b^2)
  13. 13.
    General difference of powers
    an−bn=(a−b)(an−1+an−2b+⋯+bn−1)a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots+b^{n-1}\right)
  14. 14.
    Sum of odd power
    n odd:an+bn=(a+b)(an−1−an−2b+⋯+bn−1)n\text{ odd}:\quad a^n+b^n=(a+b)\left(a^{n-1}-a^{n-2}b+\cdots+b^{n-1}\right)
  15. 15.
    Difference of even power
    n even:an−bn=(a+b)(an−1−an−2b+⋯−bn−1)n\text{ even}:\quad a^n-b^n=(a+b)\left(a^{n-1}-a^{n-2}b+\cdots-b^{n-1}\right)
  16. 16.
    Hockey Stick Identity
    (kk)+(k+1k)+(k+2k)+⋯+(nk)=(n+1k+1)\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\cdots+\binom{n}{k}=\binom{n+1}{k+1}
  17. 17.
    Vandermonde's Identity
    (m0)(nk)+(m1)(nk−1)+(m2)(nk−2)+⋯+(mk)(n0)=(m+nk)\binom{m}{0}\binom{n}{k}+\binom{m}{1}\binom{n}{k-1}+\binom{m}{2}\binom{n}{k-2}+\cdots+\binom{m}{k}\binom{n}{0}=\binom{m+n}{k}
  18. 18.
    Symmetric cubic sum
    a3+b3+c3=(a+b+c)(a2+b2+c2−ab−ac−bc)+3abca^3+b^3+c^3=(a+b+c)(a^2+b^2+c^2-ab-ac-bc)+3abc
  19. 19.
    Factoring quadratic by grouping
    x2+(a+b)x+ab=(x+a)(x+b)x^2+(a+b)x+ab=(x+a)(x+b)
  20. 20.
    Binomial Theorem
    (a+b)n=(n0)an+(n1)an−1b+(n2)an−2b2+⋯+(nn)bn(a+b)^n=\binom{n}{0}a^n+\binom{n}{1}a^{n-1}b+\binom{n}{2}a^{n-2}b^2+\cdots+\binom{n}{n}b^n
  21. 21.
    Quadratic Formula
    ax2+bx+c=0  ⇒  x=−b±b2−4ac2aax^2+bx+c=0\;\Rightarrow\;x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}
  22. 22.
    Approaches to Similar Equations
    Addition and Subtraction.\text{Addition and Subtraction.}
  23. 23.
    SFFT (Simon's Favorite Factoring Trick)
    xy+ax+by=c  ⇒  (x+b)(y+a)=c+abxy+ax+by=c\;\Rightarrow\;(x+b)(y+a)=c+ab
    GSFFT (General Form)\text{GSFFT (General Form)}
    axy+bx+cy=daxy+bx+cy=d
    a2xy+abx+acy=ada^2xy+abx+acy=ad
    (ax+c)(ay+b)=ad+bc(ax+c)(ay+b)=ad+bc
  24. 24.
    Square of a sum (n terms)
    (x1+x2+⋯+xn)2=x12+⋯+xn2+2x1x2+⋯+2xn−1xn(x_1+x_2+\cdots+x_n)^2=x_1^2+\cdots+x_n^2+2x_1x_2+\cdots+2x_{n-1}x_n
  25. 25.
    Arithmetic Sequence and Series
    an=a1+(n−1)da_n=a_1+(n-1)d
    Sn=a1+a2+⋯+an=n2(a1+an)S_n=a_1+a_2+\cdots+a_n=\frac{n}{2}(a_1+a_n)
  26. 26.
    Expansion (or factorization) of three binomials
    abc−ab−ac−bc+a+b+c−1=(a−1)(b−1)(c−1)abc-ab-ac-bc+a+b+c-1=(a-1)(b-1)(c-1)
  27. 27.
    Expansion (or factorization) of two binomials
    a2+ab+ac+bc=(a+b)(a+c)a^2+ab+ac+bc=(a+b)(a+c)
  28. 28.
    Max-QM-AM-GM-HM-Min Inequality
    x1,…,xn∈R+x_1,\dots,x_n\in\mathbb{R}^+
    max⁡{xi}≥x12+x22+⋯+xn2n≥x1+x2+⋯+xnn≥x1x2⋯xnn≥n1x1+1x2+⋯+1xn≥min⁡{xi}\max\{x_i\}\ge\sqrt{\frac{x_1^2+x_2^2+\cdots+x_n^2}{n}}\ge\frac{x_1+x_2+\cdots+x_n}{n}\ge\sqrt[n]{x_1x_2\cdots x_n}\ge\frac{n}{\frac{1}{x_1}+\frac{1}{x_2}+\cdots+\frac{1}{x_n}}\ge\min\{x_i\}
    Equality holds if and only if all xi are equal.\text{Equality holds if and only if all }x_i\text{ are equal.}
  29. 29.
    Integer and Fractional Parts
    [x]: Integer part{x}: Fractional part[x]:\text{ Integer part}\qquad\{x\}:\text{ Fractional part}
    We can write x as:\text{We can write }x\text{ as:}
    x=k+r,k∈Z,  r∈R,  0≤r<1x=k+r,\qquad k\in\mathbb{Z},\;r\in\mathbb{R},\;0\le r<1
  30. 30.
    Vieta's Formula
    ax2+bx+c=0ax^2+bx+c=0
    r1+r2=−ba,r1r2=car_1+r_2=-\frac{b}{a},\qquad r_1r_2=\frac{c}{a}
    ax3+bx2+cx+d=0ax^3+bx^2+cx+d=0
    r1+r2+r3=−bar_1+r_2+r_3=-\frac{b}{a}
    r1r2+r1r3+r2r3=car_1r_2+r_1r_3+r_2r_3=\frac{c}{a}
    r1r2r3=−dar_1r_2r_3=-\frac{d}{a}
    anxn+an−1xn−1+⋯+a0=0a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0=0
    r1+⋯+rn=−an−1anr_1+\cdots+r_n=-\frac{a_{n-1}}{a_n}
    ∑i<jrirj=an−2an\sum_{i<j}r_ir_j=\frac{a_{n-2}}{a_n}
    ⋯\cdots
    r1r2⋯rn=(−1)na0anr_1r_2\cdots r_n=(-1)^n\frac{a_0}{a_n}
  31. 31.
    Signs and Roots of Quadratics
    f(x)=ax2+bx+c,Δ=b2−4acf(x)=ax^2+bx+c,\qquad \Delta=b^2-4ac
    ConditionNumber of Real RootsSign of f(x)f(x)
    Δ>0\Delta>02
    sign(a)0−sign(a)0sign(a)r₁r₂
    Δ=0\Delta=01
    sign(a)0sign(a)r
    Δ<0\Delta<00
    sign(a)
  32. 32.
    Remainder of Polynomial Division
    A(x)÷B(x):  A(x)=B(x)Q(x)+R(x),deg⁡(R(x))<deg⁡(B(x))A(x)\div B(x):\;A(x)=B(x)Q(x)+R(x),\quad \deg(R(x))<\deg(B(x))
    ⇒ If B(x)=0, then A(x)=R(x)\Rightarrow\text{ If }B(x)=0,\text{ then }A(x)=R(x)
  33. 33.
    Number of Positive Divisors
    n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
    Number of positive divisors of n:  (α1+1)(α2+1)⋯(αk+1)\text{Number of positive divisors of }n:\;(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)
  34. 34.
    Sum of Positive Divisors
    n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
    (1+p1+p12+⋯+p1α1)(1+p2+p22+⋯+p2α2)⋯(1+pk+pk2+⋯+pkαk)(1+p_1+p_1^2+\cdots+p_1^{\alpha_1})(1+p_2+p_2^2+\cdots+p_2^{\alpha_2})\cdots(1+p_k+p_k^2+\cdots+p_k^{\alpha_k})
    =p1α1+1−1p1−1×p2α2+1−1p2−1×⋯×pkαk+1−1pk−1=\frac{p_1^{\alpha_1+1}-1}{p_1-1}\times\frac{p_2^{\alpha_2+1}-1}{p_2-1}\times\cdots\times\frac{p_k^{\alpha_k+1}-1}{p_k-1}
  35. 35.
    Product of Positive Divisors
    n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}
    t=(α1+1)(α2+1)⋯(αk+1)t=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)
    Product of positive divisors of n:  nt/2\text{Product of positive divisors of }n:\;n^{t/2}
  36. 36.
    General Solutions of Trigonometric Equations
    sin⁡α=sin⁡β  ⇒  α=β+360k,  180−β+360k,  k∈Z\sin\alpha=\sin\beta\;\Rightarrow\;\alpha=\beta+360k,\;180-\beta+360k,\;k\in\mathbb{Z}
    cos⁡α=cos⁡β  ⇒  α=±β+360k,  k∈Z\cos\alpha=\cos\beta\;\Rightarrow\;\alpha=\pm\beta+360k,\;k\in\mathbb{Z}
    tan⁡α=tan⁡β  ⇒  α=β+180k,  k∈Z\tan\alpha=\tan\beta\;\Rightarrow\;\alpha=\beta+180k,\;k\in\mathbb{Z}
    cot⁡α=cot⁡β  ⇒  α=β+180k,  k∈Z\cot\alpha=\cot\beta\;\Rightarrow\;\alpha=\beta+180k,\;k\in\mathbb{Z}
  37. 37.
    Trigonometric Transformations
    sin⁡(90∘−α)=cos⁡αsin⁡(90∘+α)=cos⁡α\sin(90^\circ-\alpha)=\cos\alpha\qquad \sin(90^\circ+\alpha)=\cos\alpha
    cos⁡(90∘−α)=sin⁡αcos⁡(90∘+α)=−sin⁡α\cos(90^\circ-\alpha)=\sin\alpha\qquad \cos(90^\circ+\alpha)=-\sin\alpha
    tan⁡(90∘−α)=cot⁡αtan⁡(90∘+α)=−cot⁡α\tan(90^\circ-\alpha)=\cot\alpha\qquad \tan(90^\circ+\alpha)=-\cot\alpha
    cot⁡(90∘−α)=tan⁡αcot⁡(90∘+α)=−tan⁡α\cot(90^\circ-\alpha)=\tan\alpha\qquad \cot(90^\circ+\alpha)=-\tan\alpha
    sin⁡(180∘−α)=sin⁡αsin⁡(180∘+α)=−sin⁡α\sin(180^\circ-\alpha)=\sin\alpha\qquad \sin(180^\circ+\alpha)=-\sin\alpha
    cos⁡(180∘−α)=−cos⁡αcos⁡(180∘+α)=−cos⁡α\cos(180^\circ-\alpha)=-\cos\alpha\qquad \cos(180^\circ+\alpha)=-\cos\alpha
    tan⁡(180∘−α)=−tan⁡αtan⁡(180∘+α)=tan⁡α\tan(180^\circ-\alpha)=-\tan\alpha\qquad \tan(180^\circ+\alpha)=\tan\alpha
    cot⁡(180∘−α)=−cot⁡αcot⁡(180∘+α)=cot⁡α\cot(180^\circ-\alpha)=-\cot\alpha\qquad \cot(180^\circ+\alpha)=\cot\alpha
    sin⁡(−α)=−sin⁡α\sin(-\alpha)=-\sin\alpha
    cos⁡(−α)=cos⁡α\cos(-\alpha)=\cos\alpha
    tan⁡(−α)=−tan⁡α\tan(-\alpha)=-\tan\alpha
    cot⁡(−α)=−cot⁡α\cot(-\alpha)=-\cot\alpha
  38. 38.
    Trigonometric Identities
    sin⁡2α+cos⁡2α=1\sin^2\alpha+\cos^2\alpha=1
    sin⁡(α+β)=sin⁡αcos⁡β+cos⁡αsin⁡β\sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\sin\beta
    cos⁡(α+β)=cos⁡αcos⁡β−sin⁡αsin⁡β\cos(\alpha+\beta)=\cos\alpha\cos\beta-\sin\alpha\sin\beta
    sin⁡2α=2sin⁡αcos⁡α\sin 2\alpha=2\sin\alpha\cos\alpha
    cos⁡2α=cos⁡2α−sin⁡2α=2cos⁡2α−1=1−2sin⁡2α\cos 2\alpha=\cos^2\alpha-\sin^2\alpha=2\cos^2\alpha-1=1-2\sin^2\alpha
    cos⁡3α=4cos⁡3α−3cos⁡α\cos 3\alpha=4\cos^3\alpha-3\cos\alpha
    tan⁡(α+β)=tan⁡α+tan⁡β1−tan⁡αtan⁡β\tan(\alpha+\beta)=\frac{\tan\alpha+\tan\beta}{1-\tan\alpha\tan\beta}
    cot⁡(α+β)=cot⁡αcot⁡β−1cot⁡α+cot⁡β\cot(\alpha+\beta)=\frac{\cot\alpha\cot\beta-1}{\cot\alpha+\cot\beta}
    sin⁡x+cos⁡x=2sin⁡(x+45∘)\sin x+\cos x=\sqrt{2}\sin(x+45^\circ)
    sin⁡x−cos⁡x=2sin⁡(x−45∘)\sin x-\cos x=\sqrt{2}\sin(x-45^\circ)
  39. 39.
    Trigonometric Sum-to-Product Identities
    sin⁡α+sin⁡β=2sin⁡(α+β2)cos⁡(α−β2)\sin\alpha+\sin\beta=2\sin\left(\frac{\alpha+\beta}{2}\right)\cos\left(\frac{\alpha-\beta}{2}\right)
    sin⁡α−sin⁡β=2cos⁡(α+β2)sin⁡(α−β2)\sin\alpha-\sin\beta=2\cos\left(\frac{\alpha+\beta}{2}\right)\sin\left(\frac{\alpha-\beta}{2}\right)
    cos⁡α+cos⁡β=2cos⁡(α+β2)cos⁡(α−β2)\cos\alpha+\cos\beta=2\cos\left(\frac{\alpha+\beta}{2}\right)\cos\left(\frac{\alpha-\beta}{2}\right)
    cos⁡α−cos⁡β=−2sin⁡(α+β2)sin⁡(α−β2)\cos\alpha-\cos\beta=-2\sin\left(\frac{\alpha+\beta}{2}\right)\sin\left(\frac{\alpha-\beta}{2}\right)
  40. 40.
    Trigonometric Product-to-Sum Identities
    sin⁡pcos⁡q=12(sin⁡(p+q)+sin⁡(p−q))\sin p\cos q=\frac{1}{2}(\sin(p+q)+\sin(p-q))
    cos⁡pcos⁡q=12(cos⁡(p+q)+cos⁡(p−q))\cos p\cos q=\frac{1}{2}(\cos(p+q)+\cos(p-q))
    sin⁡psin⁡q=12(cos⁡(p−q)−cos⁡(p+q))\sin p\sin q=\frac{1}{2}(\cos(p-q)-\cos(p+q))
  41. 41.
    Dual Pythagorean Theorem
    Dual Pythagorean Theorem figure
    CB2−CA2=EB2−EA2=FB2−FA2=DB2−DA2CB^2-CA^2=EB^2-EA^2=FB^2-FA^2=DB^2-DA^2
  42. 42.
    Angle Bisector Theorem
    Angle Bisector Theorem figure
    BDDC=cb\frac{BD}{DC}=\frac{c}{b}
  43. 43.
    Partial Fraction Decomposition
    5x+1(x−1)(x+2)=2x−1+3x+2\frac{5x+1}{(x-1)(x+2)} = \frac{2}{x-1} + \frac{3}{x+2}

    Partial Fraction Decomposition is a technique for rewriting a rational expression as a sum of simpler fractions.

    Two Ways to Calculate the Numerators

    Start with

    5x+1(x−1)(x+2)=Ax−1+Bx+2\frac{5x+1}{(x-1)(x+2)} = \frac{A}{x-1} + \frac{B}{x+2}

    Approach 1 — Comparing Coefficients

    Multiply both sides by (x−1)(x+2)(x-1)(x+2):

    5x+1=A(x+2)+B(x−1)5x+1 = A(x+2)+B(x-1)

    Expand:

    5x+1=(A+B)x+(2A−B)5x+1 = (A+B)x+(2A-B)

    Compare coefficients:

    A+B=5A+B=5
    2A−B=12A-B=1

    Therefore,

    A=2,B=3.A=2,\qquad B=3.

    Approach 2 — Heaviside Cover-Up Method

    Let

    f(x)=5x+1(x−1)(x+2)=Ax−1+Bx+2.f(x) = \frac{5x+1}{(x-1)(x+2)} = \frac{A}{x-1} + \frac{B}{x+2}.

    Multiply both sides by (x−1)(x-1):

    (x−1)f(x)=5x+1x+2=A+B(x−1)x+2.(x-1)f(x) = \frac{5x+1}{x+2} = A+\frac{B(x-1)}{x+2}.

    Substitute x=1x=1:

    A=5(1)+11+2=63=2.A = \frac{5(1)+1}{1+2} = \frac{6}{3} = 2.

    Similarly, multiply both sides by (x+2)(x+2):

    (x+2)f(x)=5x+1x−1=A(x+2)x−1+B.(x+2)f(x) = \frac{5x+1}{x-1} = \frac{A(x+2)}{x-1}+B.

    Substitute x=−2x=-2:

    B=5(−2)+1−2−1=−9−3=3.B = \frac{5(-2)+1}{-2-1} = \frac{-9}{-3} = 3.
  44. 44.
    Creating n Equations in n Variables for Probability Problems
  45. 45.
    Adjacency in Permutations

    If some objects in a permutation problem must be adjacent, place a box around those objects and treat them as a single object.

    For example, the number of permutations of the letters in "logarithm" in which the letters l, o, and g are adjacent is

    log arithm7!×3!\boxed{\text{log}}\ \text{arithm}\qquad 7! \times 3!

    There are 7 objects after treating the boxed letters as a single object. The letters l, o, and g inside the box can be arranged in 3! ways.

  46. 46.
    Divisibility: Definition and Properties

    Definition

    a∣ba\mid b ("a divides b") if and only if there exists an integer kk such that

    b=ak,k∈Z.b=ak,\qquad k\in\mathbb Z.

    Like even numbers, which have the form 2k2k.

    Properties

    1.a∣a1.\quad a\mid a
    2.a∣02.\quad a\mid 0
    3.±1∣a3.\quad \pm1\mid a
    4.a∣b⟹−a∣b,  a∣−b,  −a∣−b4.\quad a\mid b \Longrightarrow -a\mid b,\; a\mid-b,\; -a\mid-b
    5.a∣b,  b≠0⟹∣a∣≤∣b∣5.\quad a\mid b,\; b\ne0 \Longrightarrow |a|\le|b|
    6.a∣b⟹ac∣bc6.\quad a\mid b \Longrightarrow ac\mid bc
    7.a∣b⟹a∣bc7.\quad a\mid b \Longrightarrow a\mid bc
    8.a∣1⟹a=±18.\quad a\mid 1 \Longrightarrow a=\pm1
    9.a∣b,  b∣c⟹a∣c9.\quad a\mid b,\; b\mid c \Longrightarrow a\mid c
    10.a∣b,  a∣c⟹a∣b±c,  a∣bc10.\quad a\mid b,\; a\mid c \Longrightarrow a\mid b\pm c,\; a\mid bc
    11.a∣b,  c∣d⟹ac∣bd11.\quad a\mid b,\; c\mid d \Longrightarrow ac\mid bd
    12.a∣b⟹an∣bn,n∈Z+12.\quad a\mid b \Longrightarrow a^n\mid b^n,\qquad n\in\mathbb Z^+
    13.a∣b,  a∣c⟹a∣mb+nc13.\quad a\mid b,\; a\mid c \Longrightarrow a\mid mb+nc
    14.ac∣bc,  c≠0⟹a∣b14.\quad ac\mid bc,\; c\ne0 \Longrightarrow a\mid b
    15.a∣b,  b∣a⟹∣a∣=∣b∣15.\quad a\mid b,\; b\mid a \Longrightarrow |a|=|b|
    16.a∣b,  a∣c  ⟺  a∣gcd⁡(b,c)16.\quad a\mid b,\; a\mid c \iff a\mid\gcd(b,c)
    17.a∣b,  c∣b  ⟺  lcm⁡(a,c)∣b17.\quad a\mid b,\; c\mid b \iff \operatorname{lcm}(a,c)\mid b
    18.Euclid’s Lemma:a∣bc,gcd⁡(a,b)=1⟹a∣c18.\quad \text{Euclid's Lemma:}\qquad a\mid bc,\qquad \gcd(a,b)=1 \Longrightarrow a\mid c
    19.p∣ab⟹p∣a or p∣b,p prime.19.\quad p\mid ab \Longrightarrow p\mid a \text{ or } p\mid b,\qquad p\text{ prime.}
  47. 47.
    Modular Arithmetic: Definition and Properties

    Definition

    aa is congruent to bb modulo mm if and only if their difference is divisible by mm:

    a≡b(modm)⟺m∣(a−b).a \equiv b \pmod m \quad\Longleftrightarrow\quad m\mid(a-b).

    Properties

    1.a≡a(modm)1.\quad a\equiv a\pmod m
    2.a≡b(modm)⟹b≡a(modm)2.\quad a\equiv b\pmod m \Longrightarrow b\equiv a\pmod m
    3.a≡b(modm),b≡c(modm)⟹a≡c(modm)3.\quad a\equiv b\pmod m,\qquad b\equiv c\pmod m \Longrightarrow a\equiv c\pmod m
    4.a≡b(modm)⟹{a+c≡b+c(modm),a−c≡b−c(modm),ac≡bc(modm).4.\quad a\equiv b\pmod m \Longrightarrow \begin{cases} a+c\equiv b+c\pmod m,\\ a-c\equiv b-c\pmod m,\\ ac\equiv bc\pmod m. \end{cases}
    5.a≡b(modm),c≡d(modm)⟹{a+c≡b+d(modm),a−c≡b−d(modm),ac≡bd(modm).5.\quad a\equiv b\pmod m,\qquad c\equiv d\pmod m \Longrightarrow \begin{cases} a+c\equiv b+d\pmod m,\\ a-c\equiv b-d\pmod m,\\ ac\equiv bd\pmod m. \end{cases}
    6.a≡b(modm)⟹an≡bn(modm),n∈Z+6.\quad a\equiv b\pmod m \Longrightarrow a^n\equiv b^n\pmod m,\qquad n\in\mathbb Z^+
    7.ac≡bc(modm)⟺a≡b(modmgcd⁡(m,c)).7.\quad ac\equiv bc\pmod m \Longleftrightarrow a\equiv b \pmod{\frac{m}{\gcd(m,c)}}.
    8.a≡b(modm),d∣m⟹a≡b(modd).8.\quad a\equiv b\pmod m,\qquad d\mid m \Longrightarrow a\equiv b\pmod d.
  48. 48.
    Logarithms: Definition and Properties

    Definition

    log⁡bx=y  ⟺  by=x\log_b x = y \iff b^y = x

    Domain

    x>0,b>0,b≠1x>0,\qquad b>0,\qquad b\ne 1

    Range

    (−∞,+∞)(-\infty,+\infty)

    If b>1b>1, then y=log⁡bxy=\log_b x is increasing.

    If 0<b<10<b<1, then y=log⁡bxy=\log_b x is decreasing.

    Graph of y = log_b(x) for b>1 and 0<b<1, showing the increasing and decreasing cases.

    Properties

    1.log⁡b1=01.\quad \log_b 1 = 0
    2.log⁡bb=12.\quad \log_b b = 1
    3.log⁡b(bm)=m3.\quad \log_b(b^m) = m
    4.blog⁡ba=a4.\quad b^{\log_b a} = a
    5.log⁡ba+log⁡bc=log⁡b(ac)5.\quad \log_b a + \log_b c = \log_b(ac)
    6.log⁡ba−log⁡bc=log⁡b ⁣(ac)6.\quad \log_b a - \log_b c = \log_b\!\left(\frac{a}{c}\right)
    7.log⁡b(an)=nlog⁡ba7.\quad \log_b(a^n) = n\log_b a
    8.log⁡bma=1mlog⁡ba8.\quad \log_{b^m} a = \frac{1}{m}\log_b a
    9.log⁡b ⁣(1a)=−log⁡ba9.\quad \log_b\!\left(\frac{1}{a}\right) = -\log_b a
    10.log⁡ba⋅log⁡ac=log⁡bc10.\quad \log_b a \cdot \log_a c = \log_b c
    11.log⁡ba=log⁡calog⁡cb11.\quad \log_b a = \frac{\log_c a}{\log_c b}
    12.log⁡ba=ln⁡aln⁡b,where ln⁡x=log⁡ex, e=2.71828…12.\quad \log_b a = \frac{\ln a}{\ln b},\quad \text{where } \ln x = \log_e x,\ e=2.71828\ldots
    13.log⁡ba=1log⁡ab13.\quad \log_b a = \frac{1}{\log_a b}
    14.b(log⁡ax)(log⁡ba)=x14.\quad b^{(\log_a x)(\log_b a)} = x
    15.log⁡bx=log⁡by  ⟺  x=y15.\quad \log_b x = \log_b y \iff x = y
  49. 49.
    Two Approaches to Logarithm Problems

    Approach 1

    Convert to exponential form

    Approach 2

    Use a change of variable

  50. 50.
    Principle of Inclusion–Exclusion (PIE): Fundamentals and Extensions

    Inclusion–Exclusion Principle for two sets

    For finite sets AA and BB:

    ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|

    Inclusion–Exclusion Principle for three sets

    For finite sets AA, BB, and CC:

    ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

    General Inclusion–Exclusion Principle for $n$ sets

    For sets A1,A2,…,AnA_1,A_2,\dots,A_n:

    ∣A1∪A2∪⋯∪An∣=∑i∣Ai∣−∑i<j∣Ai∩Aj∣+∑i<j<k∣Ai∩Aj∩Ak∣−⋯|A_1\cup A_2\cup\cdots\cup A_n|=\sum_i |A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots

    In compact form, the general principle is:

    ∣⋃i=1nAi∣=∑k=1n(−1)k+1∑1≤i1<i2<⋯<ik≤n∣Ai1∩Ai2∩⋯∩Aik∣\left|\bigcup_{i=1}^{n} A_i\right|=\sum_{k=1}^{n}(-1)^{k+1}\sum_{1\le i_1<i_2<\cdots<i_k\le n}\left|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}\right|

    Counting elements in exactly one set

    Let PA1,A2,…,AnP_{A_1,A_2,\dots,A_n} denote the number of elements that are contained in exactly one of the sets A1,A2,…,AnA_1,A_2,\dots,A_n.

    For two sets:

    PA1,A2=∣A1∣+∣A2∣−2∣A1∩A2∣P_{A_1,A_2}=|A_1|+|A_2|-2|A_1\cap A_2|

    For three sets:

    PA1,A2,A3=∣A1∣+∣A2∣+∣A3∣−2∣A1∩A2∣−2∣A1∩A3∣−2∣A2∩A3∣+3∣A1∩A2∩A3∣P_{A_1,A_2,A_3}=|A_1|+|A_2|+|A_3|-2|A_1\cap A_2|-2|A_1\cap A_3|-2|A_2\cap A_3|+3|A_1\cap A_2\cap A_3|

    The coefficients here are different from the ordinary Inclusion–Exclusion formula.

  51. 51.
    Euler's Totient Function φ(n)
    φ(n)=∣{1≤i≤n∣gcd⁡(i,n)=1}∣\varphi(n)=|\{1\le i\le n\mid\gcd(i,n)=1\}|

    φ(n)\varphi(n) is the number of integers from 11 to nn that are relatively prime to nn.

    If n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k},

    φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk)\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)
  52. 52.
    Euler's Theorem

    Let nn be a positive integer. If gcd⁡(n,a)=1\gcd(n,a)=1,

    aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n
  53. 53.
    Graphing Functions: Transformations and Absolute Value Functions

    Graph of ∣x∣+∣y∣=5|x|+|y|=5:

    Graph of |x| + |y| = 5

    Graph of (x−3)2+(y−4)2=9(x-3)^2+(y-4)^2=9:

    Graph of (x - 3)^2 + (y - 4)^2 = 9

    Graph of ∣x−3∣+∣y+2∣=1|x-3|+|y+2|=1:

    Graph of |x - 3| + |y + 2| = 1

    To graph absolute value equations, split the absolute values into cases, graph each case separately, and then combine the pieces.

    Graph of ||x| - 1| + ||y| - 1| = 1

    Graph of y=12xy=\dfrac{1}{2x}:

    Graph of y = 1/(2x)

    Graph Transformations

    TransformationExampleDescription
    Horizontal Shifty=f(x−3)y=f(x-3)Shift 3 units to the right
    Vertical Shifty=f(x)+2y=f(x)+2Shift 2 units upward
    Horizontal Stretchy=f(x/2)y=f(x/2)Stretch horizontally by a factor of 2
    Horizontal Compressiony=f(2x)y=f(2x)Compress horizontally by a factor of 2
    Vertical Stretchy=3f(x)y=3f(x)Stretch vertically by a factor of 3
    Vertical Compressiony=12f(x)y=\frac{1}{2}f(x)Compress vertically by a factor of 2
    Reflection across the x-axisy=−f(x)y=-f(x)Flip over the x-axis
    Reflection across the y-axisy=f(−x)y=f(-x)Flip over the y-axis
  54. 54.
    Area Formulas and Important Geometry Formulas

    Triangle Area Formulas

    1. Base and Height Formula

    Triangle with altitude h from A to BC at D
    [ABC]=12⋅AD⋅BC[ABC]=\frac{1}{2}\cdot AD\cdot BC

    2. Two Sides and Included Angle Formula

    Triangle with sides a, b, c
    [ABC]=12bcsin⁡A[ABC]=\frac{1}{2}bc\sin A

    3. Heron's Formula

    Triangle with sides a, b, c
    s=a+b+c2s=\frac{a+b+c}{2}
    [ABC]=s(s−a)(s−b)(s−c)[ABC]=\sqrt{s(s-a)(s-b)(s-c)}

    4. Expanded Heron's Formula

    Triangle with sides a, b, c
    16[ABC]2=4a2b2c2−(a2+b2−c2)216[ABC]^2=4a^2b^2c^2-(a^2+b^2-c^2)^2

    Quadrilateral Area Formulas

    General Quadrilateral

    Convex quadrilateral with diagonals intersecting at angle alpha
    [ABCD]=12AC⋅BDsin⁡α[ABCD]=\frac{1}{2}AC\cdot BD\sin\alpha

    Orthogonal Diagonals

    Quadrilateral with perpendicular diagonals
    [ABCD]=12AC⋅BD[ABCD]=\frac{1}{2}AC\cdot BD

    Circle Formulas

    Circle Area and Circumference

    Circle with radius r and center O
    Area=πr2\text{Area}=\pi r^2
    Circumference=2πr\text{Circumference}=2\pi r

    Sector Area and Arc Length

    Circular sector with radius r and central angle alpha

    If α\alpha is in degrees:

    Area=α360πr2\text{Area}=\frac{\alpha}{360}\pi r^2
    Length of arc AB=α360⋅2πr\text{Length of arc }AB=\frac{\alpha}{360}\cdot2\pi r

    Special Right Triangles

    30-60-90 Triangle

    30-60-90 right triangle
    Sides are a, a32, a2\text{Sides are } a,\ \frac{a\sqrt3}{2},\ \frac{a}{2}

    45-45-90 Triangle

    45-45-90 right isosceles triangle
    Sides are a22, a22, a\text{Sides are }\frac{a\sqrt2}{2},\ \frac{a\sqrt2}{2},\ a

    Equilateral Triangle

    Equilateral triangle with altitude AM
    AM=a32AM=\frac{a\sqrt3}{2}
    [ABC]=a234[ABC]=\frac{a^2\sqrt3}{4}

    Trapezoid

    Trapezoid ABCD with height h
    [ABCD]=h(AB+CD)2[ABCD]=\frac{h(AB+CD)}{2}

    Parallelogram

    Parallelogram ABCD with height h
    [ABCD]=h⋅AB[ABCD]=h\cdot AB
  55. 55.
    Shoelace Theorem
    Polygon with vertices A_1 through A_n

    The vertices should be written in clockwise or counterclockwise order:

    A1(x1,y1), A2(x2,y2), …, An(xn,yn)A_1(x_1,y_1),\ A_2(x_2,y_2),\ \ldots,\ A_n(x_n,y_n)

    The area of the polygon is:

    Area=12∣x1y2+x2y3+⋯+xn−1yn+xny1−y1x2−y2x3−⋯−yn−1xn−ynx1∣\text{Area}=\tfrac{1}{2}\bigl|x_1y_2+x_2y_3+\cdots+x_{n-1}y_n+x_ny_1-y_1x_2-y_2x_3-\cdots-y_{n-1}x_n-y_nx_1\bigr|
  56. 56.
    Gauss' Idea (Rainbow Idea)

    Pair up the elements:

    Gauss pairing 1+100, 2+99, ... equals 50 x 101

    or

    S=1+2+3+⋯+98+99+100S=1+2+3+\cdots+98+99+100
    S=100+99+98+⋯+3+2+1S=100+99+98+\cdots+3+2+1
    2S=101+101+⋯+1012S=101+101+\cdots+101
    2S=100×1012S=100\times101

    Therefore:

    S=100×1012S=\frac{100\times101}{2}
  57. 57.
    Famous Trigonometric Values

    For the following important angles:

    θ\thetasin⁡θ\sin\thetacos⁡θ\cos\thetatan⁡θ\tan\thetacot⁡θ\cot\theta
    0∘0^\circ001100Undefined
    30∘30^\circ12\tfrac{1}{2}32\tfrac{\sqrt3}{2}33\tfrac{\sqrt3}{3}3\sqrt3
    45∘45^\circ22\tfrac{\sqrt2}{2}22\tfrac{\sqrt2}{2}1111
    60∘60^\circ32\tfrac{\sqrt3}{2}12\tfrac{1}{2}3\sqrt333\tfrac{\sqrt3}{3}
    90∘90^\circ1100Undefined00
    180∘180^\circ00−1-100Undefined
    270∘270^\circ−1-100Undefined00
  58. 58.
    Law of Cosines
    Triangle ABC with sides a, b, c

    For a triangle with sides aa, bb, cc:

    a2=b2+c2−2bccos⁡Aa^2=b^2+c^2-2bc\cos A

    or

    cos⁡A=b2+c2−a22bc\cos A=\frac{b^2+c^2-a^2}{2bc}
  59. 59.
    Ptolemy's Theorem
    Cyclic quadrilateral ABCD with diagonals

    A quadrilateral ABCDABCD is cyclic if and only if:

    AB⋅CD+AD⋅BC=AC⋅BDAB\cdot CD+AD\cdot BC=AC\cdot BD
  60. 60.
    Angles in Circles

    Central Angle

    Central angle equal to arc alpha

    Inscribed Angle

    Inscribed angle equal to half of arc alpha

    Tangent-Chord Angle

    Tangent-chord angle equal to half of arc alpha

    Interior Angle

    Interior angle equal to (alpha + beta)/2

    Exterior Angle

    Exterior angle equal to (beta - alpha)/2
  61. 61.
    4 Rules of Cyclic Quadrilaterals

    1. Opposite angles are supplementary

    Cyclic quadrilateral ABCD inscribed in a circle

    ABCDABCD is cyclic if and only if:

    ∠A+∠C=180∘\angle A+\angle C=180^\circ

    or

    ∠B+∠D=180∘\angle B+\angle D=180^\circ

    2. Equal angles subtend the same chord

    Cyclic quadrilateral with equal angles at A and C

    ABCDABCD is cyclic if and only if:

    ∠A1=∠C1\angle A_1=\angle C_1

    3. Intersecting chords

    Diagonals of cyclic quadrilateral intersecting at P inside the circle

    ABCDABCD is cyclic if and only if:

    PA⋅PC=PB⋅PDPA\cdot PC=PB\cdot PD

    4. Power of a point

    Secants from external point P meeting the circle

    ABCDABCD is cyclic if and only if:

    PA⋅PD=PB⋅PCPA\cdot PD=PB\cdot PC
  62. 62.
    Consider the Unit Circle in Trigonometry
    Unit circle showing sin alpha and cos alpha
    Unit circle showing tan alpha and cot alpha
  63. 63.
    Derivative
    Tangent line to f(x) at x0 with slope f'(x0)

    Definition

    The derivative represents the slope of the tangent line:

    f′(x0)=lim⁡h→0f(x0+h)−f(x0)hf'(x_0)=\lim_{h\to 0}\frac{f(x_0+h)-f(x_0)}{h}

    For finding local maximum and minimum, consider:

    f′(x)=0f'(x)=0
    Local maximum, local minimum, and saddle point on a curve

    Basic derivative rules

    (c)′=0(c)'=0
    (xn)′=n xn−1(x^n)'=n\,x^{n-1}
    (cf(x))′=c f′(x)(cf(x))'=c\,f'(x)
    (f(x)+g(x))′=f′(x)+g′(x)(f(x)+g(x))'=f'(x)+g'(x)
    (f(x)g(x))′=f′(x)g(x)+f(x)g′(x)(f(x)g(x))'=f'(x)g(x)+f(x)g'(x)
    (f(x)g(x))′=f′(x)g(x)−f(x)g′(x)g(x)2\left(\frac{f(x)}{g(x)}\right)'=\frac{f'(x)g(x)-f(x)g'(x)}{g(x)^2}

    Chain Rule

    (f(g(x)))′=f′(g(x))⋅g′(x)(f(g(x)))'=f'(g(x))\cdot g'(x)

    Common derivatives

    (xn)′=n xn−1(x^n)'=n\,x^{n-1}
    (un)′=n un−1u′(u^n)'=n\,u^{n-1}u'
    (ex)′=ex(e^x)'=e^x
    (ln⁡x)′=1x(\ln x)'=\frac{1}{x}
    (sin⁡x)′=cos⁡x(\sin x)'=\cos x
    (cos⁡x)′=−sin⁡x(\cos x)'=-\sin x
    (tan⁡x)′=1+tan⁡2x(\tan x)'=1+\tan^2 x
    (cot⁡x)′=−(1+cot⁡2x)(\cot x)'=-(1+\cot^2 x)

    If:

    f′(x)>0 ⇒ f(x) increasesf'(x)>0\ \Rightarrow\ f(x)\ \text{increases}
    f′(x)<0 ⇒ f(x) decreasesf'(x)<0\ \Rightarrow\ f(x)\ \text{decreases}
    Sign of derivative around local maximum and local minimum
  64. 64.
    Remainder Rules

    Divisibility by 3

    The remainder of nn when divided by 33 is equal to the remainder of the sum of the digits of nn when divided by 33.

    Divisibility by 9

    The remainder of nn when divided by 99 is equal to the remainder of the sum of the digits of nn when divided by 99.

    Divisibility by 11

    The remainder of nn when divided by 1111 is equal to the remainder of the alternating sum of its digits.

    Example:

    53295≡9−2+3−5=5(mod11)53295\equiv 9-2+3-5=5\pmod{11}

    From right to left, consider the signs ++ and −- alternately.

    Divisibility by 2, 5, and 10

    Only the last digit matters.

    Divisibility by 4, 25, and 100

    Only the last two digits matter.

    Divisibility by 8, 125, and 1000

    Only the last three digits matter.

  65. 65.
    Casework: Start with the Most Limiting Case

    Constraints can be based on the number of elements, on the size of the elements, or on other conditions.

    But usually, if you base your answer on the most limiting case, it will make the problem easier to solve.

  66. 66.
    Signs Have No Effect on the Parity
    ∣ ∣ ∣a∣−∣b∣+∣c∣−∣d∣ ∣ ∣≡a+b+c+d(mod2)\bigl|\,|\,|a|-|b|+|c|-|d|\,|\,\bigr|\equiv a+b+c+d\pmod{2}
  67. 67.
    When We Have a Trapezoid in a Problem, Draw the Altitudes
    Trapezoid ABCD with altitudes drawn from A and B to base DC
  68. 68.
    Circles, Tangents, and Radical Axis

    1. Tangent and Radius

    Radius perpendicular to tangent line at point of tangency

    The radius is perpendicular to the tangent line.

    OP⊥tangentOP\perp\text{tangent}

    2. Two Tangents from an External Point

    Two tangents from external point A meeting circle at B and C

    If two tangents are drawn from the same external point, their lengths are equal.

    AB=ACAB=AC

    3. Radical Axis

    Two intersecting circles with radical axis through intersection points

    When two circles intersect, draw the radical axis. It is usually useful in angle chasing.

    The radical axis is the line passing through the intersection points of the two circles.

    4. Two Tangent Circles

    When two circles are tangent, the centers and the tangent point are collinear.

    Two externally tangent circles with centers O1, O2 and tangent point P

    For externally tangent circles:

    O1, P, O2 are collinearO_1,\,P,\,O_2\ \text{are collinear}
    O1O2=R1+R2O_1O_2=R_1+R_2

    5. One Circle Inside Another (Internally Tangent)

    Small circle inside larger circle, internally tangent at point P

    For internally tangent circles:

    O1, O2, P are collinearO_1,\,O_2,\,P\ \text{are collinear}
    O1O2=R2−R1O_1O_2=R_2-R_1
  69. 69.
    Two Approaches for Square Roots

    1) Square it.

    2) Use a changing variable.

  70. 70.
    Geometric Approach in Probability

    1 dimension

    0≤x≤10\le x\le 1
    P ⁣(13<x<12)=12−13=16P\!\left(\tfrac{1}{3}<x<\tfrac{1}{2}\right)=\tfrac{1}{2}-\tfrac{1}{3}=\tfrac{1}{6}
    Number line from 0 to 1 with segment between 1/3 and 1/2 highlighted

    2 dimensions

    0≤x,y≤10\le x,y\le 1
    P(∣x−y∣≥12)=2×12×122=14P(|x-y|\ge \tfrac{1}{2})=2\times\frac{\tfrac{1}{2}\times\tfrac{1}{2}}{2}=\tfrac{1}{4}
    Unit square with two shaded triangles representing |x-y| >= 1/2

    3 dimensions

    0≤x,y,z≤10\le x,y,z\le 1
    P(x+y+z≤1)=12×12×123=16P(x+y+z\le 1)=\frac{\tfrac{1}{2}\times\tfrac{1}{2}\times\tfrac{1}{2}}{3}=\tfrac{1}{6}
    Unit cube with tetrahedron representing x+y+z <= 1 shaded
  71. 71.
    Stars and Bars

    71.1

    x+y+z=20x+y+z=20

    xx, yy, zz are positive integers.

    20 stars divided into three groups x, y, z by two dividers

    There are

    (192)\binom{19}{2}

    ways to place two dividers between 20 stars.

    71.2

    x1+x2+⋯+xk=nx_1+x_2+\cdots+x_k=n
    xi≥1x_i\ge 1
    (n−1k−1)\boxed{\binom{n-1}{k-1}}

    71.3

    x+y+z+w=30x+y+z+w=30
    x≥−5,y≥3,z≥0,w≥1x\ge -5,\qquad y\ge 3,\qquad z\ge 0,\qquad w\ge 1

    Transform the variables as follows:

    x′=x+6≥1x'=x+6\ge 1
    y′=y−2≥1y'=y-2\ge 1
    z′=z+1≥1z'=z+1\ge 1
    w′=w≥1w'=w\ge 1

    Then

    x′+y′+z′+w′=35x'+y'+z'+w'=35

    so the number of solutions is

    (343)\boxed{\binom{34}{3}}

    71.4

    x+y+z≤30x+y+z\le 30
    x,y,z≥1x,y,z\ge 1

    Consider the possible values of x+y+zx+y+z:

    x+y+z#(x,y,z)30(292)29(282)28(272)⋮⋮3(22)\def\arraystretch{1.8}\begin{array}{c|c} x+y+z & \#(x,y,z)\\[6pt] \hline 30 & \binom{29}{2}\\[10pt] 29 & \binom{28}{2}\\[10pt] 28 & \binom{27}{2}\\[10pt] \vdots & \vdots\\[10pt] 3 & \binom{2}{2} \end{array}

    By Toolkit 16 — Hockey Stick Identity,

    #(x,y,z)=(22)+(32)+⋯+(292)=(303)\#(x,y,z)=\binom{2}{2}+\binom{3}{2}+\cdots+\binom{29}{2}=\boxed{\binom{30}{3}}

    71.5

    x+y+z=20x+y+z=20
    7≥x≥17\ge x\ge 1
    y≥1y\ge 1
    z≥1z\ge 1

    Total:

    x+y+z=20,x,y,z≥1x+y+z=20,\qquad x,y,z\ge 1
    (192)\binom{19}{2}

    Unfavorable:

    x+y+z=20x+y+z=20
    x≥8,y≥1,z≥1x\ge 8,\qquad y\ge 1,\qquad z\ge 1

    Set

    x′=x−7≥1.x'=x-7\ge 1.

    Then

    x′+y+z=13x'+y+z=13

    and the number of unfavorable solutions is

    (122).\binom{12}{2}.

    Therefore,

    Favorable=(192)−(122)\boxed{\text{Favorable}=\binom{19}{2}-\binom{12}{2}}
  72. 72.
    Double Counting (Consider from Different Aspects)
    A,B⊆{1,2,…,n}A,B\subseteq\{1,2,\ldots,n\}
    A∩B=∅A\cap B=\varnothing

    Instead of considering the subsets, we should consider the elements.

    Each element has 3 possible choices for AA and BB:

    AB✓✓✓××✓\begin{array}{c|c} A & B\\ \hline \checkmark & \checkmark\\ \checkmark & \times\\ \times & \checkmark \end{array}

    Therefore,

    3⋅3⋅3⋯3⏟n times=3n.\underbrace{3\cdot 3\cdot 3\cdots 3}_{n\text{ times}}=3^n.
  73. 73.
    3 Approaches for Finding the Closed Form of aₙ

    73.1

    an=an−1+3n−4,n≥1a_n=a_{n-1}+3n-4,\qquad n\ge 1
    a0=7a_0=7

    Write the consecutive equations:

    an−an−1=3n−4a_n-a_{n-1}=3n-4
    an−1−an−2=3n−7a_{n-1}-a_{n-2}=3n-7
    an−2−an−3=3n−10a_{n-2}-a_{n-3}=3n-10
    ⋮\vdots
    a2−a1=3(2)−4a_2-a_1=3(2)-4
    a1−a0=3(1)−4a_1-a_0=3(1)-4

    Add these equations so that the intermediate terms telescope:

    an−a0=((3(1)−4)+(3n−4))n2=(3n−5)n2.a_n-a_0=\frac{((3(1)-4)+(3n-4))n}{2}=\frac{(3n-5)n}{2}.

    Therefore,

    an=n(3n−5)2+a0=n(3n−5)2+7.a_n=\frac{n(3n-5)}{2}+a_0=\boxed{\frac{n(3n-5)}{2}+7}.

    73.2

    If the coefficient of an−1a_{n-1} is a constant different from 11:

    an=2an−1+5,n≥1a_n=2a_{n-1}+5,\qquad n\ge 1
    a0=9a_0=9

    Let

    bn=an2n.b_n=\frac{a_n}{2^n}.

    From

    an=2an−1+5,a_n=2a_{n-1}+5,

    divide by 2n2^n:

    an2n=an−12n−1+52n.\frac{a_n}{2^n}=\frac{a_{n-1}}{2^{n-1}}+\frac{5}{2^n}.

    Therefore,

    bn=bn−1+52n,n≥1,b_n=b_{n-1}+\frac{5}{2^n},\qquad n\ge 1,

    and

    b0=a020=9.b_0=\frac{a_0}{2^0}=9.

    Now write:

    bn−bn−1=52nb_n-b_{n-1}=\frac{5}{2^n}
    bn−1−bn−2=52n−1b_{n-1}-b_{n-2}=\frac{5}{2^{n-1}}
    bn−2−bn−3=52n−2b_{n-2}-b_{n-3}=\frac{5}{2^{n-2}}
    ⋮\vdots
    b2−b1=522b_2-b_1=\frac{5}{2^2}
    b1−b0=521.b_1-b_0=\frac{5}{2^1}.

    Adding gives

    bn−b0=521+522+⋯+52n−1+52n.b_n-b_0=\frac{5}{2^1}+\frac{5}{2^2}+\cdots+\frac{5}{2^{n-1}}+\frac{5}{2^n}.

    Then

    bn−b0=52(1+12+⋯+12n−2+12n−1).b_n-b_0=\frac{5}{2}\left(1+\frac{1}{2}+\cdots+\frac{1}{2^{n-2}}+\frac{1}{2^{n-1}}\right).

    Using the geometric series,

    bn−b0=52⋅1−12n1−12=5(1−12n).b_n-b_0=\frac{5}{2}\cdot\frac{1-\frac{1}{2^n}}{1-\frac{1}{2}}=5\left(1-\frac{1}{2^n}\right).

    Thus,

    bn=5(1−12n)+b0=14−52n.b_n=5\left(1-\frac{1}{2^n}\right)+b_0=14-\frac{5}{2^n}.

    Since

    an=2nbn,a_n=2^n b_n,

    we get

    an=14⋅2n−5.\boxed{a_n=14\cdot 2^n-5}.

    73.3

    If the coefficient of an−1a_{n-1} is nn:

    an=nan−1+(n−2)!,n≥2a_n=na_{n-1}+(n-2)!,\qquad n\ge 2
    a1=5a_1=5

    Let

    bn=ann!.b_n=\frac{a_n}{n!}.

    From

    an=nan−1+(n−2)!,a_n=na_{n-1}+(n-2)!,

    divide by n!n!:

    ann!=an−1(n−1)!+(n−2)!n!.\frac{a_n}{n!}=\frac{a_{n-1}}{(n-1)!}+\frac{(n-2)!}{n!}.

    Therefore,

    bn=bn−1+1n(n−1)=bn−1+1n−1−1n,n≥2.b_n=b_{n-1}+\frac{1}{n(n-1)}=b_{n-1}+\frac{1}{n-1}-\frac{1}{n},\qquad n\ge 2.

    Also,

    b1=a11!=5.b_1=\frac{a_1}{1!}=5.

    Now write:

    bn−bn−1=1n−1−1nb_n-b_{n-1}=\frac{1}{n-1}-\frac{1}{n}
    bn−1−bn−2=1n−2−1n−1b_{n-1}-b_{n-2}=\frac{1}{n-2}-\frac{1}{n-1}
    bn−2−bn−3=1n−3−1n−2b_{n-2}-b_{n-3}=\frac{1}{n-3}-\frac{1}{n-2}
    ⋮\vdots
    b3−b2=12−13b_3-b_2=\frac{1}{2}-\frac{1}{3}
    b2−b1=1−12.b_2-b_1=1-\frac{1}{2}.

    After telescoping,

    bn−b1=1−1n.b_n-b_1=1-\frac{1}{n}.

    Therefore,

    bn=1−1n+b1=6−1n.b_n=1-\frac{1}{n}+b_1=6-\frac{1}{n}.

    Hence,

    an=n! bn=6n!−(n−1)!.a_n=n!\,b_n=6n!-(n-1)!.

    So,

    an=6n!−(n−1)!.\boxed{a_n=6n!-(n-1)!}.
  74. 74.
    Triangle Method for Identities with Coefficients

    Start with:

    1⋅21+2⋅22+3⋅23+⋯+(n−1)2n−1+n 2n.1\cdot 2^1+2\cdot 2^2+3\cdot 2^3+\cdots+(n-1)2^{n-1}+n\,2^n.

    Write the following equations in a triangular arrangement:

    21+22+23+⋯+2n−1+2n ⟶ 2n+1−21  22+23+⋯+2n−1+2n ⟶ 2n+1−22  23+⋯+2n−1+2n ⟶ 2n+1−23  ⋮  2n−1+2n ⟶ 2n+1−2n−1 2n ⟶ 2n+1−2n\begin{array}{l} 2^1+2^2+2^3+\cdots+2^{n-1}+2^n\ \longrightarrow\ 2^{n+1}-2^1\\[2pt] \qquad\ \ 2^2+2^3+\cdots+2^{n-1}+2^n\ \longrightarrow\ 2^{n+1}-2^2\\[2pt] \qquad\qquad\ \ 2^3+\cdots+2^{n-1}+2^n\ \longrightarrow\ 2^{n+1}-2^3\\[2pt] \qquad\qquad\qquad\qquad\ \ \vdots\\[2pt] \qquad\qquad\qquad\qquad\qquad\ \ 2^{n-1}+2^n\ \longrightarrow\ 2^{n+1}-2^{n-1}\\[2pt] \qquad\qquad\qquad\qquad\qquad\qquad\qquad\ 2^n\ \longrightarrow\ 2^{n+1}-2^n \end{array}

    Then add them:

    =n 2n+1−(21+22+23+⋯+2n−1+2n).=n\,2^{n+1}-\left(2^1+2^2+2^3+\cdots+2^{n-1}+2^n\right).

    Since

    21+22+⋯+2n−1+2n=2n+1−21,2^1+2^2+\cdots+2^{n-1}+2^n=2^{n+1}-2^1,

    we get

    =n 2n+1−(2n+1−21)=n\,2^{n+1}-(2^{n+1}-2^1)
    =(n−1)2n+1+21.=\boxed{(n-1)2^{n+1}+2^1}.
  75. 75.
    Try Small Examples
  76. 76.
    3 Ideas in Paths

    Idea 1. Placing Numbers

    1) Origin =1=1.

    2) Number at each position == the sum of the numbers at exactly the previous positions.

    At each step, we can jump 1 or 2 units to the right or one unit upward.

    # ways from AA to BB

    Grid from A to B with numbers placed at each intersection, illustrating the placing-numbers approach

    Idea 2. Permutation

    At each step, we can jump 1 unit to the right or one unit upward.

    # ways from AA to BB

    Grid from A to B with a sample lattice path highlighted

    Each path corresponds to a permutation of 5 RR's and 3 UU's.

    RRRRRUUURRRRRUUU
    8!5! 3!=8⋅7⋅63!=56\frac{8!}{5!\,3!}=\frac{8\cdot 7\cdot 6}{3!}=56

    Idea 3. Levels

    At each step, we can jump 1 unit to the right, one unit upward, or 1 unit to the left.

    We can't pass through a point more than once.

    # ways from AA to BB

    Grid from A to B split into 4 horizontal levels with arrows indicating transitions

    There are 4 levels (horizontal lines). If we only determine the places where we go to the next level, then the path will be determined.

    6⏟Level 1 to 2×6⏟Level 2 to 3×6⏟Level 3 to 4=63=216\underbrace{6}_{\text{Level 1 to 2}}\times\underbrace{6}_{\text{Level 2 to 3}}\times\underbrace{6}_{\text{Level 3 to 4}}=6^3=216
  77. 77.
    sin, cos, tan, cot — Special Angles

    15° and 75°

    Anglesin⁡θ\sin\thetacos⁡θ\cos\thetatan⁡θ\tan\thetacot⁡θ\cot\theta
    15∘15^\circ6−24\dfrac{\sqrt{6}-\sqrt{2}}{4}6+24\dfrac{\sqrt{6}+\sqrt{2}}{4}2−32-\sqrt{3}2+32+\sqrt{3}
    75∘75^\circ6+24\dfrac{\sqrt{6}+\sqrt{2}}{4}6−24\dfrac{\sqrt{6}-\sqrt{2}}{4}2+32+\sqrt{3}2−32-\sqrt{3}

    18°, 36°, 54°, and 72°

    Anglesin⁡θ\sin\thetacos⁡θ\cos\thetatan⁡θ\tan\thetacot⁡θ\cot\theta
    18∘18^\circ5−14\dfrac{\sqrt{5}-1}{4}10+254\dfrac{\sqrt{10+2\sqrt{5}}}{4}15+25\dfrac{1}{\sqrt{5+2\sqrt{5}}}5+25\sqrt{5+2\sqrt{5}}
    36∘36^\circ10−254\dfrac{\sqrt{10-2\sqrt{5}}}{4}1+54\dfrac{1+\sqrt{5}}{4}5−25\sqrt{5-2\sqrt{5}}15−25\dfrac{1}{\sqrt{5-2\sqrt{5}}}
    54∘54^\circ1+54\dfrac{1+\sqrt{5}}{4}10−254\dfrac{\sqrt{10-2\sqrt{5}}}{4}15−25\dfrac{1}{\sqrt{5-2\sqrt{5}}}5−25\sqrt{5-2\sqrt{5}}
    72∘72^\circ10+254\dfrac{\sqrt{10+2\sqrt{5}}}{4}5−14\dfrac{\sqrt{5}-1}{4}5+25\sqrt{5+2\sqrt{5}}15+25\dfrac{1}{\sqrt{5+2\sqrt{5}}}
  78. 78.
    When ab = x² or ab = px²

    aa and bb are positive integers.

    78.1

    If ab=x2ab=x^2 and gcd⁡(a,b)=1\gcd(a,b)=1, then a=y2, b=z2a=y^2,\ b=z^2.

    78.2

    If ab=x2ab=x^2 and gcd⁡(a,b)=d\gcd(a,b)=d, then a=dy2, b=dz2a=dy^2,\ b=dz^2.

    pp is a prime number.

    78.3

    If ab=px2ab=px^2 and gcd⁡(a,b)=1\gcd(a,b)=1, then a=py2, b=z2a=py^2,\ b=z^2 or a=y2, b=pz2a=y^2,\ b=pz^2.

    78.4

    If ab=px2ab=px^2 and gcd⁡(a,b)=d\gcd(a,b)=d, then a=dpy2, b=dz2a=dpy^2,\ b=dz^2 or a=dy2, b=dpz2a=dy^2,\ b=dpz^2.

  79. 79.
    Calculate gcd(a,b)

    Use the following example: gcd⁡(2n+3, 5n−4)=d\gcd(2n+3,\,5n-4)=d.

    Since d∣2n+3d\mid 2n+3, multiply by 55:  d∣10n+15\ d\mid 10n+15.

    Since d∣5n−4d\mid 5n-4, multiply by 22:  d∣10n−8\ d\mid 10n-8.

    Subtracting gives d∣23d\mid 23, so d=1d=1 or 2323.

    At the end, we should find at least one value of nn for each possible value of dd to prove that the value of dd is reachable.

    Examples:  n=1: gcd⁡(5,1)=1;n=10: gcd⁡(23,46)=23\ n=1:\ \gcd(5,1)=1;\qquad n=10:\ \gcd(23,46)=23.

  80. 80.
    Trigonometric Ratios in a Right Triangle
    Right triangle ABC with right angle at A and angle alpha at C
    sin⁡α=Opposite SideHypotenuse=ABBC\sin\alpha=\frac{\text{Opposite Side}}{\text{Hypotenuse}}=\frac{AB}{BC}
    cos⁡α=Adjacent SideHypotenuse=ACBC\cos\alpha=\frac{\text{Adjacent Side}}{\text{Hypotenuse}}=\frac{AC}{BC}
    tan⁡α=Opposite SideAdjacent Side=ABAC\tan\alpha=\frac{\text{Opposite Side}}{\text{Adjacent Side}}=\frac{AB}{AC}
    cot⁡α=Adjacent SideOpposite Side=ACAB\cot\alpha=\frac{\text{Adjacent Side}}{\text{Opposite Side}}=\frac{AC}{AB}
  81. 81.
    Substitution

    Example: Philippine Mathematical Olympiad

    The next problem is from the 2022 Philippine Mathematical Olympiad — Qualifying Stage.

    Problem 20: Let a,b,ca,b,c be real numbers such that

    3ab+2=6b,3bc+2=5c,3ca+2=4a.3ab+2=6b,\qquad 3bc+2=5c,\qquad 3ca+2=4a.

    Suppose the only possible values for the product abcabc are r/sr/s and t/ut/u, where r/sr/s and t/ut/u are both fractions in lowest terms. Find

    r+s+t+u.r+s+t+u.

    Solution

    3ca+2=4a ⇒ 3ca=4a−2 ⇒ c=4a−23a(1)3ca+2=4a\ \Rightarrow\ 3ca=4a-2\ \Rightarrow\ c=\frac{4a-2}{3a}\hspace{4em}(1)
    3ab+2=6b ⇒ 2=b(6−3a) ⇒ b=26−3a(2)3ab+2=6b\ \Rightarrow\ 2=b(6-3a)\ \Rightarrow\ b=\frac{2}{6-3a}\hspace{4em}(2)

    Substitute (1) and (2) into 3bc+2=5c3bc+2=5c:

    3(26−3a)(4a−23a)+2=5(4a−23a) ⇒ (22−a)(4a−23a)+2=5(4a−23a)3\left(\tfrac{2}{6-3a}\right)\left(\tfrac{4a-2}{3a}\right)+2=5\left(\tfrac{4a-2}{3a}\right)\ \Rightarrow\ \left(\tfrac{2}{2-a}\right)\left(\tfrac{4a-2}{3a}\right)+2=5\left(\tfrac{4a-2}{3a}\right)
    ⇒ 2(4a−2)+2(2−a)(3a)=5(4a−2)(2−a) ⇒ 8a−4+12a−6a2=40a−20a2−20+10a\Rightarrow\ 2(4a-2)+2(2-a)(3a)=5(4a-2)(2-a)\ \Rightarrow\ 8a-4+12a-6a^2=40a-20a^2-20+10a
    ⇒ 14a2−30a+16=0 ⇒ 7a2−15a+8=0 ⇒ (7a−8)(a−1)=0 ⇒ a=1 or a=87\Rightarrow\ 14a^2-30a+16=0\ \Rightarrow\ 7a^2-15a+8=0\ \Rightarrow\ (7a-8)(a-1)=0\ \Rightarrow\ a=1\ \text{or}\ a=\tfrac{8}{7}

    Case 1

    a=1 ⇒ b=26−3a=23 ⇒ c=4a−23a=23 ⇒ abc=49=rsa=1\ \Rightarrow\ b=\tfrac{2}{6-3a}=\tfrac{2}{3}\ \Rightarrow\ c=\tfrac{4a-2}{3a}=\tfrac{2}{3}\ \Rightarrow\ abc=\tfrac{4}{9}=\tfrac{r}{s}

    Case 2

    a=87 ⇒ b=26−3a=26−247=79 ⇒ c=4a−23a=327−2247=34a=\tfrac{8}{7}\ \Rightarrow\ b=\tfrac{2}{6-3a}=\tfrac{2}{6-\frac{24}{7}}=\tfrac{7}{9}\ \Rightarrow\ c=\tfrac{4a-2}{3a}=\tfrac{\frac{32}{7}-2}{\frac{24}{7}}=\tfrac{3}{4}
    ⇒ abc=87⋅79⋅34=23=tu ⇒ r=4, s=9, t=2, u=3 ⇒ r+s+t+u=18\Rightarrow\ abc=\tfrac{8}{7}\cdot\tfrac{7}{9}\cdot\tfrac{3}{4}=\tfrac{2}{3}=\tfrac{t}{u}\ \Rightarrow\ r=4,\ s=9,\ t=2,\ u=3\ \Rightarrow\ r+s+t+u=18
  82. 82.
    3D Shapes: Surface Area and Volume

    Total Surface Area (TSA) and Volume

    Cube

    Cube with side length a
    TSA=6a2\mathrm{TSA}=6a^2
    V=a3V=a^3

    Rectangular Prism (Cuboid)

    Rectangular prism with sides a, b, c
    TSA=2(ab+ac+bc)\mathrm{TSA}=2(ab+ac+bc)
    V=abcV=abc

    Prism

    Oblique prism with height h
    V=h⋅AreabaseV=h\cdot \text{Area}_{\text{base}}

    Sphere

    Sphere with radius r
    TSA=4πr2\mathrm{TSA}=4\pi r^2
    V=43πr3V=\frac{4}{3}\pi r^3

    Cylinder

    Cylinder with radius r and height h
    TSA=2πr(r+h)\mathrm{TSA}=2\pi r(r+h)
    Lateral Area=2πrh\text{Lateral Area}=2\pi rh
    V=πr2hV=\pi r^2h

    Cone

    Cone with radius r, height h, slant l
    TSA=πr(r+l)\mathrm{TSA}=\pi r(r+l)
    Lateral Area=πrl\text{Lateral Area}=\pi rl
    l=r2+h2l=\sqrt{r^2+h^2}
    V=13πr2hV=\frac{1}{3}\pi r^2h

    Pyramid

    Pyramid with base area B and height h
    V=13Areabase⋅hV=\frac{1}{3}\text{Area}_{\text{base}}\cdot h

    Regular Tetrahedron

    Regular tetrahedron with edge a
    TSA=a23\mathrm{TSA}=a^2\sqrt{3}
    h=a23h=a\sqrt{\dfrac{2}{3}}
    V=a3212V=\frac{a^3\sqrt{2}}{12}
  83. 83.
    Diagonal of a Grid
    Diagonal of an m by n grid crossing lattice lines

    If you draw the diagonal of an m×nm\times n grid, then the diagonal is split into m+n−gcd⁡(m,n)m+n-\gcd(m,n) parts.

  84. 84.
    Ratios of Areas
    Triangle ABC with cevian AP
    [APB][APC]=BPPC\frac{[APB]}{[APC]}=\frac{BP}{PC}
    Triangle ABC with point L on cevian AP
    [ALB][ALC]=BPPC\frac{[ALB]}{[ALC]}=\frac{BP}{PC}
  85. 85.
    Menelaus' Theorem
    Menelaus configuration with transversal cutting triangle ABC
    Menelaus configuration with transversal cutting extensions
    DBDC⋅ECEA⋅FAFB=1\frac{DB}{DC}\cdot\frac{EC}{EA}\cdot\frac{FA}{FB}=1

    if and only if D,E,FD,E,F are collinear.

  86. 86.
    Regular Polygons

    For an nn-sided polygon,

    Sum of interior angles=180∘(n−2)\text{Sum of interior angles}=180^\circ(n-2)

    Regular Hexagon

    For a regular hexagon with side length aa:

    a)

    ∠A=180∘(6−2)6=120∘\angle A=\frac{180^\circ(6-2)}{6}=120^\circ

    b)

    Regular hexagon divided into six equilateral triangles
    [ABCDEF]=6(a234)=3a232[ABCDEF]=6\left(\frac{a^2\sqrt{3}}{4}\right)=\frac{3a^2\sqrt{3}}{2}

    c)

    Regular hexagon with diagonal AC of length a√3
    AC=a3AC=a\sqrt{3}

    d)

    Regular hexagon with long diagonal AD of length 2a
    AD=2aAD=2a

    Regular Octagon

    For a regular octagon with side length aa:

    a)

    ∠A=180∘(8−2)8=135∘\angle A=\frac{180^\circ(8-2)}{8}=135^\circ

    b)

    Regular octagon inscribed in a square of side a+a√2
    [ABCDEFGH]=(a+a2)2−4(a2/22)[ABCDEFGH]=(a+a\sqrt{2})^2-4\left(\frac{a^2/2}{2}\right)
    =a2+2a2+2a22−a2=2a2(1+2)=a^2+2a^2+2a^2\sqrt{2}-a^2=2a^2(1+\sqrt{2})

    c)

    Regular octagon with diagonal AC and 135° angle at B
    AC=a2+2AC=a\sqrt{2+\sqrt{2}}
    AC2=a2+a2−2a2cos⁡135∘=2a2+2a222AC^2=a^2+a^2-2a^2\cos 135^\circ=2a^2+2a^2\frac{\sqrt{2}}{2}
    =2a2+a22=a2(2+2)=2a^2+a^2\sqrt{2}=a^2(2+\sqrt{2})

    d)

    Regular octagon with diagonal AD of length a(√2+1)
    AD=a2+a=a(2+1)AD=a\sqrt{2}+a=a(\sqrt{2}+1)

    e)

    Regular octagon with diagonal AE and right triangle ADE
    AE=a4+22AE=a\sqrt{4+2\sqrt{2}}
    AE2=a2+AD2=a2+(a(2+1))2AE^2=a^2+AD^2=a^2+\left(a(\sqrt{2}+1)\right)^2
    =a2+a2(3+22)=a2(4+22)=a^2+a^2(3+2\sqrt{2})=a^2(4+2\sqrt{2})