The simplest and most frequently useful invariant.
As an encoding. In hat-guessing puzzles, the first prisoner announces the parity of what they see, which lets everyone else deduce their own colour exactly. One bit, maximally used - see the hat puzzle.
As an impossibility proof. If every move preserves parity and the target has different parity from the start, the target is unreachable. This kills a whole class of "can you get from A to B" questions in one line.
Generalisation: arithmetic modulo k when there are k states rather than two.