Invariants and Constructive Problems

Two advanced skills that no template covers.

Invariants. Find a quantity that every operation preserves. Classic: the XOR of 1..n equals [n, 1, n+1, 0][n mod 4] — an O(1) answer hiding inside a seemingly linear task. Another: when asked to make all values equal by "add k to two different elements each step", the invariant is the set of differences between elements; feasibility becomes a modular condition.

Constructive. You must output any object satisfying the constraints, and the proof is the construction. Example: a permutation of 1..n with no fixed point and no two adjacent values differing by exactly 1. For even n, evens-ascending then odds-ascending works: 2 4 6 1 3 5 — no fixed point, no adjacent pair is consecutive. State WHY the construction works, then encode it. Check n = 1, 2, 3 by hand: small n are where constructions break.