Tl:dr; search “What does the game look like?” on this page. (Leave the “” marks out, they just denote the beginning and end of the string.)
There are an unspecified but finite number of chips on a table. Each chip is one of three colors: white, black or red. Define a “move” to be the act of replacing two chips of different colors with one chip of the third color. Prove that if after some sequence of moves we end up with a single chip on the table, the color of this chip can’t depend on the exact sequence of moves that we made. In other words, if there are two distinct sequences of moves we could make such that in both cases we end up with a single chip left on the table, these chips must be of the same color.
Prove that solvable games have one solution.
Prove that, playing in reverse, one cannot reach the same game (x, y, z) from more than one starting point. (Where starting points are a permutation of (0, 1, 0).)
Assign each game (x, y, z) an end.
Well if it ends in (0, 0, 1), then that means after a series of moves like
(+, -, -)
(-, +, -)
(-, -, +)
each happening some number of times (a, b, c) respectively, it ends in (0, 0, 1).
So
x+a-b-c = 0
y+b-a-c = 0
z+c-a-b = 1
That doesn’t seem like a lot to go off of.
But suppose (x, y, z) is a round game. That is:
a=b=c=n.
Then
x+n-2n=0
y+n-2n=0
z+n-2n=1
Then
x-n=0
y-n=0
z-n=1
More generally, any solvable round game which ends in 1, 2 or 3 (that is (1, 0, 0), (0, 1, 0), (0, 0, 1)), will be of the form
1+n, 2+n, or 3+n (that is (1+n, n, n), (n, 1+n), (n, n, 1+n)).
We have proved the theorem for solvable round games, as no number n exists such that, for example
(1+n, n, n) = (n, 1+n)
Further, a solvable round game has a cycle number of 0, or 3 (they’re the same thing).
Any solvable game with a cycle number of 1 can be reduced to a solvable round game in one move.
Any solvable game with a cycle number of 2 can be reduced to a solvable round game in one move.
One move each (white, then black, then red, not necessarily in that order), will turn a solvable round game into a solvable round game.
Will any (legal) move in a solvable game with a cycle number of c, make it solvable game with a cycle number of (c-1)? Though of course, 0 goes to 2, 2 goes 1, 1 goes to 0? [You could define it that way.* (The legal restriction might not even be necessary.)]
[The stuff in []s was added later. The * was added after that. Then this was added.]
white (you can’t legally illegally play white again after this)
(4, 0, 1) and c = 1
black
(3, 1, 0) and c = 0
black (you can’t legally illegally play black again after this)
(2, 2, −1) and c = 1
red (you can only legally play red at this point, for the rest of the game)
(1, 1, 0) and c = 1
red
(0, 0, 1) and c = 0
.
.
What does the game look like?
On round one (the very end):
(0, 0, 1) or (0, 1, 0) or (1, 0, 0)
On round 2 (the second to last round):
(1, 1, 0) or (1, 0, 1) or (0, 1, 1)
On round 3 (the third to last round):
(There’ll be a 2, a 1, and 0. The 1 will be in the same place as round one.)
Other end states:
Can you put the game in an end state other than a permutation of (0, 0, 1)? Yes, easy as (1, 2, 3), black, white, black. Though (1, 2, 3) is solvable: black, white, white, then there’s only one path left: red, then black.
Solving:
Tl:dr; search “What does the game look like?” on this page. (Leave the “” marks out, they just denote the beginning and end of the string.)
Prove that solvable games have one solution.
Prove that, playing in reverse, one cannot reach the same game (x, y, z) from more than one starting point. (Where starting points are a permutation of (0, 1, 0).)
Assign each game (x, y, z) an end.
Well if it ends in (0, 0, 1), then that means after a series of moves like
(+, -, -)
(-, +, -)
(-, -, +)
each happening some number of times (a, b, c) respectively, it ends in (0, 0, 1).
So
x+a-b-c = 0
y+b-a-c = 0
z+c-a-b = 1
That doesn’t seem like a lot to go off of.
But suppose (x, y, z) is a round game. That is:
a=b=c=n.
Then
x+n-2n=0
y+n-2n=0
z+n-2n=1
Then
x-n=0
y-n=0
z-n=1
More generally, any solvable round game which ends in 1, 2 or 3 (that is (1, 0, 0), (0, 1, 0), (0, 0, 1)), will be of the form
1+n, 2+n, or 3+n (that is (1+n, n, n), (n, 1+n), (n, n, 1+n)).
We have proved the theorem for solvable round games, as no number n exists such that, for example
(1+n, n, n) = (n, 1+n)
Further, a solvable round game has a cycle number of 0, or 3 (they’re the same thing).
Any solvable game with a cycle number of 1 can be reduced to a solvable round game in one move.
Any solvable game with a cycle number of 2 can be reduced to a solvable round game in one move.
One move each (white, then black, then red, not necessarily in that order), will turn a solvable round game into a solvable round game.
Will any (legal) move in a solvable game with a cycle number of c, make it solvable game with a cycle number of (c-1)? Though of course, 0 goes to 2, 2 goes 1, 1 goes to 0? [You could define it that way.* (The legal restriction might not even be necessary.)]
[The stuff in []s was added later. The * was added after that. Then this was added.]
By construction (playing backwards):
(0, 0, 1), (1, 1, 0), (2, 0, 1), (1, 1, 2), (2, 2, 1), (3, 1, 2), (2, 2, 3)
(nada), red, black, white, red, black, white,
Starting there:
(2, 2, 3) and c = 0
white
(3, 1, 2) and c = 2
white
(4, 0, 1) and c = 1
black
(3, 1, 0) and c = 0
red
(2, 0, 1) and c = 2
black
(1, 1, 0) and c = 1
red
(0, 0, 1) and c = 0
And illegal play:
(2, 2, 3) and c = 0
white
(3, 1, 2) and c = 2
white (you can’t legally illegally play white again after this)
(4, 0, 1) and c = 1
black
(3, 1, 0) and c = 0
black (you can’t legally illegally play black again after this)
(2, 2, −1) and c = 1
red (you can only legally play red at this point, for the rest of the game)
(1, 1, 0) and c = 1
red
(0, 0, 1) and c = 0
.
.
What does the game look like?
On round one (the very end):
(0, 0, 1) or (0, 1, 0) or (1, 0, 0)
On round 2 (the second to last round):
(1, 1, 0) or (1, 0, 1) or (0, 1, 1)
On round 3 (the third to last round):
(There’ll be a 2, a 1, and 0. The 1 will be in the same place as round one.)
Other end states:
Can you put the game in an end state other than a permutation of (0, 0, 1)? Yes, easy as (1, 2, 3), black, white, black. Though (1, 2, 3) is solvable: black, white, white, then there’s only one path left: red, then black.
*Or maybe not, see Other end states, above.