Alice, Bob, and Charles want to evenly distribute a dozen doughnuts. Initially, Alice has 5, Bob has 3, and Charles has 4. However, they want to do it according to the following rules:
1) Bob may give a doughnut to Alice at any time.
2) If Charles has an odd number of doughnuts, then Alice may give a doughnut to Bob.
3) If Charles has an even number of doughnuts, then Charles may give or take a doughnut from either Alice or Bob.
4) If Alice has at least 2 more doughnuts than Bob, then Charles may give or take a doughnut from either Alice or Bob.
i) Is the following an invariant: “(Charles has an odd number of doughnuts) OR (Alice has more doughnuts than Bob)”?
ii) Can the state (4,4,4) ever be reached?
Define the following 6 states:
Use each of the given rules to determine the possible transitions between these states.
For example, first rule: $(A,B,C) \rightarrow (A+1, B-1, C)$ or stay, giving the transitions:
$$1 \rightarrow 1, 1 \rightarrow 2, 2 \rightarrow 3, 6 \rightarrow 6, 6 \rightarrow 5, 5 \rightarrow 4$$
Second rule: C odd (so we are concerned only with states 1, 2, 3) and (A, B, C) -> (A-1, B+1, C)
$$3 \rightarrow 3, 3 \rightarrow 2, 2 \rightarrow 1$$
Complete the transitions. for third and fourth rules.
You'll find that there is no transition to state $6$. Its absence means $(A > B) \lor C \text{ is odd}$ is always true, hence an invariant.
Now, can we reach $(4,4,4)$? Also do you see why we used six states in the answer, not four (say $A\leq B$ and $A > B$ for $C$ even and odd)?