Random Envelopes

So, apparently I misread that snake puzzle from last time, the intention was to get to a position where there is only one type of snake, rather than one where there are equal numbers of all snakes. The solution is basically the same, but the "brute force" method of applying AnBmCk is slightly less effective, since you must prove that you cannot reach any of 45-0-0, 0-45-0, 0-0-45, so hitting on the mod 3 solution is more needed.

Anyway, I found a new puzzle on the xkcd forums, I thought it was sort of cool:
Alice and Bob are having a conversation that you are overhearing. Alice has a collection of N envelopes and says to Bob, "for each of these envelopes, it contains either a dollar coin or nothing, I chose to fill the envelopes at random, what is the expected value of the contents of a random envelope?"

Bob responds, "It depends on the method you used to decide to fill the envelopes. You could have flipped a coin for each one, filling it if you got heads and not if you got tails, in that case the expected value of an envelope is $1/2."

Alice decides to tell Bob the method she used to fill the envelopes, she whispers it to him. "I see," Bob replies, "I will purchase a random envelope from you for the expected monetary value, then." Alice agrees, Bob hands her some money and selects an envelope. Bob finds that the envelope does contain a coin and pockets it.

Alice takes the now-empty envelope from Bob and shuffles it back in with the other envelopes. Alice says to Bob, "what is the expected value of a random envelope now?" To which Bob replies, "it is the same as before my purchase."

What is a possible value for N and random method that Alice could have used to make this scenario possible?

When I first read this puzzle, I was certain it was impossible. There is no way that Bob could have taken a coin away and not changed the expected value of a random envelope. However I was missing something. Obviously not something stupid like "Bob can see which envelope he opened earlier because it is now torn" or something like that, that would hardly make an interesting puzzle. There is a well-defined method that Alice can use to make it so that after Bob finds and removes a coin the expected value of a random envelope has not changed.

There are actually many possible solutions, so when I do post the solution next time it will by no means be a complete listing of all possibilities (there are far too many), try to see if you can come up with at least one possible solution though.

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 AnBmCk acting on (13,15,17), you get
AnBmCk(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 AnBmCk 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.

Snakes On An Island

I sort of wanted to work through the solution to the tic-tac-toe variant from last time, but in truth its probably not very interesting to actually do it. Anyway, when I get desperate for new blogging material I might go back to that. For now, I learned a new puzzle from the people in the math room on KGS:
There is an island with snakes on it. The snakes can be either red, green, or blue. If two snakes of different colours meet, they each become the third colour. The snakes never reproduce or die.

Starting with 13 red snakes, 15 green snakes, and 17 blue snakes, is it possible to get to a configuration with equal numbers of snakes of each colour? Find the steps that would need to happen, or prove that it is impossible.

So, you can reformulate this as balls in three jars, and the legal move is to select a jar and move one ball from each of the other two jars into the selected one. Starting from 13-15-17, try to get to 15-15-15.

Cats And Dogs

Hmm... been some time since I blogged, something of a commentary on the complete lack of interesting puzzles I've come across in the past while. A few months ago I was lying in bed thinking about tic-tac-toe and my mind wandered into a bit of a neat game.

When I was young, it was common for a game of tic-tac-toe (which I will start calling TTT, to avoid typing that out everytime) that ended in a tie to be referred to as "cats", and I remember one friend of mine who would occasionally call a tie game "cats" only sometimes and "dogs" at other times. It took me some weeks of playing games with her before I managed to decipher the rule that she used in calling some games "cats" and some "dogs". Basically it came down to if there was a letter "C" in the final position. Consider a game of TTT with X going first (when I was young, O always went first, but I have discovered in my adult life that I am apparently the only person on the planet who thinks that O goes first, so I will submit and use the majority convention here), if the game ends in a tie there will be 5 X's on the board and 4 O's, and those 5 X's can form one of only three possible shapes (they aren't hard to find, and I don't feel like figuring out a good way to draw them). One of those shapes looks like a "C" when oriented correctly, and the draw would be called "cats" if that shape appeared, and the draw was "dogs" otherwise.

Lying in bed, I considered using this "cats" vs "dogs" distinction as a tiebreaker on the game of TTT. Since it is trivial for X to achieve "dogs" by making their first move in the center, it is natural to break ties as "cats" is a win for X and "dogs" is a win for O.

Looking at the possible tie configurations, we can see that "cats" occurs if and only if X controls three of the four side squares, which basically tells us that the game is about controling the side squares. So we can reword the game as "play TTT as normal, X going first, if the game ends in a tie, then whoever controls more of the side squares wins, if that is a tie then O wins." Actually this game is somewhat interesting, sides are the worst places in normal TTT, but this puts an extra emphasis on controlling the sides, so there is some sort of balance. You want to take the sides as soon as possible, but make sure not to let the opponent get an old-fashioned three in a row while you are doing that.

Anyway, I'm going to leave you with that. If you are like me, you will take the time to solve out this game, its only slightly harder than TTT, and its sort of fun. As adults we never get to solve out TTT because we solved it so young, its nice to be able to start over again.

James suggested calling this game "Cats and Dogs," which seems like a smart enough thing to do, so I guess that will be that.