MathGoldMedalist
Sign InRegister

Invariants

Idea · Intermediate

Combinatorics

An invariant is a quantity or property that remains unchanged throughout a process.

Suppose a configuration changes repeatedly:

S0⟶S1⟶S2⟶⋯S_0\longrightarrow S_1\longrightarrow S_2\longrightarrow\cdots

Instead of tracking the entire configuration, we look for a simpler quantity I such that

I(S0)=I(S1)=I(S2)=⋯\boxed{I(S_0)=I(S_1)=I(S_2)=\cdots}

If the initial and target configurations have different values of the invariant, then the target configuration is impossible to reach.

I(initial)≠I(target)⟹target is impossible\boxed{I(\text{initial})\ne I(\text{target})\Longrightarrow\text{target is impossible}}

Finding Invariants by Tracking Changes

A useful way to discover an invariant is to calculate how quantities change after each possible operation.

If I is a quantity being tracked, define

ΔI=Iafter−Ibefore\boxed{\Delta I=I_{\text{after}}-I_{\text{before}}}

and calculate the change in I for every possible type of move.

If

ΔI=0\Delta I=0

for every move, then I itself is invariant.

If instead

ΔI≡0(modm)\Delta I\equiv0\pmod m

for every move, then

I(modm)\boxed{I\pmod m}

is invariant.

Back to Toolkit