Invariant Problem on colored chips 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.
 A: 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 
$$

