This references the end of the post, and the solution.
This definition of f is not quite what we wanted, since it will assign colors to configurations such as (3,0,0) which really have no way of being reduced to a single chip state.
If your solution doesn’t work, make it work.
That color is proved correct, if you can:
play forwards and backwards
Handle negative piles (with IOUs).
For the reverse play through to a solvable state search this page for: “Other end states”.
Negative approach:
(0, 3, 0)
(-1, 2, 1)
(0, 1, 0)
Alternatively, just add extra moves to the game that can be made using a composition of moves even though it moves through a state with negative piles, as long as it moves all positive states (at the start) to positive states (at the end), like:
For your move, remove 2 from a pile of your choice.
This is the part of the claim which says that the color of the final chip should be independent of the sequence of moves we choose to make: it can only be a function of the current state of the game, not of what the players choose to do later on.
So that part was wrong, because unless you allow stuff like inverted moves, the result is dependent on what players choose to do later on.
I was wondering if anyone would pick up on that. Kudos to you!
Here is my explanation of what’s going on here: you’re looking at the different cosets of the submodule of the free module Z3 spanned by the column vectors
A=⎡⎢⎣−1111−1111−1⎤⎥⎦
You can figure out the structure of the quotient systematically by looking at the Smith normal form of this matrix, and you can work that out by taking the greatest common divisor of the determinants of its minors. In this case we get d1d2d3=detA=(4), d1d2=(2) and d1=1, so we can deduce that the Smith normal form is diag(1,2,2) and the quotient is isomorphic to the Klein-four group V4. This explains why a map to V4 is the right invariant for this problem.
This references the end of the post, and the solution.
If your solution doesn’t work, make it work.
That color is proved correct, if you can:
play forwards and backwards
Handle negative piles (with IOUs).
For the reverse play through to a solvable state search this page for: “Other end states”.
Negative approach:
(0, 3, 0)
(-1, 2, 1)
(0, 1, 0)
Alternatively, just add extra moves to the game that can be made using a composition of moves even though it moves through a state with negative piles, as long as it moves all positive states (at the start) to positive states (at the end), like:
For your move, remove 2 from a pile of your choice.
So that part was wrong, because unless you allow stuff like inverted moves, the result is dependent on what players choose to do later on.
I was wondering if anyone would pick up on that. Kudos to you!
Here is my explanation of what’s going on here: you’re looking at the different cosets of the submodule of the free module Z3 spanned by the column vectors
A=⎡⎢⎣−1111−1111−1⎤⎥⎦
You can figure out the structure of the quotient systematically by looking at the Smith normal form of this matrix, and you can work that out by taking the greatest common divisor of the determinants of its minors. In this case we get d1d2d3=detA=(4), d1d2=(2) and d1=1, so we can deduce that the Smith normal form is diag(1,2,2) and the quotient is isomorphic to the Klein-four group V4. This explains why a map to V4 is the right invariant for this problem.