In a course we were once given the following question
There is a finite stack of chips on a table, each chip having one of three different colors $a,b$ and $c$ . At any time, you may choose two chips of different color and replace them by a chip of the third color, reducing the stack. Under which starting-conditions can the stack be reduced to one chip of color $j\in \{a,b,c\}$?
The task is to find the fitting invariant for the problem.
A similar question, but not quiet the same is this one.
We will define an invariant $\Delta$ for a stack of chips, which will essentially contain some information about the different parities of the colors that are present.
Let $S$ be the stack of chips. Then for each color $j \in \{a,b,c\}$ we define $$n_j := \text{number of chips in $S$ having the color $j$}$$ and put everything into a tuple $n := (n_a \mid n_b \mid n_c) \in \mathbb{N}^3$, which fully caracterises the stack. The exchanges of two chips for another chip can now be expressed as operations on $n$ $$ T_j(n) = n' ~~~~~\text{with}~~~~ \begin{cases} n'_k = n_k + 1 &\text{if}~~ k=j \\ n'_k = n_k - 1 &\text{else} \end{cases} $$ so, for example, taking away two chips of color $b$ and $c$ to get one of color $a$ is $$ T_a(n) = ( n_a + 1 \mid n_b - 1 \mid n_c - 1 ) $$ To every $T_j$ we can easily define it's inverse $T_j^{-1}$ which just reverses the exchange and leeds to the previous stack. Given a stack $S$ we can define
$$ \Delta(n) := ( n_a - n_b \mid n_b - n_c \mid n_c - n_a ) \mod 2 $$
Now what happens if we use $T_a$ on $n$ and then calculate the new $\Delta$? \begin{align} \Delta(T_a(n)) &= \Delta ( n_a + 1 \mid n_b - 1 \mid n_c - 1 ) \\ &= ( n_a + 1 - n_b + 1 \mid n_b - 1 - n_c +1 \mid n_c -1 - n_a -1) \\ &= ( n_a - n_b \mid n_b - n_c \mid n_c - n_a ) \mod 2 \\ &= \Delta(n) \end{align} In the same way you can easily check that $\Delta(T_j^k(n)) = \Delta(n)$ holds for all colors $j$ and for all $k \in \mathbb{Z}$. So we have found our invariant for the Problem. For the following, let $\eta_j$ be the vector of the stack containing only one chip of the color $j$. If we start with one chip and use the $T_j^{-1}$ operations to build up a stack $S$, we have
$$ S ~\text{is build up from one chip of color}~j ~\implies \Delta(n) = \Delta(\eta_j) ~\wedge~ S ~\text{contains chips of different colors} $$
because $\Delta$ is invariant, and in every step we get chips of different colors to our stack.
Since we can also imagine to run the process in reverse, we notice that
$$ \text{$S$ can be build up the stack $S_0$} ~\iff~ \text{$S$ can be reduced to the stack $S_0$} $$
For the final part, we will show that
$$ \Delta(n) = \Delta(\eta_j) ~\wedge~ S ~\text{contains chips of different colors} \implies S~ \text{can be reduced to one chip of the color} ~j$$
For the prove we use induction on the number $N>1$ of chips in the stack. For $N=2$ this is trivial.
So let $N>2$. By assumption we have a $j\in \{a,b,c\}$, such that $\Delta(n)=\Delta(\eta_j)$ and we have at least two chips of different color in $S$. Without loss af generality, say $j=a$ .
By assumtion the stack can not contain only chips of one color.
If there are two colors present in the stack, say $a'$ and $b'$ , we can exchange two of them to get a chip of the third color $c'$. We are left with $N-1 \geq 2$ chips, one of them having color $c'$ and another one having either color $a'$ or $b'$ . In either case we are left with at least two chips of different color.
Now consider all three colors being present in the stack. In this case, we apply $T_{c}$ . By assumption we still have $$ \Delta(T_c(n)) = \Delta(n) = \Delta(\eta_a) = ( ~1 \mid 0 \mid -1) \mod 2 $$ Assume this exchange also left us with $N-1$ chips of the color $c$ . Then we would have $$ \Delta(n) = ( ~0 \mid -1 \mid 1) \mod 2 $$ which is a contradiction. Thus we have at least two colors left in the stack.
This shows that in any case, we can use the induction hypothesis which tells us that the $N-1$ stack can be reduced to one chip of color $a$. $~~~\square$
Using everyting that was shown, you get the final result (for $N>1$)
$$ \Delta(n) = \Delta(\eta_j) ~\wedge~ S ~\text{contains chips of different colors} ~\iff S ~\text{can be reduced to one chip of color}~j $$
