One Way Or The Other

Solution time! Puzzle last time was that game about breaking chocolate.

I know of two ways to come about the solution, the one is easy and elegant (and was how I solved it initially), while the other is a bit more roundabout and uses a bunch of game theory that I think is sort of cool. Anyway, I'm going to do the long game theory version first, if you want to just read the elegant quick solution, skip to the second last paragraph.

First of all, I'm going to set up a bit about game theory of impartial games, games where both players always have the same options available to them (other games are called partizan, chess and go are partizan games with one player playing black and the other white, I cannot move your pawn). I will also be focused exclusively on the type of game where the players alternate turns in the usual way. It is clear that for any impartial game, in any position either the active player has a winning strategy or the inactive player does. As is standard, we will call the former kind of position an "N-position" (for next player wins) and the latter a "P-position" (for previous player wins). It is clear that from any position you always want to move to P-positions, when possible.

At this point will be looking just at games that use the "normal play" rule that is, if you have no moves available on your turn you lose the game (as opposed to the "misère play" rule where having no legal moves is a win). So the game state with no legal moves is a P-position. Generally speaking, if from a game state you can move to a P-position, then that game state must be an N-position (since P-position moves are winning moves, having a P move available means that the active player has a winning strategy). On the other hand, if all the legal moves from a game state are N-positions (including the specific case of no legal moves), then that game state must be a P-position. So if a player has used this to completely map out the game space (first by labeling the end state P then moving outward labeling things P or N) that player will always try to move to a P-position, the opponent will have to choice to move to an N-positon, from which a new move to a P-position is available, and eventually the game must end with the winning player being the one who can move the game into P-positions (the end state also being a P-position).

Next we must figure out how game types combine when you add them together as we do in the breaking chocolate game. Suppose we start the breaking chocolate gmae from a 5x6 position and we move to the 5x2 + 5x4 position, what does that "+" mean? It means that we can make a move in either game. So, if G and H are both games, then G+H is the game where you can legally move in either G or in H, you must move in one of them, but not in both. Convince yourself that this addition is associative, that is (G+H)+J is the same as G+(H+J), it is also commutative but that is trivial.

Now we can prove something, I claim that if G is a P-position and if H is a P-position, then G+H is also a P-position (yay, a theorem), the proof is to simply show the strategy. If G is a P-position, then the inactive player has a response to any move the active player can make, and the inactive player can guarantee that it is the active player will run out of moves first (note how much more difficult it is if we used misère play instead, the fact is normal play is much easier to analyise in most cases). All this is true about H as well, so by simply always responding to the opponents moves in G with moves in G and respond to moves in H with moves in H you can always get to another position of the form P+P. So, we see that:

P+P=P

Good good.

Next, I claim that if G is an N-position and H is a P-position then G+H is an N-position. To prove this I simply need to show that there is a legal move in G+H to a state that is a P-position. We know that there is a legal move in G to a game state K with K being a P-position, but then K+H is a P-position by the previous theorem. So we see that there is a legal move in G+H to a P-position, specifically the move from G to K. So, we have:

N+P=N

Actually, we can quite generally show that if H is a P-position, then for any game G, G+H=G because you can just use your strategy in G and always respond to opponent moves in H with moves in H.

Alright, it is natural to wonder about N+N next, unfortunately you can come up with situations in actual games where N+N can be P and other games where N+N can be N. You can show that any game plus itself is a P-position, because in G+G you can always answer your opponents move in one with the same move in ther other, so they will run out of moves first, so G+G is a P-position, but if G and H are both N-positions, but not the same N-position, you can't prove much.

Alright, now for the chocolate game, I will prove the following statement for some arbitrary AxB position (I would have used NxM, but N is being used for something else here, and that notation is more standard):

AxB is a P-position if both A and B are odd and is an N-position if either A or B is even

The proof will be by induction, we can see this are true if AxB is 1x1, now to prove it by indution suppose we have want to prove this statement for a particular AxB and we are going to assume it is true for all ixB (with i less than A) and all Axj (with j less than B).

Now, I must show that AxB can reach a P-position if either A or B are even, this is easy, just move to (A/2)xB+(A/2)xB or Ax(B/2)+Ax(B/2), whichever exists. Then you mirror the opponent from there and cannot run out of moves first, so AxB can reach a P-position, it must be an N-position. Now if A and B are both odd, a generic legal move is to RxB+SxB with R even and S odd. But then RxB is an N-position and SxB is a P-position by the induction assumption and we know that N+P=N, so any legal move leads to an N-position meaning AxB must have been a P-position.

This completes the proof of the theorem, so we know from any start position if it is a P-position or an N-position so we can clearly say who wins and how (and the typical winning move is to break even sides directly in half), now I will show that that is totally unneeded and if you are in a winning position you can just make random moves and you won't ruin it.

Consider, at the start of the game we have a single block of chocolate on the table (of size NxM), each move causes one break in an existing piece of chocolate, increasing the number of blocks of chocolate on the table by exactly 1. The game ends when there are NxM blocks of chocolate on the table, so exactly NxM-1 moves have gone by, no matter what people chose as their moves there were exactly NxM-1 moves in all cases. The first player wins if NxM is even as there will be an odd number of moves, and the second player wins if NxM is odd as there will be an even number of moves.

Anyway, game theory is cool, but this game is really trivial. The P and N-position things come up alot in other games though, for example the game where you are removing sticks from a pile of N sticks but you cannot remove more than 4 (or K) at a time. You can also be a bit more general and use the Sprague–Grundy theorem to make any impartial game under the normal play condition into nim, but that takes more work (though not much more).

Breaking Chocolate

Alright, new puzzle time. I'm a bit surprised I hadn't posted this puzzle before, as I thought of it many years ago. Anyway, I sort of came up with it myself, but I may have had some influence from Carl Michal. Also, this game appears exactly in Winning Ways For Your Mathematical Plays, so I cannot claim that that book didn't give me inspiration. Anyway, on to the puzzle:

Consider a two player game in which the players take turns breaking up an NxM block of chocolate. On a players turn, they select one existing block of chololate and break it in a straight line along one of its break lines making two smaller blocks of chocolate. The players alternate turns, selecting a single block and breaking it into two smaller blocks. If on a players turn they have no legal moves (because there are only 1x1 blocks left), they lose. Determine the optimal strategy and who will be the winning player from a starting NxM position.

To clarify, a legal move is to select an available NxM block, then select a positive integer k less than N or a positive integer i less and M and turn that NxM block into either a (N-k)xM block plus a kxM block, or into a Nx(M-i) block plus a Nxi block. To give some examples, in the 1x1 case the first player loses (having no legal moves), and in the 1x2 case the first player wins (by making the only legal move).

True And False

I suppose the True or False puzzle from last time has been up long enough, so I should probably get around to the solution. Like I said, my solution will basically be following the derivation that Tanya Khovanova did on her blog, because she did a better job of it than I expect to be able to anyway.

Alright, remember last time I said it is important to solve the simpler case of 5 questions with 4 attempts, so lets assume that we already have the ability to do that (I will show how later) and then use that to solve the problem of 30 questions. Without any loss of generality, we might as well have Victor answer "true" to all the questions first, to establish a base case. Next, we can submit the first 5 as "false" and the other 25 as "true" to get a base case for the first 5 questions (which we can then solve independently in 4 attempts), next we do the next batch of 5 as "false" with the rest "true" to get a base case for the next 5 and solve those in 4 more attempts. When we get to the last batch of 5, we don't need to do a final base case for those ones, as we already had our initial base case to tell us how many true answers are on the test in total, and we knew how many true were in each other block of 5, so we have already found our base for the last 5 questions. This argument shows quite generally that if you can do Q questions in N attempts then you can do MQ questions in MN attempts (for our case Q=5, N=4, M=6).

Now, how do we do 5 questions in 4 attempts? First we spend one attempt on our base case to see how many answers are "true", so we submit TTTTT. For the other 3 attempts, we will switch some of the answers to "false". There is no need to switch 3 of them to "false", as you get the same information by taking the compliment and switching the other 2 of them to "false". Similarly switching 4 or 5 to "false" is also meaningless, so we need only worry about 1 or 2. If we use FTTTT for our second attempt, we will get the answer to the first question and have 2 more attempts to solve out the remaining 4 questions, seems sort of hard (is in fact impossible, but I'm not going to prove that), so for our second attempt we must flip two answers to "false". Thus we can use FFTTT as our second test.

For our third test, we can basically choose between TTFFT ad FTFTT, depending on if we want our third attempt to have any overlap with our second attempt. But TTFFT is the same information as FFTTF which along with our second attempt gives the same information as TTTTF with only one "false" is probably a bad idea. Thus for our third attempt we should use FTFTT. By a similar logic we can use FTTFT for our fourth attempt.

So our exams are TTTTT, FFTTT, FTFTT, FTTFT. The first one give us the number of "true" answers. Adding up the second, third, and fourth mod 2, we can determine the answer to question 5 (as a "true" in one of the first four question contributes 0 mod 2, while a "false" contributes 1 mod 2). Next, going from TTTTT to FFTTT you either gained 2 points, lost 2 points, or stayed the same If you gained or last 2, you know the answers to the first two questions and finishing things off is easy, if you stayed the same then exactly one of the first two questions is true while the other is false. Similarly, TTTTT and FTFTT tells you if questions 1 and 3 are both true or false (easy to solve) or 1 of each. And same for questions 1 and 4. The only hard case is if your score never went up or down, but in that case exactly one of 1 and 2 is true, exactly one of 1 and 3 is true, and exactly one of 1 and 4 is true, thus the only cases are TFFF or FTTT and our base case will distinguish those.

This completes the proof that you can do 30 questions in 24 attempts. Note that this strategy was non-adaptive, in the sense that I never used the information gained from submitting one exam to decide my questions for the next exam. I could have just submitted my 24 exams in any order and then studied them to get my answers. One can in theory make more powerful strategies by using adaptive strategies, by using information you gain along the way to adjust what you are doing, but then the strategy tree is way harder to figure out, because it is theoretically very large.

Bulls And Cows

I suspect that there might be only finitely many logic puzzles in the universe that I find interesting, because they seem to be running out at an alarming rate. Anyway, Tanya Khovanova had an interesting one a few weeks back that I might as well put here:

A test consists of 30 true or false questions. Victor will take the test but starts off having no idea what any answers are. After taking the test, Victor gets his score: the number of correct answers. He is allowed to re-take the same test several times. Can Victor work out a strategy that guarantees that he can figure out all the answers after the 24th attempt?

Note that Victor does not need to get everything right on the 24th attempt, just that he needs to know all the correct answers (so that on a 25th take, he would get them all right).

Naturally one can generalize this puzzle to Q questions and N attempts at the test. This game is actually just mastermind with two colours. One important simpler case is 5 questions, 4 attempts, I say that case is important because you can use it to solve this one of Q=30, N=24.

Tanya actually did a very nice explanation of the answer and some side calculations, when I post my answer I will basically just be copying what she wrote, but I like having an archive of stuff I find interesting, so I want this puzzle to be posted here.

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.

Unfair Auction

Time for the solution to that stupid auction game puzzle from last time.

As with so many puzzles like this, it basically comes down to solving the simpler cases first and moving up. Actually, we will generalize the puzzle a bit, and assume Alice is starting with $N.

Alright, in the "one coin means winning the game" case, it is obvious Bob simply must open the bidding with $N. A bid of any less hands Alice the win, and a bid of any more is unnecessary, so we can see that Bob must start with $N also. We can actually say something a bit stronger, if we are in a position where Alice needs one more coin to win and Bob needs one more coin to win, then Bob wins iff he has at least as much money as Alice has left.

Next the two coin game. There are four positions to consider here, we will first introduce some variables to help the notation. Let A be the number of coins Alice needs in order to win, and let B be the number of coins Bob needs in order to win. Then the positions can be represented as (A,B) being any of (1,1), (1,2), (2,1), (2,2). Obviously if we are in (1,1) then Bob needs the same amount of money as Alice, and if we are in the position (1,2) then Bob needs twice as much money as Alice, as he must bid enough so she can't outbid him, twice. In the position (2,1), Alice will lose if she lets Bob get a coin, so when Bob bids x, Alice must pay x+1, and then Bob must have as much money as Alice left over so he can win. Thus Bobs money-x=Alices money-(x+1), so Bob can have 1 less dollar than Alice in this position, and then he can bid anything he wants and win. Finally, the position (2,2), Bob will have F dollars and Alice will have N dollars. Bob will bid z dollars on the first coin. If he wins, he will have F-z vs N, and we know that he can then win the game if F-z=N-1. If Alice outbids him for z+1, Bob will have F-z dollars and Alice will have N-(z+1), and we know that Bob can win the game if F-z=2(N-(z+1)).

Combining those equations we get F=3/2(N-1), which tells you the amount of money Bob needs to start with.

Alright, we can just keep that pattern going. Define F(A,B,N) as the amount of money Bob needs to win from the position where Alice needs A more coins, Bob needs B more coins, and Alice has N dollars left. Clearly F(1,B,N)=B*N, as Bob must bid N every round, and F(A,1,N)=N-(A-1) as Alice can outbid Bob each of A-1 times losing one dollar on him each time, and then be unable to outbid him the last time. Finally, from some position (A,B,N), Bob has F(A,B,N) dollars, Bob will bid x, and Alice can either let him have it, moving to (A,B-1,N) with Bob having F(A,B,N)-x, or Alice can outbid him, moving to (A-1,B,N-(x+1)), with Bob having F(A,B,N)-x. This means that F(A,B-1,N)=F(A-1,B,N-(x+1))=F(A,B,N)-x.

Looking back at the strategy in the two coin game, Bob needed $3z while Alice had $2z+1 when Bob bid z on the first round. Actually he can bid z on all three rounds and Alice does not have enough money to outbid him twice, so he trivially wins (we also showed it was a minimal win). If one expects this strategy to continue upwards, Bob simply identifies a z such that Alice cannot pay Az+A, so she cannot outbid him A times (Az=N-A+1 will work) and then Bob will need (A+B-1)z dollars to win (so he can pay $z each of the (A+B-1) times a coin is won). Thus, we expect that F(A,B,N)=(N-A+1)(A+B-1)/A is the solution. One can confirm is satisfies our earlier relations, with x=z that we have found.

Actually this has alot of discretization error in it, since Bob cannot bid non-integer values. By our solution we expect that in the case of A=B, the amount of money Bob needs is z(2A-1), with z=(N-A+1)/A, so if N=100 and A=3, say, then z=32+1/3 and Bob needs 161+2/3. If Bob is given $162, it is not enough, he can make bids of $33, $33, $32, $32, $32, and Alice can outbid the three times he bids $32. She could even outbid two $32's and one $33, she cannot outbid two $33's and one $32 though, so Bob needs 32+33+33+33+33 dollars, so Bob needs $164 to win.

Its a bit sad the solution is so boring, Bob has some freedom in how he bids, but the strategy of just "pick a number large enough that Alice cannot afford to outbid it enough times" is basically optimal. Asymptotically, in the case A=B, with N>>A>>1, the solution is that Bob needs 2N dollars and bids N/A each round, Alice being unable to outbid him A times.

Auctioning Coins

Time for a new puzzle. I thought I learned this one on the forums at xkcd, but I was incorrect, what actually happened was that I misread a puzzle that somebody had posted and created my own inadvertent variant. Anyway, here it is:

Bob and Alice are playing an auction game. In a round of the auction a single coin is going to be put up for auction and Bob makes a bid on that coin. Alice can then either outbid him or pass. If Alice outbids Bob, she wins the bid, Bob does not get to bid again (the auction is once-around). Additionally, it is an all-pay auction, any bid you make you must pay, even if you lose the bid. The first person to acquire three coins wins the game.

It is clear that Alice has a large advantage in this game, so Bob gets to start with extra money. Given that Alice starts with $100, what is the minimum amount of money that Bob needs to start with so that he has a winning strategy?

To be clear, only nonnegative integer bids are allowed, no fractions. In a given round, Bob bids $k (and immediately pays it) and Alice gets the choice of either paying $(k+1) for the coin or letting Bob have it. Bob is allowed to bid zero (and will be forced to if he runs out of money), and Alice may then take the coin for $1 (which she will probably do unless she is out of money).

On the forums, the actual puzzle had an infinite number of rounds of bidding, and a player won as soon as they had a three coin lead. That puzzle had a much more complicated answer, but if I am honest the answer to this one is actually sort of boring once you get it, I just found it fun to solve out.

All Drunk

So, whats the solution to running out of interesting puzzles? Stop posting. I guess the other solution is to post non-interesting puzzles, or possibly interesting non-puzzles, but that seems like so much more work than not posting at all. Anyway, I guess one should post the solution to the drinking game puzzle from last time.

First of all, it is obvious that Alice can get a 1/2-1/2 split with Bob if she wants, so the only question is if she can do any better than that. Bob being forced to drink from the bottle at least once is a disadvantage for him, if not for that rule it is clear that the optimal strategy is 1/2-1/2 in general. Since Bob being forced to drink from the bottle is a disadvantage, we can assume he will try to get rid of that, specifically if the bottle ever has less poison than the cup, Bob will immediately drink from the bottle and the remaining bottles will get split 1/2-1/2.

As soon as Bob has drank from the bottle, the remaining bottles get split 1/2-1/2. If we get to the last bottle and Bob has not yet drank from the bottle, Alice will do a 1-0 split, forcing Bob to drink all of the poison in the bottle. Thus, if there are two bottles left, let us assume Alice does an x-y split (x>y and x is the amount in the bottle). If Bob choses x, he will have free choice on the next one and in the end Bob will have drank x+1/2 and Alice will have drank y+1/2. If Bob choses y, Alice will be able to force him to drink all of the last bottle and so Bob will drink y+1 and Alice will drink x. Bob will see this coming and choose whichever one is lower, so Alice does best to make them equal.

We have x+1/2=y+1 and x+y=1, so we get x=3/4 y=1/4, so if there are two bottles left and Bob must still drink from a bottle once, Alice splits 3/4-1/4 and forces Bob to drink 5/4. Obviously if there are two bottles left and Bob does not have to drink from a bottle, then Bob drinks half of each of the remaining bottles for a total of 1.

Now, if there are three bottles left and Bob must drink from the bottle once (the original problem), then Alice splits the first bottle x-y (x>y and x the bottle) and Bob can select either x+1 or y+5/4. Setting those equal and using x+y=1 we get x=5/8 y=3/8. So Alice divides up the first bottle 5/8-3/8 and forces Bob to drink 13/8 in total, whereas Alice only drinks 11/8.

Drinking Game

New puzzle time? It seems like that can only cause disaster when I finally run out of puzzles. My usual sources seem to be drying up, but I guess I have a few left. This one is from the xkcd forums (though, reworded):

Alice and Bob are going to be playing a game where they must drink poison. There are three bottles of poison to be divided among the players and the goal is to drink as little as possible (as some amount of the poison is lethal, but the players do not know how much). The game begins with Alice pouring some amount of the first bottle into a cup, then Bob selects if he would like to drink everything in the cup or everything in the bottle. Whichever one he does not choose Alice must drink. Then Alice pours some of the second bottle into a cup and Bob chooses who will drink from the cup and who will drink from the bottle, finally the third bottle is divided the same way. A special rule is in place however, Bob is not allowed to select from the cup all three times, he must select the bottle at least once. How should Alice divide up the bottles to minimize the amount she must drink?

Poker Time

Guess its time to blog again. The double draw poker problem has been up for ages, and my readership (yes, you) is probably bored of it.

The solution isn't hard to get at, the first thing is to notice that if Bob is able to grab an ace-high straight flush with his first move then the game is over right away (one might call an ace-high straight flush a "royal flush", but I absolutely hate that notation). So we see that Alice must block all four of the ace-high straight flushes right away, perhaps by taking all four aces and some other random card.

If Bob responds to this by taking any straight flush, Alice can get an ace-high straight flush and win (Bob cannot match that hand because he cannot access any of the aces). However, if Bob responds by grabbing all the kings, then Alice cannot do anything. She can get a queen-high straight flush, but Bob can beat that easily. Apparently just grabbing all the aces does not work.

One can try all the kings or whatever, but it is pretty apparent pretty fast that taking all the tens is the solution. After Bobs next move, Alice grabs an ace-high straight flush if she can, or a ten-high straight flush if she cannot. Without any tens, the best Bob can do is a nine-high straight flush.

Pretty simple, I know, but for some reason I like it.

Double Draw Poker

Alright, a bit of an unusual puzzle this time, but I thought it was sort of neat. I first found this on the xkcd forums:

Alice and Bob are going to play a poker variant. A standard 52 card deck is laid out face up in front of them. Alice goes first, and gets to select any 5 cards from the deck. Then Bob gets to select any 5 cards that are still in the deck (not being allowed to select any cards Alice selected). Then Alice may discard any of her cards and replace them with cards still in the deck (discarded cards are removed from the game and do not return to the deck). Then Bob may discard any of his cards and replace them with cards from the deck. At this point, the game ends and whoever has the better poker hand of 5 cards wins. If both players have equal ranked hands, then Bob wins the game (that being the compensation for going second). Who wins this game when played optimally?

If you don't know the rankings of poker hands, you are beyond help. I guess you could look them up, but I actually would say you won't find this puzzle even slightly interesting so don't even bother.

Flip A Coin

About time for the solution to the lowest number game from last time. I tried solving out the harder version myself, but I didn't manage to get anywhere, more about that later.

Before I construct the strategy, I want to point out a somewhat neat theorem about the game and discuss an incorrect strategy. One idea is just to pick 1 with probability 1/2 and 2 with probability 1/2, since this is a zero sum game, every wins zero on average if they all do the same thing. Seems like a reasonable idea, but you can beat this by always picking 3. There is a 50% chance that the other players will pick the same number as eachother and you just win, the rest of the time, they pick different numbers and you lose. Thus your average winnings are 0.5x$2-0.5x$1, which is more than zero. This hints at an interesting idea, there is no number that is the largest number players can pick in a symmetric equilibrium. Suppose each player has a strategy S which is a series of probabilities P(n) for picking number n. Suppose there is a largest number K that S suggest you will ever pick (that is, P(n)=0 for n>K). Now, you generate your random number, and it says you should play K. I say you should play K+1. If K was going to win, so will K+1 (it would only win if the opponents were about to pick the same number). But it is possible K+1 will win and K will not (specifically if both other opponents pick K). Thus it is advantageous for you to change strategy S into a slightly different strategy, and so it is not an equilibrium.

Alright, to find the actual solution, let us assume that we are going to search for a symmetric Nash equilibrium. I think there is a theorem that symmetric games always have at least one symmetric equilibrium, but I cannot find any such theorem online. Anyway, we must find a list of P(n) that is the chance a player picks n, and we know there is no K such that P(n)=0 for n>K (that doesn't actually help us, but I think its neat).

OK, suppose we had P(n), what properties would it have? First of all, no player would do any better by deviating from the strategy. Let us also assume that they will do no worse (so we get equalities instead of inequalities). Second, we know that when everybody plays P(n) they have expected winnings of zero (just by symmetry and it being a zero sum game).

Suppose 2 of the players are playing the strategy suggested by P(n) and the third player decides to write down 1. What are his expected winnings? They are:

2(1-P(1))²-P(1)(1-P(1))-P(1)(1-P(1))

That is, he wins $2 if both opponents do not pick 1, and he loses $1 if one picks 1 while the other does not and this can happen two ways. In other cases he wins nothing and loses nothing. Setting this to zero (player 3 does no worse to unilaterally change his strategy), we see that P(1)=1/2.

What happens if he instead changes his strategy to just write down 2? His expected winnings are now given by

2P(1)²+2(1-P(1)-P(2)²)-2P(1)(1-P(1))-2P(2)(1-P(1)-P(2))

That is, he wins $2 if both opponents pick 1 or if they both pick numbers larger than 2. He loses $1 if one opponent picks 1 and the other does not (can happen in two ways) and he loses $1 if one opponent picks 2 and the other picks larger than 2 (can happen 2 ways). Setting this to zero and solving for P(2) we get P(2)=1/4.

This suggests P(n)=1/2ⁿ is the solution we are looking for. This can be confirmed by looking at what happens if the third player writes down A. His winnings are

2Σ_{n to A-1} P(n)²+2(1-Σ_{n to A}P(n))²-2Σ_{n to A} P(n)(1-Σ_{j to n}P(j))

Σ_{n to A} means sum n from 1 to A. These terms can be explained the same as the A=2 case as before. Subbing in P(n)=1/2ⁿ we find that this equals zero for all A and so this strategy is a Nash equilibrium.

Actually, this strategy is quite easy to perform in real life, you simply flip a coin until it comes up heads and write down the number of flips it took, this gives the correct P(n).

For the case where ties result in everybody losing their dollar, the game is more difficult, since it is no longer zero sum, there is a chance of money exiting the system. You can try something similar where your expected winning each round is the sum of P(n)³ (which is a third of the total amount of money lost each round, on average), but then you cannot iteratively solve for each P(n) as we did, you just have infinitely many coupled equations.

The 4 player game (with friendly ties) also has this problem, since a player playing 1 wins if nobody else picked 1, but also does not lose if the other two players pick the same number, so the sum over P(n)² shows up in your first equation. The 4 player game also has annoying Nash equilibria like two players pick 1 and the other two pick 2.

Anyway, enough about that game.

Lowest Number Game

So, most of the puzzles Mark has been feeding me lately have actually come from a single website, rather than from his crazy new hypothetical officemates. For 'credit where credit is due' purposes, I will direct your attention to Tanya Khovanova’s Math Blog, which still has a few more puzzles on it that I am going to put up here, but that can wait. First, a game that I learned about some time ago, but never knew before that it had such an interesting analysis:

Three people each put $1 on the table. They then each simultaneously write down a positive integer. The integers chosen are then revealed and whoever wrote down the lowest unique one wins the $3. If everybody wrote down the same integer, then they each get their $1 back. Find the equlibrium strategy for this game.

This is a fairly standard game, and some people actually play it with large groups, it works out pretty well. The 3 player game is quite solvable though, and has a fairly cool solution. I suppose you could also change ties to "everybody loses their $1" and see what change it makes, I haven't done that yet. I guess there might be multiple equilibria in the strategy space, so the puzzle is to find any of them.

Notation, Notation, Notation

So Matt always says that the key to all mathematics is good notation, with the solution to the improved blind man puzzle that is certainly the case. I began my solution to this problem by first trying to show that it can't be done, because lets face it, its clearly impossible. In trying to make my proof that its impossible correct I managed to improve my notation to the point where the solution was easy to find. Truthfully, the notation I use in this puzzle is not all that amazing, but it does help to clear out the needless junk that this puzzle carries with it.

So, first thing we need notation for the legal moves that the player can make. There are really only three possible moves. One is to choose two coins that are diagonally opposite and flip them both, we will call this move D (for "diagonal"). The next move is to take two coins that are adjacent to eachother and flip them both, I called this move H (for "horizontal"). The last move is to just flip a single coin, which coin is always irrelevant, because the spinning of the board will always result in you not having any control whatsoever on which coin gets flipped, this move is called S (for "single").

Alright, next we need to consider the possible board positions. I will name a board position with a number that corresponds to the maximum number of coins that have a common side up. So a position with three coins white side up and one coin black side up with be called position 3. A position with two coins on white and two on black will be called position 2. Position 4 is of course the goal. All positions of the name 3 are identical to the player, as white cannot be told from black in any way, and the exact location of the odd coin out can never be determined. The 2 positions do break into two distinct categories though, 2H will denote the position with two white coins that are adjacent to eachother and two black coins also adjacent to eachother. 2D will denote the position with two white coins diagonally opposite and the two black coins diagonally opposite.

Now, consider the effect that the 3 moves {D,H,S} have on the 3 non-winning positions {3,2H,2D}. D and H can only take position 3 to position 3, as D and H flip two coins each and so cannot change if there are an odd number of coins with black (or white) side up. So we will begin only using moves D and H to make sure we are not in any of positions {2D, 2H} and then we will solve the position 3 case after.

Move 1: D

This will have no effect on the board from position 2H (the only thing D can do to 2H is make it another 2H), and if the position was 2D, we now win. Of course, position 3 would be unchanged.

Move 2: H

This still does not change position 3, and it will turn position 2H into either position 4 or position 2D.

Move 3: D

If the board was in position 2D, we have now won. We have now totally ruled out any position 2D or 2H. If we have not won yet we must be in position 3.

Move 4: S

On position 3, S will make it either position 4 or one of positions 2D or 2H (which one is unknown). But now we know for a fact the board is not in position 3.

Moves 5-7: D,H,D

By the same logic as before, this will rule out position 2D, then change 2H into 2D, then lead to position 4.

This completes the solution. As before, I'm pretty convinced this solution is optimal, but I don't see a real proof of it.

Blind And Numb

Alright, so I have recently found a more difficult extension to the blind man puzzle:

There are four coins, each with a black side and a white side. The coins are arranged in a 2x2 pattern on a board. A blind man is going to play a game with these coins, he wins the game if at the end of one of his turns every coin has the same side up.

A turn consists of the man selecting any two coins, and he may then flip either or both of them. Coins may not be moved. After his turn he will be told if he has won. If he has not won yet, the board will be randomly rotated before his next turn.

Find a strategy that guarantees he can win within N turns, for some number N.

Its the exact same puzzle, except that you do not get to learn the status of the two holes that you choose. Of course it requires a few more moves, but its really interesting that you can still solve it.

Blind Man Winning

Time for the solution to the Blind man puzzle. The solution is actually fairly simple to explain, I don't even need pictures or anything. I'll explain it over a few steps.

First move: select two adjacent holes, fill them with pegs.
Second move: select two diagonally opposite holes, fill them with pegs.

Now there are at least 3 holes with pegs in them, as you could not have selected the same two holes twice there. At this point you have either won or the final hole is empty. If you have not won yet,

Third move: select two diagonally opposite holes, if one is empty, fill it and you win. If both are pegged, empty one of them.

Now you know that the board has two pegged holes adjacent to eachother, and two empty holes adjacent to eachother.

Fourth move: select two adjacent holes, if both are filled, empty them. If both are empty, fill them. If one is empty and one is full, switch them

Now you have either won by filling the empty holes or emptying the filled ones, or the board is in a configuration with two pegged holes that are diagonally opposite, and two empty holes that are diagonally opposite. Now you are set to win.

Fifth move: select two diagonally opposite holes, if they are empty fill them, if they are pegged empty them.

Now you win.

This strategy will solve the puzzle for N=5. I would be greatly surprised if there are solutions with less moves, but it is not clear at all the me how to prove it. If anybody out there has a better solution or a proof that there isn't one, feel free to post it in the comments.

Blind Man Walking

Time for a new puzzle I suppose. Though most people who read this blog have already heard this puzzle anyway, so whatever. Anyway, I first learned this puzzle somewhere randomly on the internets:

Consider a square wooden board with four holes drilled in it, arranged in a 2x2 square, with pegs available to fill the holes. A blind man is going to play a game on this board, he wins the game if at the end of one of his turns either every hole has a peg in it or no hole has a peg in it.

A turn consists of the man selecting any two holes, finding out their current status, and he may then change their status to anything he likes. His turn is then over. If he has won, he is now told so, if he has not won, the board will be randomly spun before his next turn.

Find a strategy that guarantees he can win within N turns, for some number N.

The bit about winning in N turns is just to rule out the random strategy, which would work eventually. You need a strategy that is guaranteed to work in a limited number of turns. Also by "randomly spun" I suppose it should be taken for given that the spins will be in multiples of 90 degrees.