Comprehensive Study Notes: The Art of Problem Solving Volume 2 and Beyond

Introduction to The Art of Problem Solving

• Background: For over 24 years, the classic Art of Problem Solving books (Volume 1 and Volume 2) have served as resources for the American Mathematics Competitions (AMC) and other national/local math events.

• Authors: Sandor Lehoczky and Richard Rusczyk.

• Community Stats (as of Sept 2017): Over 295,000 members for the online forum with over 6,000,000 messages posted.

• Instructional Icons:

  • The Eyeball: Indicates especially important areas of the text.

  • The Threaded Needle: Indicates particularly difficult problems or concepts.

  • The Bomb: Signals a warning to facilitate avoiding common mistakes.

Chapter 0: Proof Techniques

• Importance of Proofs: Essential for mathematical understanding; without knowing why a tool works, it cannot be used to its full capacity.

• Common Methods:

  • Contradiction: To prove statement $A$, show that if $A$ were false, an impossible statement must be true.

    • Example: Proving infinitely many primes by assuming a finite set $\{p_1, p_2, ..., p_k\}$ and constructing $Z = p_1 p_2 ... p_k + 1$, which is not divisible by any of the primes.

  • Mathematical Induction: Generally used for statements true for all positive or non-negative integers. Prove for $n=1$, then show that if it holds for $n=k$ (inductive hypothesis), it must hold for $n=k+1$.

    • Example: Proving Fibonacci sum identity $F_0 + F_1 + ... + F_n = F_{n+2} - 1$.

  • Pigeonhole Principle: If $kn+1$ objects are placed in $n$ boxes, at least one box must contain at least $k+1$ objects.

    • Example: Proving that if 5 points are selected in a unit square, some pair are no more than $\frac{\sqrt{2}}{2}$ apart by dividing the square into four quadrants.

Chapter 1: Logarithms

• Purpose: Devised to turn multiplication/division into addition/subtraction.

• Core Relationship: If $10^x = 1234$ and $10^y = 5678$, then $\log(1234 \times 5678) = x + y = \log 1234 + \log 5678$.

• Properties of Logarithms:

  1. $\log_a b^n = n \log_a b$

  2. $\log_a b + \log_a c = \log_a (bc)$

  3. $\log_a b - \log_a c = \log_a (b/c)$

  4. $(\log_a b)(\log_c d) = (\log_a d)(\log_c b)$

  5. $\frac{\log_a b}{\log_a c} = \log_c b$ (Change of Base Form)

  6. $\log_{a^n} b^n = \log_a b$

• Chain Rule for Logarithms: $(\log_a b)(\log_b c) = \log_a c$.

• Warning: The base and argument of all logarithms must be positive. Always check solutions against initial constraints.

• Reciprocal Rule: $\log_w z = \frac{1}{\log_z w}$.

The Big Picture: Logarithms and Music

• Pitch and Vibration: Vibration rate translates to pitch ($cycles/second = Hz$).

• Harmonies: Intervals sound "good" when frequencies are nice multiples (e.g., an octave is a factor of 2; a major fifth is a ratio of $3/2$).

• Even Tempering: Dividing an octave into 12 pieces where each is the same multiple of the last ($2^{1/12}$). This allows a scale to work in any key.

• Calculation: Logarithms determine where a tone (e.g., $1.5F$) sits on the scale using $k = 12 \log_2 1.5$.

Chapter 2: Trigonometry Beyond Right Triangles

• Unit Circle Definition: Sine and cosine are Cartesian coordinates of a point on a circle of radius 1 centered at the origin. $(x, y) = (\cos \theta, \sin \theta)$.

• Quadrants and Signs:

  • Quadrant I: All positive.

  • Quadrant II: Sin positive; Cos/Tan negative.

  • Quadrant III: Tan positive; Sin/Cos negative.

  • Quadrant IV: Cos positive; Sin/Tan negative.

• Identities Defined Historically:

  • $\sin(\alpha \pm \beta) = \sin \alpha \cos \beta \pm \sin \beta \cos \alpha$

  • $\cos(\alpha \pm \beta) = \cos \alpha \cos \beta \mp \sin \alpha \sin \beta$

  • $\tan(\alpha \pm \beta) = \frac{\tan \alpha \pm \tan \beta}{1 \mp \tan \alpha \tan \beta}$

• Graphs:

  • Sinusoid: The wave patterns of Sine and Cosine.

  • Amplitude: Half the difference between the largest and smallest values. Dictated by the coefficient ($A \sin x$).

  • Period: The interval after which the graph repeats ($\frac{2\pi}{k}$ for $\sin kx$).

  • Frequency: Reciprocal of period ($\frac{1}{Period}$).

  • Phase Shift: The horizontal slide of the parent function. For $\sin(ax + b)$, the shift is $-\frac{b}{a}$.

• Inverse Functions: The symbols $\operatorname{Sin}^{-1}$, $\operatorname{Cos}^{-1}$, and $\operatorname{Tan}^{-1}$ refer to principal values.

  • $\operatorname{Sin}^{-1}$ and $\operatorname{Tan}^{-1}$ range: $(-\pi/2, \pi/2]$.

  • $\operatorname{Cos}^{-1}$ range: $[0, \pi]$.

• Even and Odd Functions:

  • $\cos(-x) = \cos x$ (Even)

  • $\sin(-x) = -\sin x$ (Odd)

• Double Angle Formulas:

  • $\sin 2x = 2 \sin x \cos x$

  • $\cos 2x = \cos^2 x - \sin^2 x = 2 \cos^2 x - 1 = 1 - 2 \sin^2 x$

  • $\tan 2x = \frac{2 \tan x}{1 - \tan^2 x}$

• Half Angle Formulas:

  • $\cos \frac{x}{2} = \pm \sqrt{\frac{1 + \cos x}{2}}$

  • $\sin \frac{x}{2} = \pm \sqrt{\frac{1 - \cos x}{2}}$

• Sum-to-Product Formulas:

  • $\cos \alpha + \cos \beta = 2 \cos \frac{\alpha + \beta}{2} \cos \frac{\alpha - \beta}{2}$

  • $\sin \alpha + \sin \beta = 2 \sin \frac{\alpha + \beta}{2} \cos \frac{\alpha - \beta}{2}$

Chapter 3: Advanced Triangle Geometry

• Law of Cosines: For any triangle with sides $a, b, c$, $c^2 = a^2 + b^2 - 2ab \cos C$. Used to find the third side given SAS, or angles given SSS.

• Law of Sines: $\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C} = 2R$, where $R$ is the circumradius.

• Area Formulas:

  1. $\text{Area} = \frac{1}{2} ab \sin C$

  2. $\text{Area} = rs$ (where $r$ is inradius and $s$ is semiperimeter)

  3. Heron's Formula: $\text{Area} = \sqrt{s(s-a)(s-b)(s-c)}$

  4. $\text{Area} = \frac{abc}{4R}$

  5. $\text{Area} = \frac{a^2 \sin B \sin C}{2 \sin A}$

  6. $\text{Area} = 2R^2 \sin A \sin B \sin C$

• Cevians: Segments from a vertex to the opposite side (altitudes, medians, angle bisectors).

• Stewart's Theorem: If cevian $d$ with length $d$ cuts side $a$ into segments $m$ and $n$, then $cnc + bmb = dad + man$.

• Median Length: $4AD^2 = 2(AB^2 + AC^2) - BC^2$.

• Angle Bisector Length: $d^2 = bc (1 - \frac{a^2}{(b+c)^2})$ or $AD^2 = (AB)(AC) - (BD)(CD)$.

Chapter 4: Cyclic Quadrilaterals

• Core Properties:

  1. Opposite angles sum to $180^{\circ}$.

  2. Angles subtended by the same arc are equal ($\angle ABD = \angle ACD$).

• Ptolemy's Theorem: In a cyclic quadrilateral with sides $a, b, c, d$ and diagonals $e, f$, then $ac + bd = ef$.

• Brahmagupta's Formula (Area): For a cyclic quadrilateral, $\text{Area} = \sqrt{(s-a)(s-b)(s-c)(s-d)}$.

  • For general quadrilaterals: $\text{Area}^2 = (s-a)(s-b)(s-c)(s-d) - abcd \cos^2 \frac{B+D}{2}$.

Chapter 5: Conic Sections and Polar Coordinates

• Parabola: Set of points equidistant from a focus $P$ and directrix $l$.

  • Equation: $y-k = \frac{1}{4a}(x-h)^2$.

  • Vertex: $(h, k)$, Focus: $(h, k+a)$, Directrix: $y = k-a$, Latus rectum: $|4a|$.

• Ellipse: Set of points where the sum of distances to two foci is constant ($2a$).

  • Equation: $\frac{(x-h)^2}{a^2} + \frac{(y-k)^2}{b^2} = 1$.

  • Foci relation: $c^2 = a^2 - b^2$. Eccentricity: $e = c/a$. Area: $\pi ab$.

• Hyperbola: Set of points where the absolute difference of distances to two foci is constant.

  • Equation: $\frac{(x-h)^2}{a^2} - \frac{(y-k)^2}{b^2} = 1$.

  • Foci relation: $c^2 = a^2 + b^2$. Asymptotes: $(y-k) = \pm \frac{b}{a}(x-h)$.

• Polar Coordinates: Point $(r, \theta)$.

  • Translations: $x = r \cos \theta$, $y = r \sin \theta$, $x^2 + y^2 = r^2$, $\theta = \operatorname{Tan}^{-1} (y/x)$.

  • Special Curves: Rosa (rose), Lemniscate (infinity symbol), Cardioid (heart), Spiral of Archimedes ($r = a\theta$).

• Rotating Conics: To eliminate the $xy$ term in $Ax^2 + Bxy + Cy^2...$, rotate by angle $\alpha$ where $\cot 2\alpha = \frac{A-C}{B}$.

• Discriminant: $B^2 - 4AC$.

  • If $0$: Parabola.

  • If < 0: Ellipse.

  • If > 0: Hyperbola.

Chapter 6: Polynomials

• General Form: $f(x) = a_n x^n + a_{n-1} x^{n-1} + ... + a_0$.

• Synthetic Division: A shorthand for dividing by $(x-a)$.

• Remainder Theorem: The remainder of $f(x) / (x-a)$ is $f(a)$.

• Fundamental Theorem of Algebra: A degree $n$ polynomial has exactly $n$ roots.

• Rational Root Theorem: For integer coefficients, rational roots are $p/q$ where $p | a_0$ and $q | a_n$.

• Vieta's Formulas (Coefficients and Roots):

  • $\sum r_i = -a_{n-1}/a_n$

  • $\sum r_i r_j = a_{n-2}/a_n$

  • Product $r_1 r_2 ... r_n = (-1)^n a_0/a_n$

• Newton's Sums: Relates sums of powers of roots ($s_k = \sum r^k$) to coefficients:

  • $a_n s_1 + a_{n-1} = 0$

  • $a_n s_2 + a_{n-1} s_1 + 2a_{n-2} = 0$

• Transformations:

  • Roots are reciprocals: Reverse the coefficient order.

  • Roots are $k$ times original: Multiply $a_{n-i}$ by $k^i$.

  • Roots are $k$ more than original: New polynomial is $f(x-k)$.

Chapter 7: Functions

• Inverse Functions ($f^{-1}$): "Undoes" the function. $g(f(x)) = x$. Graphic representation is a reflection over $y=x$.

• One-to-One (1:1): Required for a functional inverse to exist.

• Functional Identities:

  • Logarithm: $f(xy) = f(x) + f(y)$.

  • Cauchy Functional Equation: $f(x+y) = f(x) + f(y) \implies f(x) = cx$.

• Solving Techniques:

  • Isolation: Move variables to different sides to imply a constant value.

  • Substitution: Checking specific values like $y=0, 1$ or $-x$.

  • Cyclic Functions: Using properties like $f(x) = 1/x$ where $f(f(x)) = x$.

Chapter 8: Limits and Continuity

• Definition: $\lim_{n \to \infty} \frac{n}{n+1} = 1$.

• Rational Functions: Divide by the highest power of $x$ to determine behavior at infinity.

• Continuity: $\lim_{x \to a} f(x) = f(a)$.

• Discontinuities:

  • Removable: A "hole" in the function that can be filled by redefining one point.

  • Essential: A gap where the left and right limits do not match (e.g., step function).

• Asymptotes:

  • Horizontal: Behavior as $x \to \pm \infty$.

  • Vertical: Where the denominator is zero (and numerator is not).

  • Slant/Oblique: Occurs when degree of numerator is 1 higher than denominator.

• Important Limits:

  • $\lim_{x \to 0} \frac{\sin x}{x} = 1$

  • $\lim_{x \to 0} \frac{1 - \cos x}{x} = 0$

  • The constant e: $\lim_{n \to \infty} (1+\frac{1}{n})^n = e \approx 2.71828$

Chapter 9: Complex Numbers

• Argand Plane: Plotting $a+bi$ with real part on the x-axis and imaginary part on the y-axis.

• Polar Form: $z = r(\cos \theta + i \sin \theta) = r e^{i\theta}$.

• Magnitude (Modulus): $|z| = \sqrt{a^2 + b^2}$.

  • Properties: $|zw| = |z||w|$; Triangle Inequality $|z+w| \le |z| + |w|$.

• De Moivre's Theorem: $(r e^{i\theta})^n = r^n e^{in\theta} = r^n (\cos n\theta + i \sin n\theta)$.

• Roots of Unity: Roots of $x^n - 1 = 0$. They form a regular $n$-gon on the unit circle in the complex plane. Sum of roots: $1 + w + w^2 + ... + w^{n-1} = 0$.

• Euler's Formula: $e^{iy} = \cos y + i \sin y$.

Chapter 10 & 11: Vectors and Matrices

• Vector Operations: Addition (tail-to-head), Dot Product ($\mathbf{u} \cdot \mathbf{v} = |\mathbf{u}||\mathbf{v}| \cos \theta = x_1x_2 + y_1y_2$), Cross Product ($\mathbf{u} \times \mathbf{v}$ results in a vector perpendicular to both).

• Matrix Multiplication: Row of the first by column of the second.

• Determinant ($\det A$):

  • $2 \times 2$: $ad - bc$.

  • Area/Volume scale factor: Determinant is the factor by which area is multiplied under transformation.

• Inverse Matrix: $A^{-1}$ exists iff $\det A \ne 0$.

  • For $2 \times 2$: $A^{-1} = \frac{1}{ad-bc} \begin{pmatrix} d &amp; -b \\ -c &amp; a \end{pmatrix}$.

Chapter 14: Inequalities

• Trivial Inequality: $x^2 \ge 0$ for all real $x$.

• AM-GM Inequality: $\frac{a_1 + a_2 + ... + a_n}{n} \ge \sqrt[n]{a_1 a_2 ... a_n}$. Equality holds iff all $a_i$ are equal.

• Cauchy-Schwarz Inequality: $(\sum a_i^2)(\sum b_i^2) \ge (\sum a_i b_i)^2$.

• Power Mean Inequality: Root Mean Square ($RMS$) $\ge AM \ge GM \ge$ Harmonic Mean ($HM$).

Chapter 15 & 17: Combinatorics and Counting

• Pascal's Identity: $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$.

• Vandermonde's Identity: $\sum_{k=0}^r \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r}$.

• Binomial Theorem: $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$.

• Principle of Inclusion-Exclusion (PIE): Used to count sets with overlap. For three sets: $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$.

• Generating Functions: Infinite series where coefficients represent counts. Multiplied to find ways to sum to a target value.

Chapter 16: Sequences and Series

• Sum of Squares: $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$.

• Sum of Cubes: $\sum_{i=1}^n i^3 = (\frac{n(n+1)}{2})^2$.

• Fibonacci Closed Form (Binet's Formula): $F_n = \frac{1}{\sqrt{5}} [(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n]$.

• Telescoping Series: Fractions decomposed via partial fractions (e.g., $\frac{1}{n(n+1)} = \frac{1}{n} - \frac{1}{n+1}$) to cancel middle terms.

Chapter 23 & 24: Number Theory

• Fermat's Little Theorem: If $p$ is prime, $a^p \equiv a \pmod{p}$. More commonly $a^{p-1} \equiv 1 \pmod{p}$ if $p \nmid a$.

• Euler's Totient Theorem: $a^{\phi(m)} \equiv 1 \pmod{m}$ for $\gcd(a, m) = 1$.

  • $\phi(m) = m \prod_{p|m} (1 - 1/p)$.

• Wilson's Theorem: $(p-1)! \equiv -1 \pmod{p}$ iff $p$ is prime.

• Pythagorean Triples: Primitive solutions to $x^2 + y^2 = z^2$ are $x = 2rs$, $y = r^2 - s^2$, $z = r^2 + s^2$.

• Pell Equation: $x^2 - Dy^2 = 1$. Linked to continued fractions of $\sqrt{D}$.

Chapter 25: Graph Theory

• Euler's Formula for Planar Graphs: $V - E + F = 2$.

• Edges Inequality: For planar graphs, $E \le 3V - 6$.

• Euler Trail: A trail using all edges. Possible iff graph has 0 or 2 vertices of odd degree.

• Chromatic Number (\chi): Smallest number of colors to color vertices such that no adjacent vertices share a color.

  • For $K_n$, $\chi = n$.

  • Bipartite graphs have $\chi = 2$.