Everything USAMO Tests

Work each one before reading its solution, and time yourself: a problem-1 idea should appear within thirty minutes, and the write-up should fit on one page. If an area feels slow, that is the pillar to study first. The solutions also model the expected write-up: claims stated, every step justified by a named fact, equality cases and edge cases handled.

Step 1 — by AM–GM on three terms, $\dfrac{a^3 + a^3 + b^3}{3} \ge \sqrt[3]{a^6b^3} = a^2b$. Likewise $\dfrac{2b^3 + c^3}{3} \ge b^2c$ and $\dfrac{2c^3 + a^3}{3} \ge c^2a$.

Step 2 — adding, the left sides total $\tfrac{3(a^3 + b^3 + c^3)}{3}$, which gives the claim. Equality needs $a = b$, $b = c$, $c = a$: only $a = b = c$. $\blacksquare$

How to find it. To produce $a^2b$ by AM–GM from cubes, the exponents must average to $(2, 1)$: two copies of $a^3$ and one of $b^3$.

Step 1 — induction on $n$. For $n = 1$: $F_0 = 3 = 5 - 2 = F_1 - 2$. If $F_0\cdots F_{n-1} = F_n - 2 = 2^{2^n} - 1$, then multiplying by $F_n = 2^{2^n} + 1$ gives $\left(2^{2^n}\right)^2 - 1 = 2^{2^{n+1}} - 1 = F_{n+1} - 2$.

Step 2 — if $d$ divides $F_m$ and $F_n$ with $m < n$, then $d$ divides the product $F_0\cdots F_{n-1}$, hence $d \mid F_n - (F_n - 2) = 2$. Fermat numbers are odd, so $d = 1$. $\blacksquare$ Since each $F_n$ has a prime factor and these are all different, there are infinitely many primes.

How to find it. $2^{2^n} - 1$ factors as a difference of squares again and again: $(2^{2^{n-1}} - 1)(2^{2^{n-1}} + 1)$. Unrolling that is the product formula.

Step 1 — draw the chords one at a time. A new chord that crosses $k$ earlier chords (at $k$ distinct interior points) is cut into $k + 1$ arcs, and each arc splits one existing region into two. So it adds $k + 1$ regions.

Step 2 — summing over all chords, the number of regions is $1 + (\text{number of chords}) + (\text{number of crossing points})$.

Step 3 — there are $\binom n2$ chords, and each crossing point is the crossing of the two diagonals of exactly one quadrilateral with vertices among the $n$ points; conversely each $4$ points give exactly one crossing. So there are $\binom n4$ crossing points, and the total is $1 + \binom n2 + \binom n4$. $\blacksquare$ For $n = 5$: $1 + 10 + 5 = 16$.

How to find it. Regions are hard to count directly; how many each new chord creates is easy. Build the figure one piece at a time and count what each piece adds.

Step 1 — $\angle MBC = \angle MAC$, since both are inscribed angles on the arc $MC$.

Step 2 — $\angle MAC = \angle BAM$ because $AM$ bisects angle $A$. So $\angle MBD = \angle MAB$.

Step 3 — triangles $MBD$ and $MAB$ share the angle at $M$ and have $\angle MBD = \angle MAB$, so they are similar: $\dfrac{MB}{MA} = \dfrac{MD}{MB}$, i.e. $MB^2 = MD\cdot MA$. $\blacksquare$ Read as a tangent–secant product, it says that line $MB$ is tangent to the circle through $A$, $B$, $D$.

How to find it. A product of two lengths along one line through $M$ equals a square: look for two similar triangles sharing the vertex $M$. The bisector supplies one equal angle, the circle the other.

The table is not a warm-up; for most “find all” problems it IS the discovery step, because the answer is visible by $n = 6$ or $8$. Writing the cases systematically also exposes the mechanism: the cases that fail tend to fail for the same reason, and that reason is the impossibility proof. The discipline is to treat the guess as unproved until both halves are written — the next section's warning is a pattern that holds for five cases and then fails.

Step 1 — table. $n = 1$: yes. $n = 2$: the permutations $(1, 2)$ and $(2, 1)$ give sums $(2, 4)$ and $(3, 3)$, both repeated mod $2$ — no. $n = 3$: $a_i = i$ gives $2, 4, 6 \equiv 2, 1, 0$ — yes. $n = 4$: a search of the $24$ permutations finds none. Guess: exactly the odd $n$.

Step 2 — odd $n$ work: take $a_i = i$. The sums $2i$ are distinct mod $n$ because $2$ is invertible mod $n$.

Step 3 — even $n$ fail. If the $a_i + i$ were distinct mod $n$, they would be $0, 1, \ldots, n - 1$ in some order, with sum $\tfrac{n(n-1)}{2} \equiv \tfrac n2 \pmod n$ (since $n - 1$ is odd). But $\sum(a_i + i) = 2\cdot\tfrac{n(n+1)}{2} = n(n + 1) \equiv 0$. As $\tfrac n2 \not\equiv 0 \pmod n$, contradiction. $\blacksquare$

How to find it. The table shows odd $n$ work with the identity; for the failures, compute the one quantity every candidate shares — the total sum — both ways.

Step 1 — table: $3 = 1 + 2$, $5 = 2 + 3$, $6 = 1 + 2 + 3$, $7 = 3 + 4$, $9 = 4 + 5$, $10 = 1 + 2 + 3 + 4$, $\ldots$; the failures up to $16$ are $1, 2, 4, 8, 16$. Guess: all except powers of $2$.

Step 2 — a sum of $k \ge 2$ consecutive integers starting at $a \ge 1$ is $n = \tfrac{k(2a + k - 1)}{2}$, so $2n = k(2a + k - 1)$. The two factors differ by $2a - 1$, an odd number, so one is odd, and both exceed $1$ ($k \ge 2$, $2a + k - 1 \ge 3$). So $2n$ has an odd factor greater than $1$, and $n$ is not a power of $2$.

Step 3 — conversely, if $n$ has an odd divisor $x > 1$, write $2n = xy$ with $y = \tfrac{2n}{x}$ even, so $x \ne y$. Put $k = \min(x, y) \ge 2$ and $2a + k - 1 = \max(x, y)$; then $a = \tfrac{\max - \min + 1}{2}$ is a positive integer (the difference of an odd and an even number is odd). So $n$ is such a sum. $\blacksquare$ Example: $n = 12$, $x = 3$, $y = 8$: $k = 3$, $a = 3$, and $3 + 4 + 5 = 12$.

How to find it. The table's failures are $1, 2, 4, 8, 16$ — powers of two announce themselves. Then write the sum in closed form; the factorization $2n = k(2a + k - 1)$ with factors of opposite parity is the whole proof.