Writing a short but rigorous proof

Question

The problem is

There are $a$ white, $b$ black, and $c$ red chips on a table. In one step, you may choose two chips of different colors and replace them by a chip of the third color. Prove that a state with exactly one chip remaining can be reached if and only if there are two numbers in $\{a,b,c\}$ with equal parity, the other has the opposite parity, and it is not true that there is exactly one nonzero number in $\{a,b,c\}$ and that number is odd.

My proof spans 7 paragraphs:

• 1st paragraph: consider that if all parities equal then such a state is unreachable
• 2nd paragraph: therefore two parities equal and the other differs; the number with different parity is of different parity until the end
• 3rd paragraph: definitions of types of states ("$A$-states", "$B$-states", etc.)
• 4th paragraph: consider that the game ends with all chips of one color
• 5th and 6th paragraphs: proof by contradiction that a position with exactly one chip can be reached
• 7th paragraph: conclusion

My question:

How do I write a proof shorter than that with sufficient rigour?

Answer 1

Well, your argument in paragraphs 3-6 seems considerably more complicated than necessary. I don't know exactly what argument you have in mind, but all you need to do is describe a simple strategy that says what two colors to replace at any given time and explain why that strategy can't cause you to "lose" (i.e., you have no legal moves but still more than one chip). Then, since the total number of chips decreases in each step, you must eventually reach an end state with more than one chip.

To find this strategy, note that the only way to reach a losing state is if you're in a state like $(1,1,n)$ and you remove the $1$ and $1$ to move to $(0,0,n+1)$. So, your strategy is just, don't do that: if two colors have just one chip left, don't choose those two colors, unless the third color is empty so you have no choice (and in that case you win since you'll be left with one chip). (The third color can't also have only one chip by the parity assumption.)

So, just describe this strategy in one sentence, explain how after each move using this strategy there always will be another legal move available unless there's only one chip left in another sentence or two, and conclude that because the number of chips is decreasing each move, it eventually reaches 1. That's a single short paragraph that should be able to replace most of what you have in paragraphs 3-6.

Answer 2

Without seeing your proof it's hard to talk about shortening it. Some of these "paragraphs" are easily packed into a single sentence (e.g. the first and fourth paragraphs).

That said, a (potentially) easier way to go about this is to use induction on the total number of chips, i.e. to show that if the "if and only if" statement is true for $n = 1, 2, \ldots, N$ chips (where $n = a + b + c$), then it must be true for $n = N + 1$ chips as well. To see a very general sketch of how this would work, I'll use the following notation:

• $A_1$: this denotes the statement that "a state with exactly one chip remaining can be reached".
• $A_2$: this denotes the statement "there are two numbers in $\{a,b,c\}$ with equal parity, the other has the opposite parity, and it is not true that there is exactly one nonzero number in $\{a,b,c\}$ and that number is odd.

It's very easy to show that "$A_1$ if and only if $A_2$" is true for $n = 1$.

For the induction step, suppose that $A_1 \Longleftrightarrow A_2$ is also true for $n = 1, 2, \ldots, N$, and now consider the case with $N + 1$ chips. To prove $A_2 \Longrightarrow A_1$, assume $A_2$. Then is there a way of performing the chip replacement operation so that you arrive at a version of the problem that implies $A_1$ from your induction assumption?

To prove $A_1 \Longrightarrow A_2$, for any $N+1$ chips with property $A_1$ we have to be able to perform the chip replacement so that it enters a configuration of $N$ chips with property $A_2$ (why? Look at the inductive assumption.) Now suppose that you "reversed" the chip replacement operation on this configuration. No matter what colors you chose, you should be able to show that the resulting $N + 1$ chips also have property $A_2$.