Invariant Snakes

Solution time. Puzzle last time was that weird snake puzzle.

First thing, if you played around with it for a bit, you almost certainly noticed that there was no way to get to 15-15-15. This is probably a good thing, given that the puzzle would have been stupid if you could, but sort of awesome if you couldn't. Playing around with it, you probably noticed that there was some sort of parity thing going on, some hidden quantity is conserved, stopping us from getting to 15-15-15.

For a first solution, I'm going to work through what most people probably did (and was posted in the comments). Consider three operators, A, B, and C, which act on three-vectors (x,y,z) such that

A(x,y,z)=(x+2,y-1,z-1)
B(x,y,z)=(x-1,y+2,z-1)
C(x,y,z)=(x-1,y-1,z+2)

These A,B,C aren't quite matrices, because they aren't linear, but whatever, they are operators. They almost form the generators of an abelian group with the relation ABC=I the identity operator. I say almost because there is a bit of an issue, specifically, note that AB(1,0,2)=A(0,2,1)=(2,1,0), but BA(1,0,2)=B(3,-1,1)=(2,1,0). In the first order we applied B then A and it works fine, but in the second order with A the B the number of snakes ran negative. If we allow the numbers of snakes to run negative, then A,B,C do form the generators of an abelian group. If we manage to prove the statement "you cannot reach 15-15-15 even allowing snakes to run negative", then this proves the statement "you cannot reach 15-15-15 being restricted to nonnegative numbers", so lets just allow the snakes to run negative.

Now, consider a general operator AⁿB^mC^k acting on (13,15,17), you get

AⁿB^mC^k(13,15,17)=(13+2n-m-k, 15+2m-n-k, 17+2k-n-m)

setting that equal to (15,15,15) you get

2n-m-k=2
2m-n-k=0
2k-m-n=-2

which can be arranged to get n-k=4/3 which cannot happen.

This is enough to give us the solution to the original problem, but I wasn't happy with this, I wanted to find the invariant hiding in the bushes. Clearly we have one invariant x+y+z (the total number of snakes) and explicitly checking the operators A,B,C from before we see this is conserved. Lets reconsider what happens when we apply AⁿB^mC^k on just (0,0,0) and see what (x,y,z) we can access. We get

x=2n-m-k
y=2m-n-k
z=2k-n-m

from which we can see x-y=3(n-m). Which tells us that x-y is a multiple of three. So if y=2, then x must be -1,2,5,8 or something, it must be 2 mod 3. This suggest that in general (x-y) mod 3 is the invariant (and by symmetry (y-z) mod 3 and (z-x) mod 3). Checking the operators A,B,C explicitly, we can see that in fact all of those operators do preserve (x-y) mod 3.

Actually, since x+y+z is conserved, it is also the case that (x+y+z) mod 3 is conserved, and so if (x-y) mod 3 is conserved then so is (x-y+x+y+z) mod 3, which is (z+2x) mod 3, but 2=-1 mod 3 so this is (z-x) mod 3. Also (x-y-x-y-z) mod 3 must be conserved, and this is (-2y-z) mod 3 and -2=1 mod 3 so this is (y-z) mod 3. We can see there are really only 2 real conserved quantities here, x+y+z and (x-y) mod 3, the others (y-z) mod 3 and (z-x) mod 3 will be guaranteed conserved if those other two are.

Anyway, if we start at 13-15-17, we have x+y+z=45 and (x-y) mod 3 = 1, so we will be able to reach 15-15-15 about as easily as we could reach 11-13-12, we simply cannot do it because it doesn't conserve the two invariants it needs to.