Nightmare Ramp II

Nightmare combinatorics problems rarely yield to counting formulas; they yield to finding the RIGHT OBJECT to reason about. The menu, roughly in the order worth trying: an INVARIANT or monovariant (something processes preserve or push one way — parities, sums mod $k$, potential functions); the EXTREMAL configuration (Week 7's method, now applied to exotic structures: consider the largest antichain, the minimal counterexample, the last time something happens); a clever ENCODING (bijection to lattice paths, sequences, or matrices where structure is visible); and the two Week 20 methods when existence-flavored.

Monovariants deserve their own drill: to prove a process terminates or reaches a state, exhibit an integer-valued quantity, bounded below, that strictly decreases with each step (or bounded above and strictly increasing — the value set must be discrete, or the decrease bounded away from zero, for the argument to close). The craft is DESIGNING the quantity — weighted sums with weights chosen to make every legal move decrease it. When a process problem stalls, the productive question is never 'what happens next' but 'what number goes down'.

The write-up trap specific to combinatorics: arguments that are secretly pictures. A proof that says 'clearly we can pair them up' owes the pairing rule; 'continuing this way' owes the induction. The full-write-up gate this week exists because combinatorial hand-waves feel most convincing to their author — write the bijection as a function with a domain, prove it is well-defined and invertible, and the hand-wave either becomes a proof or reveals its gap.

Pitfall. Proposing a monovariant and verifying it on one example instead of against the general move. The quantity must decrease for EVERY legal move from EVERY position — check the algebra, not an instance.

The nightmare-tier linear algebra repertoire, distilled to four moves. TRACE PAIRING: $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ — cyclic invariance kills more hard problems than any other one-line fact (commutator traces vanish, so $AB - BA = I$ is impossible in finite dimensions: take traces). RANK BOOKKEEPING: $\operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B)$ and rank-nullity as counting. SPECTRAL SHIFTING: $p(A)$ has eigenvalues $p(\lambda_i)$; if a polynomial annihilates $A$, every eigenvalue is a root — so equations like $A^2 = A - I$ instantly locate the spectrum. POSITIVITY: $\operatorname{tr}(A^T A) = \sum a_{ij}^2 \ge 0$ with equality iff $A = 0$ — the inner-product structure that turns matrix identities into inequalities.

Matrices ENCODE: adjacency matrices make walk-counting spectral ($(A^k)_{ij}$ counts length-$k$ walks — so trace of $A^k$ counts closed walks, and eigenvalue bounds become combinatorial bounds); circulant matrices diagonalize in the roots-of-unity basis (Week 19's filter, now as a change of basis); Vandermonde determinants prove polynomial independence. When a combinatorics nightmare mentions a process on states, writing its transition matrix is phase-one data gathering in matrix form.

Determinant evaluation at this tier is never cofactor grinding: it is recognizing structure — row operations to triangularity, factoring out Vandermonde, rank-one update formulas ($\det(I + uv^T) = 1 + v^T u$), or evaluating the determinant as a polynomial in a parameter and finding its roots. If a determinant problem seems to require expansion, you have not found its structure yet.

Pitfall. Reaching for entries and indices when an invariant would do. Index computations on nightmare LA problems are almost always a trap; the intended solutions apply trace/rank/spectrum to the STATEMENT, not to the coordinates.

The full-write-up protocol: solved problems from this phase get complete, submission-grade write-ups — stated lemmas, proved claims, closed cases, equality conditions — then sit for a day and get re-read as a hostile grader armed with the Week 17 checklist. Two per week is the dose; the point is calibrating your sense of 'this write-up is a 10' against reality, because miscalibration there is invisible until a real grader shows you, and December has no appeals process.

Structure that graders reward: state the plan in one sentence up front ('We show $f$ is injective, then that injectivity forces linearity'); promote reusable steps to named lemmas with their own proofs; mark case boundaries loudly; end by CONNECTING the last computation to the problem's literal question. Structure that graders punish: proofs that read as a transcript of the discovery process, with dead ends left in and the actual argument assembled implicitly across the page.

The miss-autopsy-plus-repair gate closes the loop: for each mock or archive miss this phase, classify (knowledge gap / recognition gap / execution slip / write-up leak), then DO the repair — the five-problem drill, the technique-card update, the re-solve — within the week. An autopsy without a scheduled repair is a diary entry; the repair is the training.

Pitfall. Leaving the discovery narrative in the write-up. The grader wants the theorem's proof, not the story of finding it — reorder ruthlessly: definitions, lemma, proof, conclusion, even though you discovered them in the opposite order.