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
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
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
For the final part, we will show that
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$)