I paused after reading the statement of the problem so as to solve the problem myself. Here’s what I came up with.
From experience with other problems (I used to do USAMO), I looked for invariants and suspected that modulo would be involved. I found some relatively quickly.
Let r, w, and b be the number of red, white, and black chips, respectively, in any board state.
The moves we’re allowed to make are of the form “r += 1; w -= 1; b -= 1”, or “r -= 1; w += 1; b -= 1″, or “r -= 1; w -= 1; b += 1”.
If we look at the sums of two colors—for example, r+w—we find that the effects of each move on the sum are “r+w remains the same”, “r+w remains the same”, and “r+w decreases by 2”, respectively.
It follows that, for each sum of two colors, the even-odd parity is preserved by all moves. In other words, “r+w mod 2”, “r+b mod 2″, and “w+b mod 2” are the same before a move and after a move, and indeed their values in the starting state of the game and any possible ending state must be the same.
Therefore, if there is an end state in which there is one chip left… That chip has a color (for example, red). Then the other two colors (in the example, b+w) sum to zero, so their sum is even. If their sum is even in the end state, then that must have been true in the start state, and in any other possible ending state. But, in _any_ state where there is only one chip left, if those two colors sum to an even number, then there must be zero chips of those two colors (since you can’t have negative chips), and so the one chip must be of the first color, which was to be proven.
I paused after reading the statement of the problem so as to solve the problem myself. Here’s what I came up with.
From experience with other problems (I used to do USAMO), I looked for invariants and suspected that modulo would be involved. I found some relatively quickly.
Let r, w, and b be the number of red, white, and black chips, respectively, in any board state.
The moves we’re allowed to make are of the form “r += 1; w -= 1; b -= 1”, or “r -= 1; w += 1; b -= 1″, or “r -= 1; w -= 1; b += 1”.
If we look at the sums of two colors—for example, r+w—we find that the effects of each move on the sum are “r+w remains the same”, “r+w remains the same”, and “r+w decreases by 2”, respectively.
It follows that, for each sum of two colors, the even-odd parity is preserved by all moves. In other words, “r+w mod 2”, “r+b mod 2″, and “w+b mod 2” are the same before a move and after a move, and indeed their values in the starting state of the game and any possible ending state must be the same.
Therefore, if there is an end state in which there is one chip left… That chip has a color (for example, red). Then the other two colors (in the example, b+w) sum to zero, so their sum is even. If their sum is even in the end state, then that must have been true in the start state, and in any other possible ending state. But, in _any_ state where there is only one chip left, if those two colors sum to an even number, then there must be zero chips of those two colors (since you can’t have negative chips), and so the one chip must be of the first color, which was to be proven.