Standard Hat Rules Apply

Bulls And Cows

2012-02-02T12:14:00.000-08:00

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.

Same As Before

2012-01-10T12:11:00.000-08:00

Ok, time to solve out the weighing medals problem from last time.

First, its easy to see that the gold medal will never be on the scale, there is nothing to balance it against, so we might as well throw it away and if we can't find the fake in the others then the fake was the gold medal. Next, note that we can't leave all the silvers off the first weighing, because then they must all go on the second weighing (since the gold is never being weighed, we must weigh everything else at least once or we can't find the fake) and there is no way to divide up the 3 silvers into two piles. Similarly, we must put at least one bronze on the first weighing.

It makes the most sense to weigh 2 bronze and 1 silver against 2 bronze and 1 silver for our first one, this way, if one side is heavy we have immediately identified 2 bronze and 1 silver as the "suspect group". We can use our second measurement to weigh the two suspect bronze against eachother and figure our which of the three medals is the fake.

If our first measurement comes out balanced, we have the gold, 1 bronze, and 1 silver as our suspect group. We put the suspect bronze with a genuine silver on the left against the suspect silver and a genuine bronze. Now 'left heavy' 'right heavy' and 'balanced' all point to a unique medal.

This solves the problem, and as stated isn't very difficult. What I found sort of cool was if you reconsider that solution without the different types of medals. It is just the 9 coins and 2 weighings problem and you start by weighing 3 vs 3 to get a suspect group of size 3. Of course, if the solution to the different medals problem is to work for arbitrary values of masses of genuine medals m_bronze, m_silver, m_gold, then it must work in the particular case where all those m's are equal (I suppose this isn't true if your solution divided by m_bronze-m_silver or something, but we aren't doing that).

Anyway, thats all I got.

Weighing Medals

2011-12-30T13:01:00.000-08:00

Almost a new year already, apparently I didn't do quite as much blogging this year, as I usually get about 40 posts a year and this year I only have about 30. I choose to blame it on my thesis rather than on my general laziness.

Anyway, I found a new puzzle over at Tanya Khovanovas Math Blog that I thought was sort of neat:

There is a collection of medals and one of them is known to be fake. There is 1 gold medal, 3 silver medals, and 5 bronze medals. A fake medal weighs slightly less than the corresponding real medal. All real medals of the same type weigh the same amount, but medals of differing types might not weigh the same amount. Using a balance scale and two weighings, find a strategy that is guaranteed to identify the fake medal.

Standard balance scale rules, of course. The balance scale can be envisioned as having two places to put stuff, and then you push a button and it will tell you either "left side heavy", "right side heavy", or "balanced". The button will only work two times and then the scale will break.

Its actually a pretty simple puzzle if you have done the other balance scale problems, it only took me a few minutes to get it, but I somehow was very satisfied with the answer.

Finding Coins

2011-12-14T16:36:00.000-08:00

Alright, time to finish off the envelope puzzle from last time. This post is going to wind up getting into Bayes' theorem, which has never come up before in my blogging, to my surprise. I suppose I might as well also give a little proof and statment of Bayes' theorem while I'm at it, since its sort of cool.

First though, I want to explicitly demonstrate the solution to the follow-up problem of last time, then I will give a more general derivation using Bayes' theorem. The first thing to remember here, and the general theme of this post actually, is that Bob gained information when he selected a random envelope and found a coin. The explicit two envelope solution of last time served as a good example of this, but it is important enough that I want it stated explicitly. When Bob found a coin in a random envelope, he has to reevaluate his stance on how Alice put coins in envelopes. At first he thought it was 50-50 of zero or two coins, but after finding one, he knew there were two and not zero.

So, I'm going to just give the answer to the follow-up puzzle and then show that it is, in fact, an answer (I will later show that it is 'the' answer). It is for N=4 the scenario is consistent. Before opening an envelope, the cases k=0,1,2,3,4 are all equally likely, and so the expectation of a random envelope is 1/5(0/4)+1/5(1/4)+1/5(2/4)+1/5(3/4)+1/5(4/4)=1/2. A random envelope is worth $1/2, not very surprising. Next, when Bob finds a coin, he knows that k=0 is impossible, and if k had been 1 there would have been only a 1/4 chance of finding a coin, while if k was 4 he was certian, thus it is 4 times more likely that k=4 than k=1. Thus, Bob thinks the values k=0,1,2,3,4 have the relative likleyhoods of 0:1:2:3:4, meaning k=0 has probablity 0, k=1 probablity 1/10, k=2 probability 2/10, k=3 probability 3/10 and k=4 probability 4/10. for a given k, now that a coin has been removed, the expectation value of an envelope is (k-1)/4, so a random envelope now has expectation value 0/4(1/10)+1/4(2/10)+2/4(3/10)+3/4(4/10)=1/2. So we can see N=4 is a solution.

To prove N=4 is the only solution, and to sort of derive it in the first place, we need Bayes' theorem. Suppose we have some an experiment that we are doing, and there are events that can occur, call the events A,B,C... and so on. Now, We can talk about the probabilty of an event A, we call that P(A), and we can talk about the probabilty of an event A given that some other event B has occured, we call that P(A|B). We can of course talk about the probablity that both A and B occur, P(A and B) and such things. It can be seen that the probabilty that both A and B occur is equal to the probabilty that A occurs times the probabilty that B occurs given that A already occured, so we can say:

P(A and B)=P(A)P(B|A)

Of course I could switch A and B in that statement to get:

P(A and B)=P(B)P(A|B)

Giving us that

P(A|B)P(B)=P(B|A)P(A)
P(A|B)=P(B|A)P(A)/P(B)

This last line is the statement of Bayes' Theorem.

So, this theorem can be used to tell us how likely is was that 'Alice put k coins in the envelopes' given that 'Bob found one at random' as long as we can calculate the chance that 'Bob found one at random' given that 'Alice put k coins in the envelopes'. That second one sounds pretty easy to calculate. This is the use of Bayes' theorem, it allows us to switch the order of conditionals which can often make it easier to calculate.

In most practical cases, we have a list of mutually exclusive events A_i and another list of mutually exclusive events B_i such that exactly one A_i and one B_i must occur. Of course, for particular i and j, we can read off Bayes' theorem as:

P(A_i|B_j)=P(B_j|A_i)P(A_i)/P(B_j)

and to find P(B_j) we can find P(B_j|A_k) for each k and then multiply by P(A_k) and sum over k. Essentially we can see that in this case the denominator is serving as a normalizing constant (constant for each choice of j, that is) and that summing both sides of that last equation with resepct to i will give 1 (since exactly one of the A_i must happen).

Now lets try to use Bayes' theorem to solve the follow-up problem. Alice has N envelopes, placed coins in k of them, Bob found a coin. So for our purposes let the event A_i be 'Alice placed coins in exactly i envelopes', and the events B₀ and B₁ are 'Bob didn't find a coin' and 'Bob found a coin', respectively. So we have

P(A_i|B₁)=P(B₁|A_i)P(A_i)/P(B₁)

P(B₁|A_i) is easy, its i/N, and P(A_i) is just 1/(N+1). P(B₁), the chance Bob found a coin, is the numerator summed over i, it is Σ i/(N(N+1)), which is just 1/2. So we have

P(A_i|B₁)=2i/(N(N+1))

Now, what is the expectation value of an envelope given that Bob found and then removed a coin? It is

Σ (i-1)/N 2i/(N(N+1))

Which is the chance of finding one of the remaining i-1 coins time the chance there were i coins (given that Bob found one) summed over i. We can rewrite this as

2/(N²(N+1))Σ (i²-i)

That sum evaluates to N³/3-N/3, so we now have

2(N-1)/3N

as the expectation value of a random envelope given that Bob has found a coin. If we set this to 1/2 we get N=4. Somewhat interesting is that in the limit of large N this tends to 2/3, so which is the statement that Bob pushes his expectation of a random envelope upward quite a bit if he found a coin, when N is large the act of removing one is pretty harmless, he probably won't pick that envelope again anyway.

Alright, that was fun, and in my mind was the end of the puzzle, however, in the comments of the initial post somebody showed me that you can classify all the solutions to the puzzle, so lets do that now (because its actually really cool).

First, note that the list of probabilites P(A_i) completely specifies Alices strategy. Once she has placed coins in the envelopes and shuffles them, the only information that matters is how many envelopes have coins in them. She can use whatever method she wants to place coins, but she might as well just whisper to Bob the list P(A_i), that is the only thing that matters. Alright, so we have already seen that

P(A_i|B₁)=P(B₁|A_i)P(A_i)/P(B₁)

P(B₁|A_i) is still i/N, but now P(A_i) is encapsulating Alices strategy. P(B₁) is still the sum of the numerator, that is

P(B₁)=Σ i/N P(A_i)

Actually, thats the average value of the number of envelopes that Alice put coins in divided by N (sort of obviously), we will call this K/N.

So we have

P(A_i|B₁)=i P(A_i)/K

Alright, after having found a coin, the expectation value of a random envelope is now (i-1)/N times the chance there are i coins, summed over i, so that is

Σ (i-1) i P(A_i)/(K N)

If we want this to be equal to the expectation of an envelope before Bob selected one the first time, we must set this equal to K/N, meaning we now have

K²=Σ (i-1) i P(A_i)
=Σ i² P(A_i) - Σ i P(A_i)

That second term on the right is just K and the first term on the right is the expectation of the number of coins in envelopes, squared. Some rearranging gives us

K=Σ i² P(A_i)-K²

The right side is the expectation of coins squared minus the expectation of coins, squared. This is the standard deviation of Alices strategy squared. So a strategy for Alice is a solution to this puzzle if and only if: the expectation value of the number of coins Alice places in envelopes is equal to the standard deviation squared of the number of coins Alice places in envelopes. Neat.

You can confirm explicitly that the 50-50, 0,2 strategy and the 0,1,2,3,4 strategy both have this feature. Anyway, thats basically it for this.

Half And Half

2011-12-07T12:10:00.000-08:00

So, I wasn't sure if I should put up a complete solution to the envelope puzzle from last time or just post a partial solution and have follow-up questions, but I have since decided on the latter.

Anyway, a solution to the puzzle (which was also given in the comments, but was my "intended easy solution") is: Alice has two envelopes and flips a coin, filling both envelopes with coins on heads and neither of them on tails. With this, the expected value of a random envelope is $1/2. After Bob finds a removes a coin he knows for a fact the other envelope has a coin, so the expected value of an envelope is again $1/2.

Next a follow-up problem:

Suppose instead of Alice whispering her strategy, you overheard her say "I selected an integer k from 0 to N uniformly at random and placed coins in k of the envelopes." What is the value of N so that the scenario is possible?

Its funny how our brains can work, I was again convinced that this was just impossible, even after knowing the earlier answer, but there is a way to solve this. It even has a unique answer.

Random Envelopes

2011-11-30T13:25:00.000-08:00

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 AⁿB^mC^k 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

2011-11-18T13:51:00.000-08:00

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.

Snakes On An Island

2011-11-11T13:40:00.000-08:00

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

2011-11-02T14:37:00.000-07:00

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.

Onto The Nimbers

2011-09-23T15:46:00.000-07:00

Alright, in principle there is where I should post the solution to the puzzle from last time, but first I want to talk about some game theory first, just to give a reason why I found this puzzle sort of neat in spite of the fact that it is quite simple.

Let us consider a two player game, played with piles of coins. On your turn you choose a pile of coins and remove some nonzero number of coins from that pile. The players take turns doing this, and eventually piles run out of coins. If it is your turn and there are no coins left, you lose.

If you know some game theory, you will recognize this game as Nim and you might as well stop reading this post right now, since I'm not going to say anything you don't already know. Anyway, if you haven't seen this game, I encourage you to try it out, its a fun and simple game until you have seen the complete solution, you can probably find some programs online that will play with you (and beat you, because the solution is simple to program).

Before I go through the solution, I want to set up some notation. *x will denote a pile of x coins, and *x+*y will denote a game with two piles of coins with sizes x and y. {a,b,c} will denote a game where the legal move is for a player to move to any of positions a, b, or c, so we can say that *4={*0, *1, *2, *3}, and *2={*0, *1}, of course *0={ }. Lets begin by trying to solve a few simple cases of the game.

The one heap game is trivial, you simply remove all the coins in the heap with your first move and the game is over. The two heap game is fairly simple, suppose that we have a position like *7+*4, then we simply reduce the *7 by three coins to *4. With two heaps of the same number of coins, we simply have to mirror everything our opponent does to win, if he reduces one of the 4 heaps to x, we reduce the other 4 heap to x, eventually our opponent will remove a piles final coin, and we sweep the other pile away to win.

The larger games are harder, but we can solve a few cases right away. For example, if it is our turn from the position *8+*6+*6, we should simply remove the heap of size 8, and mirror our opponent in the two heap game. Or is we are in a position *9+*8+*6+*6, we can simply reduce 9 to 8 and play two mirror games. Actually, we can see that if ever we are in some position with *a+*b+*c+*x+*x, we can ignore the last two heaps, our opponent can find no winning move in those two heaps (we just respond in the other one) and we can find no winning move in those two heaps (our opponent will do the same to us). So, from an optimal strategy point of view, adding *x+*x to any game does not change anything. We can also see that adding *0 to any game does not change anything, so we can see that there is some sense in which

*x+*x=*0

Naturally, in the game with only *0, the active player loses, and in the game with only *x+*x, the active player loses.

Now we are in a position to analyze a slightly more complicated position, *2+*1. What are the legal moves from this position? We can reach any of *2+*0, *1+*1, or *0+*1, which are *2, *0, and *1, respectively, so we can see that *2+*1={*2, *0, *1}, which is *3

*2+*1=*3

Which means that in any game with *a+*b+*c+*2+*1, you can treat this as the same as *a+*b+*c+*3. In particular *3+*2+*1 is a losing position for the first player, as it is the same as *3+*3. It also means that a game like *a+*b+*c+*3+*2+*1 is just the same as the game *a+*b+*c+*3+*3, which we have seen is the same as the game *a+*b+*c.

*3+*2+*1=*0

Actually, one might try to derive this last equation from *2+*1=*3 by adding *3 to both sides and using *3+*3=*0. Sounds reasonable enough, and if it weren't valid then our choosing to use "+" to denote these games would be questionable indeed. Actually, this means that we should also be able to add *1 to *2+*1=*3 to arrive at *2=*3+*1, is this equation valid? Well, from the position *3+*1 we can reach any of *3+*0, *2+*1, *1+*1, *0+*1, so we can see that *3+*1={*3, *3, *0, *1}={*3, *0, *1}. But we know that *2={*0, *1}, so are these things really the same?

Suppose we have a winning strategy in the game G+*2 (where G is any collection of heaps, so G represents something like *a+*b+*c), I claim we can use that as a winning strategy in G+*3+*1. If your winning strategy ever tells you to move in G, then do so. If your winning strategy is to move in *2, it must be to *1 or *0, both of which are accessible in *3+*1, so you can follow your strategy. Our only concern is that our opponent makes use of the move from *3+*1 to *3, but we can immediately revert that to *2 (since *2 is a legal move from *3), and then we can actually continue to follow our strategy.

The conclusion of this is that if you have analyzed a game and found is looks like {*0, *1, *2, *5, *9} or so, you can treat this game as *3. It can access any game that *3 can, and if you opponent moves to one of the larger numbers you can immediately revert it to *3. 3 is said to be the Minimal EXcluded number from the set {0,1,2,5,9}, denoted 3=mex{0,1,2,5,9}.

{*a, *b, *c, ...} = *n, where
n=mex{a,b,c,...}

This gives us {*0, *1, *3}=*2 which validates the equation *3+*1=*2. We can confirm that *3+*2=*1 through a similar method.

This actually gives us a complete solution for the N-pile game, as long as the piles are not larger than size 3, any two piles *x and *y can be replaced by one pile, using one of *x+*x=*0, *1+*2=*3, *1+*3=*2, *2+*3=*1. In the end, there is one pile, and you simply must reduce it to zero, if the one pile is already *0, you are in a losing position and must hope for a mistake.

Next, what do we do if we are in a position with a pile of size 4? Well, lets see what *1+*4 gives us. We can move to any of *0+*4, *1+*3, *1+*2, *1+*1, *1+*0, which means *4+*1={*4, *2, *3, *0, *1}, which is clearly *5. We can find *1+*5 as well, we can move to any of*0+*5, *1+*4, *1+*3, *1+*2, *1+*1, *1+*0, which means *1+*5={*5, *5, *2, *3, *0, *1} which by the mex rule is the same as *4. The mex rule gives us our general answer, actually:

*a+*b=*c, where
*c is the smallest number not of the form *a'+*b or *a+*b'
for any a' less than a and b' less than b

This is enough for us to fill in an entire addition table for nim if we want (these numbers are often called nimbers, just to be whimsical). A partial nimber addition table is

0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0

If you extend this, you'll see it has some nice structure in terms of blocks of powers of two. Actually, you can find a general rule, which I will not prove here:

*2^a+*2^b=*(2^a+2^b)
unless a=b

So, nimber addition for different powers of two is the same as number addition. Of course if a=b then the nim sum is zero. One can also see from the nim addition table that nim addition is associative and commutative, meaning that the nimbers form an abelian group under nim addition with identity *0 and every element is its own inverse. We can use this to do some more complicated nim addition, for example *22+*7+*25 = (*16+*8)+(*4+*2+*1)+(*16+*8+*1) = *16+*16+*8+*8+*4+*2+*1+*1 = *0+*0+*6+*0 = *6. One can extend the nimbers to allow for a multiplication and make it a full blown field (sometimes called On₂), but lets not bother with that.

One might find this addition easier to do in binary, in fact, some people describe nim addition as "convert to binary and add without carrying". This means that Patrick's addition rule from last time is actually just nim addition.

At this point is it fairly natural to solve the puzzle from last time. We can see that *a+*b+*c+...=*x+*y+*z+... if and only if *a+*b+*c+...+*x+*y+*z+...=*0, so we have an immediate check to see if Sean has any split that does not make his brother cry. If he has such a split, any split will work, so he simply gives his brother the smallest candy to keep the most for himself.

Alright, so any time you are in a situation in nim, simply check the nim sum, if it is not zero then there is some move that will make it zero. If it is already zero then you have lost and must either resign or hope for a mistake.

Nim is actually very important in game theory because any two player, perfect information, finite, impartial game with the normal ending condition can be reduced to nim. To clarify those technical terms, finite means that there is no infinite sequence of legal moves anywhere in the game, the normal ending condition is that if you have no legal moves you lose. Finally impartial means that in any position of the game, both players have the same set of legal moves available to them (contrast to something like chess where one player plays white and the other black, chess is not impartial).

As an example of another impartial game, consider the game of Cram. This game is played on a chessboard and on a players turn they place a 2x1 domino on the board to cover two squares. If it is your turn and you have no room to place a domino, you lose. One can reduce this game to nim by considering what moves are available from any given position. For example, if there is only a 1x1 square, this is the same as *0 (no legal moves). A 2x1 or 3x1 box has exactly one move, to *0, so those positions are *1. A 4x1 box or an L-shape can move either to *0 or to *1, so it is *2. You can just sort of explore the entire game like this if you feel like it.

Anyway, I think thats all I got for this. I really find the entire theory fascinating for some bizzare reason, and that puzzle reminded me that I wanted to make a post working out the solution. If you find this sort of game theory interesting, I recommend you look up the series of books by Gardener, Winning Ways For Your Mathematical Plays.

Splitting Candy

2011-09-19T13:13:00.000-07:00

Alright, new puzzle time. This is another one that Bart sent me from CodeJam:

Two brothers, Sean and Patrick, are splitting a bag of candy. The candies come in different sizes, each represented by a positive integer value. Sean, as the older brother, will split the candy into two nonempty piles, and give one to Patrick, keeping the other for himself. Patrick will then examine the two piles and decide if he thinks the split is fair. If he decides the split isn't fair, he will start crying.

Unfortunately, Patrick is very young and bad at adding. He can almost add numbers in binary, but he always forgets to carry the 1. So if he wanted to add 13 (=1101) and 6 (=0110), he will get 1011, which is 11. Some other examples are 3+5=6, 4+10=14, 7+4=3.

Sean is good at adding, and wants to take as much candy as possible while not causing his brother to cry. Given a list of numbers the represent the candy values, is it possible to easily determine if Sean can split the candies in such a way that will not make his brother cry? What is the maximum value of candy that Sean's pile can be?

As an example, if the candies are value 3,4,7, we know that Sean can split them (7, 4) vs (3) and keep 11 total for himself, Patrick will perceive this as fair because he thinks 7+4=3. As another example, if the candies are valued 2,3,4, then there is no splitting that Sean can do that will keep Patrick happy.
The puzzle is sort of neat, and gets into some math that I really like that has a lot of importance in combinatorial game theory. Basically I'm just posting the puzzle so that I can make a game theory post while making it look like a puzzle post.

Flipping Vases

2011-08-23T15:12:00.000-07:00

Alright, back to blogging before I stop blogging for another month or something. Time for the solution to the vases in a line puzzle from last time.

First of all, suppose we have a solution for N vases, then by removing vases M+1 through N, we will have a solution for M vases for any M less than N. Thus, we only need to find solutions in a few particular cases of N, as long as those cases get arbitrarily large it will be good enough (for example, we are going to wind up having a solution that works for N being a power of 2, since any number can be expressed a less than some power of two, you can simply grab that larger solution and remove the extra vases).

For future considerations, it will be slightly easier to subtract 1 from the heights of all the vases, so they are numbered 0 through N-1, rather than 1 through N.

We must arrange things so that no number is between two numbers it is the average of, so x cannot appear between x+a and x-a for any a. Note that the average of two even numbers is even and the average of two odd numbers is odd, and the average of an even number and an odd number is not an integer. This suggests that we place all the even numbers on one side, and all the odd numbers on the other. That way there is no concern of the "left side" and the "right side" having anything dangerous in between them, we can simply treat them independently.

Within the even ones, we can simply half them and solve the N/2 case. With the odd ones, we can subtract 1 from them and then half them and use the N/2 solution. Thus we can see that if we can solve N/2, we can solve N. This is why we will get solutions for powers of two, we simply must start by solving the case N=2 (this is trivial, the solution is (0 1)).

So, if we wanted to solve N=4, we have 0 1 2 3 to place in order, begin with the evens on the left and odds on the right and we get (0 2 1 3) as our solution. For N=8 we being by sorting them to (0 2 4 6 1 3 5 7) next treat 0 2 4 6 as 0 1 2 3 to get (0 4 2 6) and treat 1 3 5 7 as 0 1 2 3 to get (1 5 3 7), so the solution is (0 4 2 6 1 5 3 7).

There is another way to generate this solution, begin by writing out the numbers 0 through N-1 in binary

000
001
010
011
100
101
110
111

Next, reverse the digits

000
100
010
110
001
101
011
111

Next, read them off as they are to get (0 4 2 6 1 5 3 7), which is the same solution.

That first algorithm to get the solution is clean enough, and I was pretty happy to consider it the solution, but the second solution involving binary numbers in reverse is really cool (and I did not come up with it, I saw it on xkcd). Its a bit harder to prove that it always works though, but its not so counterintuitive that its impossible to believe. Naturally, if you want the solution for N that is not a power of two, just solve a larger N that is a power of two and ignore the extra numbers, so for N=5 we have (0 4 2 1 3), which after adding 1 becomes (1 5 3 2 4) which works as a solution.

Vases In A Line

2011-07-23T12:59:00.000-07:00

Blogging is for chumps, I'm on extended vacation (also known as semi-unemployed). Anyway, time for a puzzle that I found on the forums at xkcd:

There is a museum with N vases they wish to arrange on a display. The vases are such that the first one has a height of 1cm, the second one has height of 2cm, and so on such that the N^th one has a height of N centimeters. The people at the museum wish to arrange the vases in a linear display in a special way, such that if we have three vases with heights a,b,c, with b being the average of a and c, b does not appear between a and c.

The puzzle is to come up with an algorithm that will generate an arrangement of numbers 1 through N such that no number appears between two numbers it is the average of.

So, for example if N=5, we could not have 3 appear anywhere between 2 and 4, or anywhere between 1 and 5, 2 could not appear between 1 and 3, and 4 could not appear between 3 and 5. An acceptable answer there would be (1 5 3 2 4).

Arrangements and Derangements

2011-07-05T14:09:00.000-07:00

So, it seems that finishing my thesis has slowed down my blogging. Blogging was done as a way to slack from work, and now I don't really do much work anymore, leaving me with nothing to slack from. Basically, I need to start looking for a job so I can slack off with maximum efficiency.

Alright, time to look at the solution to the sorting puzzle from last time. I guess the solution was given in the comments, which means that I actually have something of a readership I guess (which is a good thing?), anyway, I have no problems with people posting solutions in the comments, but I'm going to do my own solution as usual.

First, lets try to solve it in some simple cases. We already know that the sequence (2 1) takes two moves, how about the sequence (3 1 2). There seems to be no reason to hold any of them in place, and a randomization has an equal chance of going to any of (1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1). The number of steps those are away from the sorted form is 0, 2, 2, k, k, 2, respectively, (knowing that, say, (1 3 2) is two steps away on average) where k is the number of steps (3 1 2) is away. This allows us to say that

k=1/6(0+1)+3/6(2+1)+2/6(k+1)

which can be solved to get k=3. So this solves the N=3 case completely.

For N=4 we have a bit more of a complicated situation, it is clear that anything such as (_ _ _ 4) reduces to the N=3 case, but we have two separate things to solve, one is things of the form (2 3 4 1) where we have everything out of place, and the other is of the form (2 1 4 3) where we have two separate groups. We already know that it is possible to solve (2 1 4 3) in two steps by doing the first two separate from the second two, but it might be better somehow to just ignore that they are two separate cycles and randomize the whole thing. If it is better, then (2 3 4 1) will be less than 4 steps away on average. If it is more than 4 on average, then we should treat cycles separately, and if it is exactly 4 then it does not matter if we isolate cycles.

First, we will treat cycles separately, and let g(n) be the number of moves it takes on average to sort an n-cycle with each element out of place to the right by one (or left if you like). We have seen g(2)=2, g(3)=3 and trivially g(0)=0, g(1) isn't really a thing since you can't have a cycle of 1 with each one being out of place. Anyway, from a 4-cycle we have 24 places we can go, 1 of them is (1 2 3 4), the solution, ₄C₂ of them are 2-cycles (like (2 1 3 4)), ₄C₂/2 of then are two 2-cycles (like (2 1 4 3)), 8 of them are 3-cycles (you can see this by locking one of them down and there are two ways the remaining three are out of place), and the remaining 6 of them are 4-cycles. We can then see that

g(4)=1/24(0+1)+6/24(g(2)+1)+3/24(g(2)+g(2)+1)+8/24(g(3)+1)+6/24(g(4)+1)

which we can solve to get g(4)=4. If we chose the other strategy of just treating two 2-cycles as a 4-cycle, we would replace the term g(2)+g(2) with g(4) instead, and still get the solution g(4)=4, showing that the strategies are the same.

Given that, we might as well only lock down ones that are in the correct place, and not worry about the smaller cycles. Let f(n) be the number of steps it takes to get from a completely unsorted list of n elements to a sorted one ("completely unsorted" means none are in the correct place). Mathematicans have a name for a completely unsorted list, they call it a derangement, and the standard notation for the number of derangements of n elements is !n. A few early ones are !0=1, !1=0, !2=1, !3=2, !4=9. Our earlier strategy for finding f(4) can be expressed as

f(4)=!0/4!(f(0)+1)+!1/4!(f(1)+1)+!2/4!(f(2)+1)+!3/4!(f(3)+1)+!4/4!(f(4)+1)

that is, f(4) is the chance you get k elements in the wrong place, times f(k)+1, summed over k. The chance that exactly k elements are in the wrong place is !k/4!. f(1) isn't really defined, but !1 is zero anyway, I just included that term for completeness.

From this we can deduce the general form

f(N)=&Sigma !k/N!(f(k)+1)

summed k from 0 to N. If we hypothesize that f(k)=k for all k less than N, we can then proceed to prove f(N)=N, though it is rather tedious to do it this way.

The more intuitive way to get f(N)=N was given in the comments, throwing N elements into the air, each one has a 1/N chance of landing in the right spot, and you threw N of them, so on average one of them will land in the right spot. Thus it takes N steps.

Sorting Numbers

2011-06-20T13:03:00.000-07:00

Alright, new puzzle time, Bart showed me this one from the Code Jam this year:

You have a list of the integers 1 through N in some random order, and you are going to attempt to sort them. The only operation you have is to randomize any subset of these integers. Specifically, you may select any subset of the integers and lock them in place, and then the other ones get rearranged randomly. You may perform this operation as many times as you like, but want to do it as few times as possible.

Given the initial list of integers, what is the optimal average number of steps it will take to get the list in order?

The original puzzle had a bit more coding bubble-wrap around it, but not too much. It also had a nicer explanation of why the algorithm is so weird, but whatever.

As a few specific examples, if the initial list is (2 1 3), you can hold the 3 in place and randomize the other two until they fall in place, this will take on average 2 steps. If the initial list is (2 1 4 3) you can hold the first two in place until the second two land in order and then hold the second two in place until the first two land in order. This will take 4 steps on average. Given the initial list, is there an easy way to determine how many steps it will take on average? (Hint: there is, or I wouldn't consider this puzzle interesting).

Cards and Coins

2011-06-07T14:15:00.000-07:00

Alright, time for the solution to the score cards puzzle I put up last time. The comments contained the essentials of the solution, but I still want to type anyway.

First, suppose we had a target number N and a solution to use bases a,b,c,d... That is to say, the product abcd... is at least N with the sum a+b+c+d+... minimized. Suppose the proper solution had a 7 as one of the bases, it is just as good to replace the 7 with a 5 and 2, it makes the sum no larger and in fact makes the product bigger, we can similarly replace 6 with 4 and 2 and even 4 with 2 and 2. In all cases where a is larger than 4 it is better to replace a with a-2 and 2 (this is sort of obvious, but if you wanted to prove it note that 2(a-2) > a can be rearranged into a > 4). Anyway, so a proper solution has no need to contain numbers greater than 3, it should only have 2's and 3's.

Next, note that if a proper solution ever had three 2's, we might as well replace them with two 3's, since the product is larger and the sum the same. So any proper solution need not contain more than two 2's. Thus, we find the algorithm to find the optimal base for a target N. Select k such that 3^k is at least as large as N and 3^k-1 is smaller than N. Compare 3^k-12 and 3^k-22² to N. Whichever of those things is smallest while being larger than N is the expression of the solution.

It is somewhat surprising that base 3 is the optimal solution, most people (myself included) would intuitively think that base 2 is better, but that is just not the case. In some cases base 2 does work fine, our solution does give an optimal solution, but it is not the only one, for example if the target number is 60 then this solution gives us to use 3⁴, however using 2⁶ works just as well. As the numbers get sufficiently large however, base 3 will always win out.

One can "generalize" this problem somewhat by assuming the numbers do not have to be integers. So, we have to select numbers a,b,c,... to minimize their sum and have their product be N. There is nothing to be gained by overshooting N if we are using reals rather than integers, so we might as well hit it exact. Whats more, if two numbers a and b appear in the solution we would do just as well to replace them with a/x and bx with a smaller sum. How do we minimize the sum of a and b while keeping the product equal? This is just minimizing the perimeter of a rectangle, make it a square, set a=b. So we actually should only use a single number a. That is, we want p copies of a such that the sum a+a+a+... is minimized while the product equals N. That is, minimize pa with N=a^p. Minimizing a(Ln(N)/Ln(a)) over a gives us a=e. Giving us that the optimal base is base e. This is sort of why 3 was best, it is the closest integer to e, with 2 also sort of being part of it (I'm not sure how to interpret that, but it feels right).

This also can be taken as a commentary on currency, the optimal base for a currency is base 3 (base e would be better, but then your coins are really weird and making change is hard). Base 3 currency is optimal in the sense of needing the fewest total number of coins to represent a variety of different values. Of course, I doubt we will see a switch to base 3 coinage anytime soon, a single coin of value 3 could probably happen (and probably has, but I know of no real world examples), but coins of value 27 and 81 would be pretty hard to get used to for people who are used to thinking in base 10.

Score Cards

2011-06-01T14:56:00.000-07:00

Alright, time for a new puzzle. Though I meant to post last time that that lemma I used didn't actually need the numbers a_i to be positive reals, it is sufficient to be real. The proof is the exact same even, the only thing that needed to be positive in the proof were the z_i, and positivity is guaranteed by L being the minimum L_i. Anyway, whatever. New puzzle, I first learned from Bart:

There is a school that is using flip cards to keep track of scores in their sporting events. They use a series of cards to represent the ones place of the score, and another series for the tens place and so on for as many places as they feel they need. They want to minimize the number of cards used however, and (being a very mathematically inclined school) they are willing to change from base 10 to another base to accomplish this. For example, if you wanted to represent scores 0-99 in base 10 you would need 20 cards (10 for the ones place and 10 for the hundreds place) however you could do even better by using base 5 and having 3 sets of 5 cards (15 cards total) and be able to represent all the way from 0-124, naturally having the ability to represent extra numbers is not harmful at all, if it uses fewer cards it is better.

Actually, this school is even more mathematically inclined than that, they are even willing to use different bases for each place, for example the first digit could be base 5, the second digit base 5 and the third digit base 4, this uses only 14 cards and can represent 100 different possible numbers.

The puzzle is this: given a target number N, find the minimum number of cards it would take to represent at least the numbers 0 through N-1 on this style of scoreboard.

The solution to this puzzle is somewhat surprising, if you do think you have found a solution, make sure you have checked it out in some medium-sized cases (like numbers 10 through 25) to make sure it works, or better yet have a full proof done that it is actually optimal.

Nonlinear Prisoners

2011-05-24T12:30:00.000-07:00

OK, I just finished my PhD departmental defense, so now its time to look over the solution to the prisoners and light switches puzzle. I wanted to have a post calculating out how long the actual strategy would take for the prisoners to complete, so here we go.

First, we need to figure out how long each procedure will take to perform, starting with the upper bound procedure. The upper bound procedure has k nights of activating people, followed by k nights of deactivating people. If the number of prisoners is N, they will have to run k from 1 to N before the warden is forced to reveal there is an upper bound, this will take N(N+1) nights, and they will have an upper bound B=2^N. The cannot say the upper bound is lower than that, as they do not know what the warden chose to do.

A ping procedure takes B nights to perform, obviously, and the bing procedure takes 1 night. The upper bound procedure is the awful one, for it takes 2^z nights if it is called for on night z.

When the how many times can the warden make them call the upper bound procedure? Well, that depends on how big he can group them up. If he groups the prisoners into very large groups and then splits them off one at a time until they are all in their own groups of size one, the warden will maximize the number of times they perform the group division procedure.

Suppose we have N prisoners. As they run the upper bound procedure, the warden cannot do better than to split them into lg(N) groups. Actually, odds are that if he does this maximally, they will probably find their value of B faster and it will be smaller, but I don't want to do a more complicated calculation than this. So, they have taken on the order of N² nights to find B, the group division procedure than takes like 2^N² nights. Next they do lg(N) pings, costing B lg(N) nights, but that is nothing compared to 2^N². The adversary makes one more group, so they call the group division procedure again and it takes 2^(2^(N²)) more nights.

We can see where this is going, the warden can make them call the group division procedure N-lg(N) times, resulting in the prisoners needing x^N² nights, where x is 2^2^2^2^..., N-lg(N) times, also known as 2 tetrad (N-lg(N)). I tried calculating out that number for something like N=20, but it was huge beyond my comprehension. So then I tried N=5, and again, it was huge beyond my comprehension. Basically, this strategy is stupid.

Linear Prisoners

2011-05-16T13:55:00.000-07:00

Alright, time to do the second half of the solution to the prisoners and light switches problem. In order to explain the solution in full, we first must make use of a lemma (thats right, this solution is so epic that it actually needs a lemma).

First, the statement of the lemma:

Suppose we have a system of unknowns a₁, a₂, ....a_k that obey a series of equations. Let S={a₁, a₂, .... a_k} and suppose the equations have the following properties:
1) a₁=1 is one of the equations
2) For every nonempty, proper subset P of S, there exists a subset Q of S such that there exists an x in Q that is not in P and one of the equations reads "the sum of P" = "the sum of Q"
3) There exists a positive solution to the equations

Then, the solution is unique over the positive numbers.

Alright, lets try to make sense of this lemma before I go proving it. First, we have k unknowns that obey some equations, how many equations exactly? Well, for every nonempty proper subset P of S, there is an equation, and there are 2^k-2 such subsets, also there is a₁=1. In total we have 2^k-1 equations for this system, so it is probably extremely overspecified. The lemma says that if we are so lucky that a solution actually exists, there is not going to be more than one.

As an explicit example, lets suppose we have three unknowns, a, b, c, that obey these equations:

a=1
a=b
b=a
c=a+b
a+b=c
a+c=b+c
b+c=a+c

We can see that it satisfies the conditions of the lemma, for every nonempty proper subset of {a,b,c}, that subset appears summed on the left side of some equation and there is a subset that is summed on that left side such that the right side has at least one element that is not on the left. Clearly one can see that a=1, b=1, c=2 is a solution, and it is fairly obvious that it is unique. In fact, we don't even need to restrict a, b, and c to be positive to get uniqueness, and I think the lemma is true without it, but the proof is very simple with that assumption. Whats more, for our purposes of solving the puzzle, we only need the lemma to be true over the positive integers.

Note that instead of b+c=a+c, we could have had b+c=a instead. Then we would still have satisfied condition 2), but not condition 3), making it so that the lemma gives us nothing useful.

Alright, lets go with the proof now. Suppose we have our system of equations and we have two sets of positive solutions {x₁...x_k} and {y₁...y_k}, we will now prove that x_i and y_i represent the same solutions. Define L_i=x_i/y_i. The set of the L_i is finite so it has a smallest element, call that L. Define z_i=x_i-Ly_i. Since L is smaller than x_i/y_i, it must be the case that z_i is nonnegative, but since L=x_i/y_i for some i, it must be the case that at least one z_i is zero. We also know that the z_i solve the same system of linear equations, being a linear combination of x and y.

Next, I claim that all the z_i are zero. Suppose some of them are not. Let P be the set of z_i=0 and P is not all of {z₁....z_k}, then by 2) there exists a Q such that the sum of P is the sum of Q and Q has an element that is not in P. But the sum of P is zero, and the sum of Q cannot be. This contradiction shows that P is either empty or all of the z_i. Since P is nonempty, we have that z_i=0 and so x_i=Ly_i. Since a₁=1 is one of the equations, it must be the case that all the x's and the y's are equal, completing the proof of the lemma.

Good times.

Now, lets construct the solution to the puzzle.

Recall we had three procedures previously, the "upper bound procedure", to find an upper bound B on the number of prisoners, the "ping", a B round procedure to send out a common knowledge signal to everybody, and the "bing", a one round procedure to send out a signal with the knowledge that the number of signals out equals the number of signals received.

We will need to define one more procedure for this solution, the "group division procedure". If this procedure is called for on night W, each prisoner looks at their history for the past W-1 nights and treats it as a binary number between 1 and 2^W (treat a history of all zeros as 2^W I guess). We have 2^W nights of pinging, where if a prisoners history was i, they ping on the i^th night. This divides people into groups. First, "you" are in group 1, and then the first group of people to ping during the group division procedure are the people in group 2, the next group of people to ping are group 3, the next group is group 4 and so on.

At the end of the group division procedure we have groups G₁ through G_k with G₁ having only "you" in it. The number of groups k is common knowledge and every person knows what group they belong to.

Note that if we call the group division procedure and get k groups, and then later we call it again and get h different groups, it must be the case that h is no smaller than k, people who had different histories at one point cannot later "merge". Whats more, if h=k, each person must be in the same group as they were last time.

The main goal of the strategy is to have every nonempty, proper subset of {G₁....G_k} send out a bing, which will be received by other people in other groups. we then check to see if everybody in the same group received the same signals, if they did we will have a series of equations that we can solve, and the lemma will guarantee the uniqueness of the solution. If it was not the case that everybody in a group received the same bings, then we can use that to make a finer group division. The adversary will have to choose between making finer and finer groups or giving us our series of equations. Eventually the groups will all be size 1, then the adversary will have no choice.

Alright, explicitly the strategy is:

First, perform the upper bound procedure, obtain a common knowledge upper bound B on the number of prisoners.

Next, perform the group division procedure, there are now groups G₁ through G_k and each prisoner belongs to some group and knows what group they belong to. k is also common knowledge.

Next, for each nonempty proper subset P of {G₁....G_k}, send out a bing if you are in a group which belongs to P. There are 2^k-2 such subsets, so there will be that many rounds of bings. Make a note of any bings you receive and the particular set P that it came from.

Next call the group division procedure again, if the number of groups is larger than it used to be, go back to the previous paragraph using the new groups, if the number of groups is the same as before, it must be the case that everybody in a given group has had the exact same history the whole time, even throughout the bing rounds.

Next, for each nonempty proper subset P of {G₁....G_k}, we will have k rounds of pings. Send out a ping on the i^th round if you belong to group G_i and you received a signal from P during the most recent bing round.

Now, for each nonempty proper subset P we know what groups received a signal from that set, meaning that we have an equation that reads "the sum of P" = "the sum of Q" for some known Q. Whats more there must be something in Q not in P, as there cannot be a closed loop that is less than all the prisoners. We know the size of group G₁ is exactly 1, as that group is "you". Finally, a solution to these equations must exist if the prisoners actually performed it. Our lemma guarantees that there is not more than one solution to this set of equations, so we can uniquely solve them to get the size of every single group. Since every prisoner was in some group, we can just add the size of the groups to get N.

This completes the deterministic solution to the puzzle. It is a bit funny that the final value of N is common knowledge to the prisoners, none of the solutions presented made use of the fact that any individual prisoner can declare knowledge of N, it didn't have to be common knowledge. Anyway, I doubt that there is much improving on this solution, because you have such limited communication available and the adversary can really restrict what sort of things you can attempt. Anyway, next time I want to do a post about how long this solution might take to implement. My guess is something like 2 tetrad N, but I haven't calculated it out yet.

Random Prisoners

2011-05-10T13:03:00.000-07:00

Alright, time to do the solution to the latest prisoners and light switches puzzle. I'm not going to post everything about the full solution here, because that would take too long, but I do want to fully examine all the probabilistic solutions.

First of all, it is quite easy to establish an upper bound on the number of prisoners that there are. We will have two types of prisoners, called "active" and "inactive". If you are active, turn your switch on every night, if you are inactive you leave it off. Suppose we selected a number k that all the prisoners knew, and we begin with everybody inactive, but "you" begin active. If the light in your room comes on on a given night, you change your state to active and leave it that way. If we keep doing this for k nights, then at the end of the process there will be somewhere between k+1 and 2^k activated prisoners. After k nights have passed, we can then check if there are any inactive prisoners still by reversing the strategy, make it so that if you see your light off, you turn inactive and stay that way. If there were still any inactive prisoners, then it will take no more than 2^k nights to deactivate everybody.

The procedure is as follows: for each k starting at 1, spend k rounds activating people, followed by 2^k rounds deactivating people. If at the end anybody is inactive, then it must be the case that everybody is inactive and the number of prisoners must be greater than k+1 (else everybody would have been active for sure), and we move on to the next value of k. If at the end of the deactivating process there are no inactive people then the number of people can be no greater than 2^k.

We will call this entire process the "upper bound procedure", it will be used to establish an upper bound B on the number of prisoners. B will always be a power of 2, but that doesn't really matter for what we will do, it is sufficient that B is determined in a well prescribed way and at the end of the process we have determined an upper bound that every prisoner is aware of. Whats more they are all aware that they are all aware of it, and so on, thus making the upper bound "common knowledge" among the prisoners.

Once we have an upper bound on the number of prisoners, we can construct another procedure which I will call a "ping". A ping is a method for prisoners to send out a signal to everybody, such that a signal being sent becomes common knowledge. If the strategy calls for a ping on day M, the procedure lasts for B (=upper bound) days, from M to M+B-1. First, each prisoner decides if they would like to send out a signal or not, if a person would like to send out a signal they are "active", otherwise they are "inactive". As always, turn on your switch if you are active, and off if you are not. If your light comes on, change your state to active. If anybody was active, then by the end of the procedure everybody will be active, if nobody was active at the start then nobody will be active at the end. Thus, if our strategy call for a ping procedure on some specified day M, the prisoners will be able to distinguish "somebody wanted to send out a signal" from "nobody wanted to send out a signal". Note that they cannot distinguish "one person wanted to send a signal" from "two people wanted to send a signal", also note that the existence of a signal being sent becomes common knowledge.

We now have enough structure to set up our first solution. Begin by performing the upper bound procedure to find an upper bound B for use in the ping procedure. Next, have an agreed on number F which depends on B, such that if B independent integers are chosen between 1 and F, it is unlikely that any two of them are the same (I will make the concept of "unlikely" more precise later). Next, each prisoner selects a random integer between 1 and F. Now we call for F rounds of pings. On the i^th round of pinging, send out a signal if your random number is i. After that, count the number of rounds that signals were sent out, guess that that number is the number of prisoners N.

As an example, suppose we determined that the number of prisoners was no greater than 8 (B=8), and we have agreed that in the case B=8, we will use F=100 000 000 (perhaps F=10^B was agreed). You perform the 100 000 000 rounds of pinging, and signals are sent on the following rounds:

18398520
19216152
41001462
53182675
71507596
90195088

Then odds are that there are 6 prisoners. Its possible that there are 7 and two of them generated the same random numbers, but unlikely, it is even possible that there are 8 and there were two duplicates, but very very unlikely.

Given B random integers from 1 to F, what is the chance that two of them are the same? I did that calculation back when I was working out stuff about the birthday paradox, the answer comes out to be approximately B²/F, provided that B² is much smaller than F. So, if you choose F=B²/e, then you fail with probability no more than e (this is approximately true as long as e is small, you might want to choose F=B³/e to be sure).

This completes the strategy that will work with probability 1-e for any e>0. This is also as far as I was able to get in figuring out this puzzle, everything after this was me cheating and reading other peoples answers.

For the next strategy, we will attempt to number the prisoners, and then each round we will check to see if anybody is still unnumbered, and then try to number them. If nobody is unnumbered we will declare success. The prescription will be such that everybody knows their own number and if m people are numbered the number m is common knowledge. It will begin with "you" being number 1 and everybody else being unnumbered. The strategy will gradually assign new numbers to people and will keep the total m common knowledge as we do it.

We will need a new, fairly simple, procedure for this solution (we will also need it for the final solution, so I might as well set it up now), a "bing" is a one night procedure, a person who wants to send out a signal turns on their switch that night, and people who do not want to send out a signal do not. Some other prisoners receive the signals, and some do not. The only thing that is common knowledge here is that the number of signals sent must equal the number of signals received (look, I said it was a simple procedure, but I need a name for it because I will use it alot).

Suppose that so far we have numbered people 1 through m, with m being common knowledge, first we have a ping round, send out a ping if you are unnumbered. If nobody sends out a ping we are done, N=m. If somebody out there is unnumbered we will next do something that will select a group of people S such that every person in S is an unnumbered person, and we will then assign numbers to the people in S.

We perform a bing where if you have a number you send out a signal, and if you are unnumbered you do not. If you received a signal that night and you are unnumbered then you are in S, if you received a signal that night and are numbered just remember it for now, we will need it later. S is necessarily nonempty, because there must have been an unnumbered person next to a numbered person. We must find the size of S and make its size common knowledge. We do this by having m rounds of pings, where on the i^th round, you send out a signal if your number is i and you received a signal during the earlier bing night. This will determine how many "wasted" signals there were during the bing night. If there were no wasted signals then the size of S would equal m, and for each wasted signal then S will be 1 fewer than that. So at this point we have a set S of unnumbered people, each person who is in S knows that they are, and the size of S is common knowledge. We will denote the size of S with s.

Each person in S chooses a random integer between 1 and s, and then we have s rounds of pings. On the i^th round, send out a ping if your random number was i. If there is a round where nobody sends a signal, then it must be the case that two people in S chose the same random number, go back to the start of this paragraph with the same set S. If a ping was sent every round then we are good, it means that each person in S has selected a different number between 1 and s. Each person in S can now claim the number m+i and each person who is numbered has a unique number, so we have now numbered people m+1 through m+s. Go back to the part of the strategy where we asked if anybody was still left unnumbered.

This strategy will always work eventually, a nonempty set S will get chosen and after some number of rounds they will eventually pick unique random numbers that they can use to number themselves with (it will on average take s! rounds to do that). Gradually people will all get numbered, notice this works even if the adversary is aware of what random numbers the random number generators are going to generate, though he might be able to delay it for quite some time in that case.

That is all I am going to post about this for now. Next time I will go over the full deterministic solution.

Crazy Warden

2011-05-04T12:31:00.000-07:00

Alright, so I found a new puzzle on the xkcd forums, and it is just far too epic to not post here:

There are N prisoners and N cells in a prison (though the prisoners do not know the value of N). The cells are all identical from the inside, you cannot tell them apart. The cells are arranged in a circle, and in each cell there is a switch. The switch controls a light in the next cell clockwise around the circle. However, the power supply for these lights is usually off, and it only comes on at midnight each night for a tenth of a second (a tenth of a second not being long enough for a prisoner to see the state of their light and make a decision about their switch).

Each day, the warden will take the prisoners out of their cells and clean out the cells, setting the light switches back to "off". The warden will then place the prisoners back into the cells as he sees fit (the prisoners do not see eachother during this process). At any time, any prisoner may announce "I know how many prisoners there are." If they are then able to state the value of N, the prisoners win and are released, if they are incorrect they lose and all the prisoners are killed.

You are one of the N prisoners. Before the game, you may send out a single email outlining the strategy the prisoners must follow. Your email cannot refer to any prisoner in particular, as you know nothing about their identities. Find a strategy that guarantees the prisoners escape against the warden acting as an adversary.

Man, those wardens are nuts. Anyway, the light switch thing can be equivalently expressed as "every night each prisoner must simultaneously transmit a '0' or a '1' to the next prisoner clockwise from them". Your strategy may contain two types of prisoners, "you" and "everybody else".

The puzzle is pretty hard, I was only able to make a small amount of progress before giving up and just looking at the solution. There are a variety of degrees of solutions one can arrive at, there is a fairly easy strategy that works with probability 1-e for any e>0, and there is a better strategy that works with probability 1. In both of these cases, it is necessary to assume the prisoners have a private random number generator at their disposal to actually generate said probabilities. The full solution, however, is a guaranteed escape, and in fact is guaranteed that for each N there is a K such that "if the number of prisoners is no greater than N, we will escape before K days have passed". Though, K is a really really huge number compared to N.

The Lowest One

2011-05-02T15:36:00.000-07:00

Solution time! Last puzzle was about Infinite Hats. Actually, its funny, I found a solution and then I told it to Mark and he found a slightly different solution that had the exact same probability of working, but then those clever people over at Tanya Khovanova’s Math Blog found a better solution than mine. Anyway, lets go over my solution first, because I'm egotistical like that.

First lets consider the two person case, as soon a one person guesses we are at probability 1/2 of being correct, and we simply need to make sure that both of them are right together or that they are wrong together. Specifically, I want to make sure that if Alice guesses wrong, Bob will also guess wrong (say). In this case, suppose Alice looks at Bobs hats and writes down the smallest number that is a black hat and similarly Bob writes down the lowest number that is a black hat on Alices head. So if Bobs first hat is black, Alice will write down 1 and then if she is wrong Bob will also be wrong.

What is the actual chance of this working? We will calculate this by looking up the hats on their heads slowly, starting at the bottom. If both are black then we lose, if one is white while the other is black, then the person with a white hat is considered correct, and if both are white we move up to the next pair of hats. Let P be the chance that one person is correct, in this case we have

P=0*1/4+1*1/4+1*1/4+P*1/4

that is, 1/4 of the time we get BB and we are wrong, in the cases where we get BW or WB then we are get one person correct, and in the case of WW we haven't really changed anything. One can solve this to get P=2/3.

Now that one person is correct, what is the chance that the other person is correct? Suppose we have already seen WB go by, so person 1 is already correct, now WB and WW both have no effect, and BB results in a loss while BW results in a win. This the odds are 1/2 of the second person being correct. All in all, the probability is 1/3 of winning the game, better than 1/4.

Actually, there is a faster way to arrive at that answer of 1/3. Consider looking at the hats that occur, from the bottom up, you will see a series of things like WW, WB, BW, BB, and then look for the lowest occurrence of each of BW, WB, and BB. If BW and WB each occur before BB, then we win. That is, of those three if the highest is BB then we win, which is clearly 1/3.

Naturally this strategy generalizes to 100 quite easily. Simply look for the lowest occurrence of all black hats by your teammates and write down that number. The relevant sequences are BBB...BBW, BBB...BWB, BBB...BWBB, ...., BWBB...BB, WBB...BBB, and BBB...BBB, of which there are 101. There is a 1/101 chance that the last one is that all black one, and then we win. This generalizes to a strategy that works with probability 1/(N+1).

Marks strategy was slightly different, instead writing down the lowest occurrence of all white hats rather than all black hats (attempting the align when the players are right rather than when they are wrong). The relevant sequences are the all white and all white with one black, again N+1 of them in total. Naturally the game is won if all white occurs before any of the other ones, and that is again 1/(N+1).

The better strategy can be arrived at in a similar fashion to some other hat puzzles, using modular arithmetic. First, let K_i be the location of the lowest white hat on person i's head. Let S be the sum of all the K_i. If each person knew S, they could find the value of K_i. Fix a constant C_N (the constant can depend on N, the number of players). Each person is to make their guess assuming the following two things:

1) S mod C_N = 0
2) each K_i is no larger than C_N

If these statements are actually true, then this is enough for the players to guess correctly. What is the chance that those two statements were actually correct? Well, the largest K_i is going to be about as large as lg(N) (lg being log base 2), so if C_N - lg(N) gets large as N goes to infinity, we should be safe as far as the second point is concerned. As for the first one, it will be on average probability 1/C_N, since S is just a random number, and the two points are approximately independent. For example you could use C_N=2lg(N) and then you have a chance of winning of about 1/2lg(N), maybe a little worse, but this is asymptotically much better than 1/(N+1). One of the posters at Tanya Khovanova's Blog showed that it is basically optimal to use C_N=lg(N)+lg(lg(N))-lg(lg(lg(N))), but thats neither here nor there.

It is interesting that this better solution always attempts to find the location of the lowest white hat on your head, rather than any hat at all, so it seems clear one should be able to do better than this, but it is not clear how much better.

Infinite Hats

2011-04-26T13:19:00.000-07:00

Time for a new puzzle. I found this one on Tanya Khovanova’s Math Blog, as so many of my puzzles are:

There is a room with 100 logicians, and each of them have an infinite number of hats in a tower upon their head. Each hat can be either white or black, and the sequence of hats upon a given logicians head is random. Standard hat rules apply of course.

At a specified time, each logician must simultaneously write down a number. For each logician, the hat of the number they wrote down is checked (so if Bob wrote down 13, we look at the 13^th hat on his head), and if that hat is white, that logician is "correct". If all the logicians are correct, they win, if any of them are incorrect they will play the game again tomorrow with new random hats.

Before the game, they may strategize. The naive strategy gives you a 1/2¹⁰⁰ chance to win, so it will take about 2¹⁰⁰ days to be released, but they do not want to wait that long. Find a strategy that will probably get them out within the year.

Because the hats are random you may use a strategy that only will specify a number with probability one. For example, Bob could look at Alice's hats and look for "the first occurrence of 578 consecutive black hats", which will appear somewhere on her head with probability one.

Unfair Auction

2011-04-21T12:43:00.000-07:00

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

2011-04-15T15:34:00.000-07:00

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.

Pigeonhole'd

2011-04-12T15:40:00.000-07:00

Solution o'clock! Hopefully you have all solved out the balls in boxes problem from last time. Given that you probably have, writing a solution is a totally pointless act, done simply to amuse myself. Here we go.

First of all, lets find some N for which we cannot always win. Specifically, consider that N=1 and there are 1000 balls. Box 999 might have 500 of them and box 1000 has the other 500 of them. In this case we have no legal moves and cannot win. What is the largest N can be so that we still might have no legal moves? To put it another way, when is N big enough to guarantee that we always have a legal move?

The most balls we can have with no legal move is 1 ball in box 2, 2 balls in box 3, 3 balls in box 4,..... k-1 balls in box k. If we have any more balls than that it will be guaranteed that we always have at least one legal move. That number of balls is 1+2+3+4+..+999 = 999*1000/2. So if N is larger than 999/2, so 500 or more, then we always have a legal move. If N is less than 500 we might have no legal moves, thus we may have started in a position with no legal moves.

Now, if N is 500 or larger, we know we always have a legal move, is this enough to guarantee that we can eventually wander our way to a solution? First note that if all the balls were in box 1, we would basically be done, we can move balls from box 1 to any target box simply by moving them 1 at a time. In fact, if we want to move balls from box i to box j, it costs us nothing to move from box i to box 1 then from box 1 to box j, so we might as well only consider moves to and from box 1.

So, assume N is 500 or larger, we have some boxes that have enough balls in them such that we can perform a move. Make all the moves you can from those boxes to box 1, such that when we are done the only legal moves we have left are from box 1. When we are done this box 1 must be nonempty, for if box 1 was empty we would have no moves, and that is impossible for N at least 500. Now, either all the balls are in box 1 or they are not, if all the balls are in box 1 we are done, we can solve the problem as mentioned earlier. If not all the balls are in box 1, there exists some k and x where box k has x balls in it, with k>1, k>x, and x>0. One can see that box 1 has at least k-x balls in it, this is apparent because if it did not I could move all the balls from box 1 into box k and leave myself with no legal moves (which is impossible). So, we can move k-x balls from box 1 into box k, bringing box k up to k balls, and we may then move all the balls from box k to box 1. We repeat this process for each nonempty box k with k>1. In the end all the balls are in box 1 and the game is trivially won.

I'm not sure why I liked this problem so much, I guess I was just pleasantly surprised to see something so simple on a Putnam. I cannot say that their questions lack creativity, but this particular problem is just the kind of creativity I like.

Balls In Boxes

2011-04-05T16:02:00.000-07:00

New puzzle o'clock! I should probably be working instead of blogging, but blogging is so much more fun. Anyway, I found something of a neat puzzle on the Putnam 2010 exam. Usually those exams are just filled with semi-impossible math problems involving stupid functions, but there was one question on that exam I thought was pretty cool as a puzzle:

There are 1000 boxes, labelled 1 through 1000. There are 1000*N balls in the boxes, distributed randomly between the boxes. You will be playing a 1 player game, trying to average out the balls in the boxes, so that each box has exactly N balls in it.

The only legal move in the game is to select a number K and move exactly K balls from box K into any other box. So you could go to box 247 and move exactly 247 balls from that box into any other box. If box 247 has fewer than 247 balls in it, you cannot do this, so you don't get to move any of them. You are allowed to keep making legal moves as long as you like, and you win if every box has exactly N balls in it.

Given that in total there are 1000*N balls in the 1000 boxes, for what values of N is it always possible to win, regardless of the initial configuration of the balls?

Naturally, the fundamental nature of the solution is not particularly sensitive to the number 1000, in the actual Putnam they used 2010, cause thats how they roll.

Correlated Hats

2011-03-31T14:06:00.001-07:00

Well, my thesis is essentially done, now its just time for the eternal editing of the damn thing (also, its only like 65 pages, somehow I had hoped for more). Anyway, time to post the solution the the hat problem from last time.

For the first part of the puzzle, consider that the logicians have some sort of strategy, which must be based on the hats of their fellow logicians and possibly some constant which varies for each individual logician and possibly some random variable. You get into the room ("you" being one of the logicians) and you check your strategy, and it says to say that your hat was white. OK, great, but since your strategy is independent of your own hat colour, your hat colour could randomize as we do this and your answer won't change. Thus you are 50% to be correct, no matter what. This is true for each and every logician. This means that no strategy can save more than 50% on average. In fact, no strategy can save less than 50% either. All strategies have an expectation value of saving 50 of the logicians.

You might think that is weird, since in so many other hat puzzles it has been that case that the logicians pull off something amazing with no information about their own hat colours. If you check carefully though, in all of those, when they were going to guess they were 50% chance to be correct, the most they ever pulled off was correlation with the other logicians being right.

Alright, now, is there a strategy that guarantees saving 50? Note that if the logicians knew if the total number of white hats was even, they could always guess their own hat, and similarly if they knew the total number of white hats was odd. So, the strategy is to have half of the logicians assume the total number of white hats is even, the other half assume that it is odd. Exactly one of those two groups will be right, and you will save 50 of them.

Finally, a strategy that saves all or none of them. This is simple given the last paragraph, simply have everybody assume the total number of white hats is even (or odd, if you prefer). They will either all be correct or all be wrong, with 50-50 chance.

Friendly Hats

2011-03-27T15:18:00.001-07:00

Been some time since I have done an actual hat puzzle. There was one recently on Tanya Khovanova’s Math Blog that I had assumed I had done before, since it was so basic. Interestingly enough, I have never actually done this one, so I might as well put it up now:

There is a room of 100 logicians wearing hats. Each hat can be either black or white, and standard hat rules apply. The logicians must simultaneously guess what colour hat they have. Every logician who guesses right is released and every one that guesses wrong is killed.

Before the hats are assigned, they logicians may get together and plan. What strategy maximizes the number of logicians you can save on average?

Thats simple enough, there are a few follow up questions that Tanya also added though:

Suppose the maximum you can save on average is N, is there a strategy that guarantees that you will save N of them?

and,

Suppose the logicians are close friends, and they do not want to see their friends die, they would rather die with them. Is there a strategy that guarantees that they will all live together or die together?

Fairly simple if you have been following all the other hat posts, most of the basic results you need to solve this out have been proven somewhere or another on this blog.

Going In Circles

2011-03-18T15:44:00.000-07:00

Alright, some time ago I promised to do more on the dots on a line puzzle, so I guess I'll do that now.

On the puzzle page over at cut-the-knot, they had a few writeups of possible ways to arrive at the solution. They varied in their degree of rigour, but they certainly were all more elegant than my method. One in particular led me to examine a few other things about the puzzle (that I honestly do not understand the implications of), and I will go over them here.

This solution was put forward by Stuart Anderson, and it beings by assuming that the dots do not necessarily follow a uniform distribution. Suppose x is the length of an interval between adjacent points, and let f(x)dx be the probability that a particular interval has length between x and x+dx. F(x) will be the cumulative probability distribution, so F'(x)=f(x) and F(x) ranges from 0 to 1, as x ranges from 0 to 1.

We will call an interval "small" if it is smaller than both its neighbours, "large" if it is larger than both its neighbours, and "medium" otherwise. Intervals that are small get painted twice, and medium ones get painted once, while large ones are unpainted. Lets try to find out how many of each region we have and how large each type is. Suppose we have an interval with size x, that occurs with chance f(x)dx, and its left hand neighbour will be smaller than it with chance F(x) (F(x) being the cumulative distribution function, it is the integral of f(y) from 0 to x). Similarly, the right hand neighbour will be smaller with chance F(x), so the total chance that we have a large region is

&int F(x) F(x) f(x) dx
=&int F(x)² dF

Where we have used f(x)=F'(x). The limits of integration are 0 to 1, since that is what F ranges over. Thus we get 1/3 for the chance an interval is large. A similar calculation shows that you also get 1/3 for small and medium intervals. This means that if an interval is selected at random, it is equally likely to be small, medium, or large, and this is independent of the probability distribution that the points are selected with.

The fact that P(small)=P(large) is somewhat obvious if you consider doing a plot of interval lengths. Small intervals will be a local minimum of the plot, while large intervals will be local maxima. For any two local minima, there must be a local maxima in between and vice-versa, so the number of small intervals must be the same as the number of large intervals (well, within 1 anyway), so in the infinite limit they will have the same probability. It is not clear why medium intervals would be equally likely, but there is probably some underlying reason.

Moving on, the expected length of a large interval is given by

&int x F(x) F(x) f(x) dx

which we can integrate by parts. Let u=x and v=F(x)³-1, so then we have

x(F(x)³-1)+&int (1-F(x)³) dx

v was chosen so that the first term would vanish at the endpoints, so that last integral gives us the average size of a large interval.

One can do a similar calculation for small and medium intervals, and the expressions are only slightly uglier, but this is as far as we can go without giving a specific form to the function F(x).

To proceed, assume that we have distributed the N dots on the line, and we scale things up by a factor of N, so there is on average 1 dot per unit length, then one can show that the function F(x) will tend to 1-e^-x for large N (I cannot really prove this, it makes sense, but people who wrote the solutions quoted at cut-the-knot took this result as obvious, so I suspect it is some elementary thing that I simply am unfamiliar with (to be honest, its why I found their solutions unconvincing and did my own awful one, I couldn't get past this point)).

Anyway, using that F for the integral, one gets that the average size of a large interval is 11/18. This must be multiplied by N to account for the fact that there are N intervals, but then divided by N because we scaled everything up by a factor of N.

A similar calculation gives that the average size of a medium interval is 5/18 and small intervals are 2/18.

So the ratio of small:medium:large intervals is 2:5:11. the small+medium intervals account for (2+5)/18 of the total length, giving the answer to the original problem. Note that if the small intervals are counted twice, then the total amount painted is (2+2+5)/18, which is exactly 1/2. I have not yet found a way to explain why this answer would be so clean.

When I first found out about the fact that small, medium, and large segments all appear with equal probability, I was inspired to try a slightly different problem. Suppose we take the unit circle and place 3 points on it, that will divide the circle into 3 parts, one small, one large, and one medium. On average, what is the relative sizes of these three parts?

This is simple enough to calculate, let the points be located at 0, x and y where x and y vary from 0 to 1 (1 being the full circle). By the symmetry of the problem, lets assume that x is smaller than y, and lets assume that the interval between 0 and x is the smallest. So y varies from 2x to 1-x and x varies from 0 to 1/3. The average length can be found from the integral

&int &int x dy dx

over the regions specified. We also need to divide by the integral of 1 over that same region, to divide by the probability that the region is actually a small one, essentially just normalizing properly.

Naturally, you can do a similar calculation for the largest interval and for the other one. In the end, you get the answers 2/18, 5/18, 11/18, unsurprising given that I chose to bring this whole thing up. So one does not need to work in the infinite case, somehow only using 3 points and 3 intervals gives the correct answer, but I have no idea why.

Shaking Hands

2011-03-09T15:24:00.000-08:00

Alright, the thesis is currently sitting at 40 pages, so I'm happy enough with my progress that I deserve to take a break. Naturally a break comes in the from of posting solutions to logic puzzles, because I have no sense of fun. So, lets look at the solution to the crazy ass number problem from last time.

First of all, if you played around with it a bit, you probably determined that for any starting N, only one final M was ever possible. As far as I am concerned, that fact was in of itself neat enough to make this puzzle pretty cool, but lets look at it a bit more.

First, if you just split N into N-1 and 1, and then N-1 into N-2 and 1 and just keep splitting off 1 all the way down, then you end with having written N-1, N-2, N-3,..., 2, 1 on board two, so the total sum is N(N-1)/2. Thus, if for any N there is only one possible value of M, that value must be N(N-1)/2. Note a particular edge case, that of N is 1, we take the value of M to be zero, later we will see that this is important for consistency.

Alright, so let us conjecture the solution to the puzzle:

When N is the starting value, then N(N-1)/2 is the unique final value of M.

Initially I wanted to prove this by induction, and one almost can, but actually to do it properly you need to break out strong induction, which I will talk briefly about first.

Induction is used if you want to prove some statement S(n) for all natural numbers n (and for the purpose of this post, the naturals start at 1 (and it pains me to write that)). You prove the statement is true by first showing that S(1) is true, and then showing that S(k-1) implies S(k) for k>1, good stuff, and the intuition behind it is pretty obvious for anybody who would actually read this blog.

For strong induction, you instead prove S(n) by proving S(1) and then show that [S(j) for all j less than k] implies S(k) for k>1. Intuitively, its not really any different from regular induction, the assumption is technically a bit different, but it still works. Naturally, one can reformulate any induction proof as a strong induction proof, as the strong induction assumption of [S(j) for all j less than k] is a stronger assumption than S(k-1), but there are some strong induction proofs that cannot be recast as regular induction, since you needed the stronger assumption. Strong induction is also used for proving statements about the ordinals, since some of those are not successors to other ones.

Anyway, let us prove our earlier conjecture by strong induction. It is easy to see that it holds for small N (I'm not sure about proving it for N=1, but lets just start with 2 or something). Now, assume that it is true for all j less than k for some k. Lets say that k is written on the board and calculate the possible values of M. We break k into p and k-p, for some p less than k. We then write p(k-p) on board 2, and are left with p and k-p on board 1. Naturally breaking up p results in us writing numbers summing to p(p-1)/2 on board 2 (by strong induction assumption) and breaking up k-p results in us writing numbers summing up to (k-p)(k-p-1)/2 onto board 2. Note that if p=1 or p=k-1, then having a 1 on board one does not result in any additional numbers on board 2, good.

So, on board 2, we have p(k-p) and a bunch of other numbers that sum to p(p-1)/2 and (k-p)(k-p-1)/2. Adding those up, we get k(k-1)/2 for any choice of p, proving the conjecture.

On the xkcd forums, somebody posted a much simpler solution than mine, and its cool enough that I will give it here.

Consider that we have N people in a room, and breaking N up into p and N-p is splitting people up into smaller groups. Before we split people up, they all shake hands with the people in the other group and say goodbye. For example, when we split 8 into 5 and 3, the 5 people each shake hands with the 3 people, so there are 15 handshakes. Board 2 is just keeping track of handshakes. The steps halt when everybody has been fully divided up and everybody must have said goodbye to everybody else. How many handshakes were there? There must have been N choose 2 of them, which is N(N-1)/2.

Splitting Up Numbers

2011-02-17T14:44:00.000-08:00

Time to take a break from thesis writing to blog. I won't have much time to blog for the next little while, due to said thesis, but I found a new puzzle recently I really wanted to post. I still intend to post the follow-up to my post from last time about other solutions to the birds on a wire problem, but I don't have the time to give that a full write up right now. Anyway, this puzzle is really weird to word properly, so if you don't get it the first time read the example I give after and then try reading it again. I first learned this puzzle on the forums at xkcd.

There are 2 blackboards, and on the first one a natural number N>1 is written, the second board starts empty. You are going to do a calculation in a series of steps. A step is defined as follows:

If there are no numbers greater than 1 on the first blackboard, stop. Otherwise select one of the numbers greater than 1, call it k. Select two natural numbers i and j smaller than k such that i+j=k. Cross out k from the first black board, and write i and j on the first blackboard. On the second blackboard, write the product i*j. Then do another step.

When you are done doing steps (because all the numbers on the first blackboard are equal to 1), and add up the numbers on the second blackboard, call this sum M.

The puzzle is, given the initial value of N, what are the possible values of M?

Alright, so as example, let us assume N=8. Now, we select a number of the board (there is only 8, so we choose it) and select that i and j are 5 and 3. We cross out 8 and write 5 and 3 on the first blackboard, and write 15 on the second one.

Next step we select 3, crossing it out and writing 1 and 2 on the first blackboard, writing 2 on the second blackboard. On the first board there is now (1,2,5) and on the second one there is (15,2)

Next step we select 5 and cross it out and write 2 and 3 on board one, writing 6 on board two. Board one has (1,2,2,3) board two has (15,2,6)

Next step we select 2, writing 1 and 1 in its place, and write 1 on board two. The boards are (1,1,1,2,3) and (15,2,6,1)

Next select 2, write 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,3) and (15,2,6,1,1)

Next select 3, writing 2 and 1 in its place, writing 2 on board two. The boards are (1,1,1,1,1,1,2) and (15,2,6,1,1,2)

Next select 2, writing 1 and 1 in its place, writing 1 on board two. The boards are (1,1,1,1,1,1,1,1) and (15,2,6,1,1,2,1)

Finally we stop, board one has no numbers greater than 1. We calculate M by adding up the numbers on board two, se we see M=28.

So we see that when N=8, it is possible for M to be 28. The puzzle is asking what other values of M are possible for N=8? What about other values of starting N?

Birds On A Wire

2010-12-15T14:45:00.001-08:00

Alright, time to post the solution to the dots on a line puzzle from last time. First I suppose I'll link directly the cut-the-knot page with the puzzle. He has a cool little applet thing there you can use to simulate the problem and try to guess the solution yourself, and he also has links to where people have written up derivations, one of which I will regurgitate on here later because I found it to be so interesting.

For today though, I am simply going to post the solution to the problem as Matt and I initially solved it. First, I must solve a very simple problem that gives us a technique that will be needed later. Consider the following problem:

N numbers between 0 and 1 are selected uniformly at random. On average what is the value of the smallest one?

First, let us try to solve this for N=2. We can see that we simply must solve the integral

∫ min(x,y) dxdy

integrated over [0,1]x[0,1], and min(,) is the minimum function. Clearly min(x,y)=min(y,x) so we can instead integrate over the "lower half triangle" and double our answer. So, instead integrate x in [0,1] and y in [0,x] in

2∫ y dxdy

the 2 is because we are only covering half the area we should be covering, and min(x,y) has been replaced by y, because x>y now. The integral is pretty simple to do, and gives the answer 1/3.

Now in the general N case we must consider we have a collection of N points {x[1],x[2],x[3]...,x[N]}, and integrate

∫ min(x[1],x[2],x[3]...,x[N]) dx[1]dx[2]dx[3]...dx[N]

As before, we order them x[1]>x[2]>x[3]...>x[N], so the min function always returns x[N], and we must integrate x[1] in [0,1], x[2] in [0,x[1]], x[3] in [0,x[2]] and so on. We must also find the prefactor, which is one over the area of the triangle we are integrating. Integrating the function 1 over the region of integration, we find the prefactor must be N!. So we must integrate

N!∫ x[N]dx[1]dx[2]dx[3]...dx[N]

over our triangular region. The final answer comes out to be 1/(N+1), sort of neat, but anyway I just wanted to demonstrate the technique so it is less confusing later.

Back to the problem at hand. We have N points {x[1],x[2],x[3]...,x[N]}, and we will order them as x[1]>x[2]>x[3]...>x[N]. Let us define

d[i]=x[i]-x[i+1]

so d[i] is the size of the i^th region, and this i runs from 1 to N-1.

Next, we will define S[i] to be equal to d[i] if the i^th region is shaded, and S[i] will be zero if it is not. The answer we seek is

S=N!∫ Σ S[j] dx[i]

Integrated over all the x[i] positions, and j summed from 1 to N-1 to add up all the shaded regions.

S[i] will be nonzero (and equal to d[i]) in one of two conditions:

1) x[i+1]-x[i+2] > x[i]-x[i+1]
2) x[i-1]-x[i] > x[i]-x[i+1]

That is, if d[i+1] is greater than d[i] or if d[i-1] is greater than d[i], d[i] will get shaded in.

With calculating probabilities, whenever you have to find the chance that A or B happens, it is often easier to find the chance that neither happened and take one minus that. Similarly here, rather than integrate whenever 1) or 2) happens, it is easier to find the situation of neither of them happening. Let is define q[i] as d[i]-S[i], so q[i] represents the unshaded regions, it is equal to d[i] when S[i]=0 and it is zero when S[i]=d[i]. Clearly then

S=N!∫ Σ S[j] dx[i]
=1 - N!∫ Σ q[j] dx[i]

We can of course move the sum outside of the integral, so we simply must calculate

∫ q[j] dx[i]

for an arbitrary j and then we can sum it up and multiply by N!.

The integration has x[1] running from 0 to 1 and x[i] running from 0 to x[i-1]. q[j] is zero in some of this region and nonzero is other parts, let us identify exactly where q[j] is nonzero. It is exactly the negation of conditions 1) and 2) earlier, that is

1) x[j+2] > 2x[j+1]-x[j]
2) x[j+1] < x[j-1]-2x[j]

This actually needs to break into a few cases, the first inequality is trivial if 2x[j+1] < x[j], since x[j+2] is always positive. The second case depends on whether x[j-1] is greater than or less than 3x[j] (because if x[j-1] is more than 3 times x[j] then the second inequality is made trivial by the fact that x[j+1] < x[j]).

So the integration region over dx[j-1] until dx[j+2] breaks up into many smaller pieces that one can cleanly write out with this information, but its fairly lengthy, so I'm not going to bother here. In this region, q[j]=d[j] so you simply integrate x[j]-x[j+1] in this region. This integral is most easily done in Maple (or whatever other math program you like) by first doing the integrals from dx[N] to dx[j+3] (the function is constant there and the integration region is simple) then doing the next four integrals carefully, then finishing it off integrating to x[1].

In the end, you get a somewhat awful function of N and j. You then sum j going from 1 to N-1 and multiply by N!. You will get something somewhat less awful, but a still terrible function of N. Finally, you must take the limit of N going to infinity (this step will be easy enough to do by hand, but by this point you already have Maple open anyway, and your spirit will have been far too crushed to do such a limit) and in then end you get 11/18. This was the unshaded region (the shaded region was 1-(the integral of q[j])) so the shaded region is given by 7/18.

Next time I'll go into a bit of the analysis by the other solutions found at the cut the knot page. One of them I found to be particularly interesting so I wanted to show it in detail, but I wanted to demonstrated my own horrible method first.

Also, I expect the date on this post will be confusing, I started writing it some time ago, but it took me more than a month to get around to finishing it.

Dots On A Line

2010-11-24T15:01:00.000-08:00

Alright, I think I've finally run out of puzzles if I'm going to post this one. It is a rather crazy one that I solved with Matt many years ago and I absolutely love the answer to it. Sadly there isn't really a clean way to solve the puzzle, you have to do it the hard way, and its really not very illustrative of why the final answer is what it is, but thats just life. I initially found this puzzle at cut the knot:

Consider the unit interval between 0 and 1. Select N points randomly on that interval (random with uniform distribution). From each selected point "color in" the part of the interval between it and the closest neighboring point. In the limit as N goes to infinity, what fraction of the interval is colored in on average?

Terrible, I know. To clarify, suppose we had N=5 and selected the points 1/10, 2/10, 4/10, 7/10 and 8/10. Then from 1/10 we would color to 2/10, from 2/10 we would color back to 1/10 (not that that does anything), from 4/10 we color back to 2/10, from 7/10 we color to 8/10 and from 8/10 we color back to 7/10 (again does nothing). Then the colored region would be [1/10,4/10] ∪ [7/10,8/10] so in total 4/10 of the interval was colored in, in this case.

Balancing It Out

2010-11-05T13:39:00.000-07:00

Time for the solution to the recent balance scale puzzle.

First, notice that there is a symmetry in the problem that needs to be broken, specifically there is no real distinction between "fake" and "genuine", if you swapped those labels the problem is identical. Let us break that symmetry by selecting a single coin and then we are going to show that all the other coins weigh the same as that special one. In effect, I will declare any coin with the same mass as that one to be "genuine" and a coin of any other mass to be "fake".

Now that we have one genuine coin, take the other nine coins and divide them up into three disjoint sets, one of two coins, one of three coins, and one of four coins. We will denote these sets of coins as 1, 2, 3, and 4, so if I say we weigh 3 vs 1+2 I mean to take the set of three coins and weigh them against the set of two coins plus the single genuine coin.

Naturally, our three weighings are going to be some coins against some other coins, equal in number, such that if a weighing is ever imbalanced we are done immediately (we would have proven there is at least one fake and one genuine coin), so we are free to assume that all weighings are balanced (as opposed to other balance scale problems where you have to divide up the tree into "if left heavy", "if right heavy", and "if balanced").

First weighing, 3 vs 1+2. When this is balanced, we know that the number of fakes in 2 (call that x) equals the number of fakes in 3 (so, x is also the number of fakes in 3). Second weighing, 4 vs 1+3. When this is balanced, we know the number of fakes in 4 is also x. Finally, we weigh 1+4 vs 2+3. When this is balanced we know that x=x+x, guaranteeing that x is 0 and there are no fake coins.

It is sort of neat that you can do those weighings in any order you want, since you don't gain information after a weighing (or rather if you did, you were done right away). But if you do the weighings in another order the information is a bit less natural to analyze.

More Masses?

2010-10-28T15:25:00.000-07:00

Alright, new puzzle I found today at Tanya Khovanova’s Math Blog:

Consider you have a collection of 10 coins. The coins can either be genuine or fake, a fake coin weights a slightly different amount than a genuine coin. All fake coins weigh the same and all genuine coins weigh the same. Using three measurements on a balance scale, prove either that all the coins have the same mass or that they do not.

For the balance scale rules, see the old counterfeit masses puzzle. These constant balance scale problems and total lack of hat problems are making me want to rename the blog "Standard Balance Scale Rules Apply".

All Drunk

2010-10-13T12:47:00.000-07:00

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

2010-09-21T15:11:00.001-07:00

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

2010-09-14T15:54:00.001-07:00

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

2010-09-02T16:15:00.001-07:00

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.

Genuine Coins

2010-08-24T13:26:00.000-07:00

Research is hard, blogging is easy.... In conclusion, time for the solution to that mass puzzle from last time.

I guess I will go through the solution as I found it. First of all, note that if your first measurement is imbalanced, you are probably home free. If the left is heavier than the right, then the right cannot have more than 1 fake mass, and therefore you can divide the right into two piles (throwing out an odd mass if you need to) and use those for your second weighing. Whichever side is lighter cannot have any fakes, and if they are both equal then neither has fakes. Thus if the first measurement has N masses to a side, then if it is unbalanced you can find N/2 genuine masses (or (N-1)/2 if N is odd).

This means that we only need to solve the case where the first measurement is balanced, and this is much more difficult to deal with (as you almost certainly found if you tried to solve it). My first solution found at least 10 genuine masses as follows: Begin by dividing up the masses into 4 groups, A has 10 masses, B has 20, C has 30 and D has 40. Next, weigh A+B against C, if this is imbalanced, use the method above to find at least 15 genuine masses. If it is balanced, this means that A+B and C each have the same number of fakes, either 0,1, or 2 each. This means that D must have 0,2, or 4 fakes, this restriction is very important. Next, weigh A+C against D. Suppose this is balanced as well. Then D must have 2 fakes (it can't have 0, for C would have 2 then), but if D has 2 fakes and this measurement is balanced, then B is free of fakes. Alright, suppose this measurement has D heavy, then if D has 2 fakes, C must have 1 and A+B has 1, but its not in A, so A is genuine, if D instead had 4 fakes, A is still genuine. Finally, if A+C is heavy, then D has 0 fakes.

So, each result in our second measurement points to one coin pile, D heavy implies A, balanced implies B and A+C heavy implies D. Thus we are guaranteed to find at least 10 genuine masses.

We can generalize this, have 4 yet unspecified piles, A,B,C,D and use the method above. This means we must obey the equations:

A+B=C
A+C=D
A+B+C+D=100

Three equations for 4 unknowns, so there is a one-dimensional degree of freedom. We use that freedom to maximize min{A,B,D}. To be strict we also want to make sure that (A+B)/2 isn't too small, just in case the first measurement is balanced, but that isn't really an issue.

One can solve those equations as to get

A=3D/2-50
B=100-2D
C=50-D/2

Just looking at integer values of D and maximizing min{A,B,D} the solution is when D=42

A=13 B=16,C=29

So this guarantees getting 13 genuine masses. One funny point, there is a "better" solution at D=300/7=42+6/7 with

A=100/7=14+2/7
B=100/7=14+2/7
C=200/7=28+4/7

So, if you can use fractional masses, this is better.

Anyway, on Tanya Khovanova’s Math Blog they discuss a solution with 14 masses, but never explain it fully. This might be related to my fractional solution, but that is slightly crazy. Anyway, this solution can be constructed using the following structure for piles: A=14, B=14, C=29, D=42, E=1

First weigh A+B+E vs C, if it is imbalanced, then you can find 14 genuine ones. If it is balanced, then D again has 0,2, or 4 fakes in it, corresponding to C having 2,1, and 0 fakes in it.

Next weigh A+C vs D+E. If this is balanced, then D must have 2 fakes, C has 1 and A has 1, so B+E are all genuine (had D no fakes, C would have 2 and E cannot make up for it). If this measurement has D+E heavy, then D cannot have 0 fakes (C would have 2) so if D has 2 fakes, C has 1 and A cannot have any, so A is genuine (if D has 4 fakes, A is also genuine). Finally, if our measurement has A+C heavy, then D cannot have 2 fakes in it, so D is genuine.

So we have A+C heavy implies D is genuine, D+E heavy implies A genuine, and balanced implies B+E genuine. This guarantees at least 14 genuine masses are found. The word genuine has lost all meaning to me at this point.

Masses Again

2010-08-16T14:03:00.000-07:00

Alright, another puzzle from Tanya Khovanova’s Math Blog. This one is another counterfeit mass thing.

There is a pile of 100 masses, and 4 of them are slightly heavier than the others. The 96 'true' masses are identical to eachother in weight, and the 4 'fakes' are slightly heavier than the others, but also identical to eachother in weight. Using 2 measurements on a balance scale, identify at least one 'true' mass.

As a follow-up, you can try to identify a collection of true masses, how many can you find in those two measurements? For rules on the balance scale, it is the same as the old one from the counterfeit masses puzzle.

I know that typically people make the counterfeits lighter than the genuine ones, but then it screws me up when I write the solution because I want the heavy ones to be the odd ones out.

Axiom Of Hats

2010-07-29T13:26:00.000-07:00

Man, I meant to blog one more time before the go congress, but blogging is so hard. Anyway, solution time. Puzzle from last time was another hat one. The solution is rather similar to puzzles I have posted here before, but it still took me a little while to get it.

As always, it is easier to start with the two person, two colour case. Suppose the two colours are white and black, and we have two rooms. Label the two rooms white and black and go into the room that corresponds to the hat colour of the other person. If you both have the same colour, you will go to the same room, but if you have different hat colours you will go to different rooms.

Naturally, a strategy for the more general case must just be a function that maps from the hats you see to the room you go to. Lets try two hat colours and N people next.

We have two rooms again, call one room even and one odd. If you see an odd number of black hats, go to the odd room, if you see an even number of black hats, go to the even room. Then, if the total number of black hats is even, white-hatted people will go to the even room and black-hatted people will go to the odd room. Naturally it works the other way if the total number of black hats is odd. One could also arrive at this strategy by assigning the rooms numbers 0 and 1 and call white 0 and black 1. Then add the hat colours you see mod 2 and go to that room.

This generalizes to the strategy for N people and K colours. First number the hat colours 0 through K-1 and number the rooms 0 through K-1. Then add the hats colours you see together mod K and go to that room. We can see this strategy works by considering the sum of all the hats (call that S), then a person with hat colour x will go to the room S-x mod K. If two people with hat colours x and y go to the same room, then S-x=S-y mod K and so x=y mod K and so x=y, two people go to the same room means they have the same hat colour, so this solution works.

Generalizing this to the case of countably infinite hat colours is trivial, you can just use the same solution and forget the mod K stuff. Each hat is a natural number, and add together the hats you see and go to that room.

With infinite logicians it is a bit more tricky. In this case there are infinitely many of them to add together, so you can't just go to the 'infinity room' and be done with it. Since we have been handed the Axiom of Choice, we might as well make use of it.

What can one do with the Axiom of Choice? In most cases, the most efficient thing to do is the same old equivalence class thing. Let us construct an equivalence class of hat sequences. Two sequences are said to be the same if they differ in only finitely many places. Now we can use the axiom of choice to construct a set S which contains exactly one element from each equivalence class. Since each logician can see all but finitely many hats, they can all determine what equivalence class we are in, and thus can select an element x in S that differs from the real sequence of hats in finitely many places. We will add together those finitely many hats to construct our solution.

Alright, so everybody sees most of the full sequence of hats y_i and they all have agreed on a sequence x_i that differs from the sequence y_i in finitely many places, they must now choose a room to go to. Let us suppose that all the hats are correct. Then it is simple, you just go to the room that x_i says you go and it will all work (the hats and the rooms have both been numbered as naturals). Now, let us suppose that person j is wearing the wrong hat colour, that is x_j ≠ y_j but all the other x_i=y_i. Now he is going to go to the room suggested by the hat x_j, which is x_j-y_j too many, so everybody else must also go x_j-y_j too many also. It is possible for this number to be negative, so first we must number the rooms as integers instead of naturals. So, the strategy is that when you are person n and you see hat j wrong, you go to room x_n+x_j-y_j. Naturally, if you see more than one wrong hat, just add up x_i-y_i of all the hats that are wrong (there are only finitely many) and add that to your own x_n and go to that room.

Tanya Khovanova has a complaint with this solution that even though the Axiom of Choice allows you to select the set S that we will use for the solution, it does not guarantee that there is a method of distributing the set S to a collection of people. If they cannot distribute the set S, they cannot guarantee that they all have the same one (and I would suppose they almost certainly do not, but that is a bit of an odd statement to make). I am not sure if I agree with her on this point, but I generally am against the Axiom of Choice in the first place, so it is a bit of a non-issue for me. At any rate, I suppose one could distinguish another axiom where you have the Axiom of Choice, and you may actually describe the set it gives you, then this puzzle simply needs that, more powerful, axiom to solve.

Hats Again

2010-07-23T14:34:00.000-07:00

Time for new puzzles that Mark told me but he actually got from Tanya Khovanova's math blog:

1000 logicians are going to play a game against The Adversary. The Adversary has a collection of hats that come in 6 different colours. There are also 6 rooms. The Adversary is going to gather all the logicians together and put a hat on each of their heads, and then the logicians must simultaneously decide what room they are going to enter. After the logicians have each gone to their chosen rooms, each room must have logicians with only one colour of hat. The logicians may strategize before the hats are assigned, find a strategy that guarantees that each room will have a unique hat colour in it. Standard hat rules apply, of course.

You can assume that the logicians know what colours are available. If you like, you can also generalize to N logicians and K hat colours, its not much harder. What is harder is allowing N and K to be infinite, you will need the axiom of choice in this case, but its also an interesting puzzle.

Flip A Coin

2010-07-21T13:01:00.000-07:00

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 &Sigma _{n to A-1} P(n)²+2(1-&Sigma _{n to A}P(n))²-2&Sigma _{n to A} P(n)(1-&Sigma _{j to n}P(j))

&Sigma _{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

2010-07-12T12:39:00.000-07:00

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.

Two At Most

2010-07-07T16:38:00.000-07:00

Time to post the solution to the follow-up coin problem from last time. The solution isn't hard to come by, and is basically an extension of the first move of the solution from last time. Last time the first measurement was the 1,2,3 against the 6 and since they balanced, you knew for a fact that the 6 was in fact the 6 (it is the only single coin that can weigh as much as three others). This time you weigh the 1,2,3,4,5 against the 7,8. They will come out balanced, but there is no way the left side weighs less than 15 and no way the right side weighs more than 15, so they must each be exactly those weights. This leaves the 6 uniquely identified.

Actually, this question has an interesting generalization, if we have N coins with masses 1 through N and we know their masses, how many measurements of a balance scale does it take to prove the mass of one of the coins? It is easy to prove that you can always do it in three or fewer measurements as follows: N can be written as a sum of 3 triangle numbers (this is a result of the Fermat polygonal number theorem, though for triangle numbers it was initially shown by Gauss). Call these numbers A, B, and C, assume that A ≥ B ≥ C. Weigh 1,2,3,4...k against A such that they balance (we know such a k exists, A is triangular), the balancing proves that the weights on the right has a mass at least A. Next weight 1,2,3,4,...m and A against (B+A), (B+A) being the single mass of mass B+A, and m is defined by 1+2+3+4+...+m=B. When they balance it proves that B+A is at least B+A. Finally weigh the 1,2,3,...j and (B+A) against N, where j is defined by 1+2+3+4+..+j=C. When they balance it proves that N is at least N. But N is at most N, so N is identified.

Actually, two weighings is always sufficient to prove that you can find one mass, this was proven in a paper entitled Baron Munchhausen’s Sequence, which also contains the proof from the previous paragraph. The proof is rather long though, and there is little sense in reproducing it here.

Probably Correct

2010-07-01T12:23:00.000-07:00

Alright, Canada day seems like a good time to post the solution for the labeled masses problem. Working on it yourself you probably found it is best to assume that the coins are labeled correctly and attempt to prove that rather than something else. Any method that would actually prove the coins are labeled correctly would also show that they are labeled incorrectly if they are not (if it didn't do that, one would hardly accept that it proves they are labeled correctly). Actually, this gives us something of a rewording of the problem, which I will later transform into the followup problem. Assume the coins are unlabeled, but you know which coin is which, you must prove to an audience (of mathematical puzzle solvers) that you know which coin is which using only 2 measurings.

Anyway, moving on to the solution (to the problem as initial worded). Its tricky to do anything involving weighing 1 coin against 2 right away, since if you weigh 1+2 against 3, even if it balances you cannot be sure that it was not the 1+3 against 4 or the 2+4 against the 6 or something. You could also try having 4 coins on one side, but that cannot work since on the second measurement you must split up those 4 coins or you cannot tell them apart. Perhaps something involving 2 vs. 2 works, but I didn't find anything. The thing that does work is to weigh the 1+2+3 against the 6. If it is imbalanced, we are done, if it is balanced then you have identified the 6 (it is the only one that can have as much mass as 3 others combined) and you have identified a group that is the {1,2,3}, since they are the only 3 light enough that a single coin could balance them.

So, in one measurement we have identified the {1,2,3}, the {4,5} and the {6}. The next measurement is to do the 6 and the 1 against the 5 and the 3.

If they are labeled correctly, the 5+3 should be heavier than the 6+1 (so, if that doesn't happen we are done). Since the 6 is identified, and the 1 must weight at least 1, the 6+1 must weigh at least 7, but since the 5+3 came out heavier, the 5 could not be any lighter and neither could the 3, so the 5 and 3 are correct. By a similar logic, the 5+3 cannot together weight more than 8, so the 1 cannot afford to be any heavier if the 6+1 is to be less than 8, thus the 1 must be the 1. That leaves the 2 and 4 both uniquely identified.

This completes the solution. I cannot prove that there aren't any other solutions, but I greatly doubt their existence.

Next, the follow-up:

A mathemagician has 8 coins, with masses 1 through 8, he knows which coin is which. He intends to prove to an audience that he knows the correct mass of at least one of the coins using a single measurement of a balance scale. What measurement can he perform to prove the mass of any one of the coins?

You may assume that the audience knows that the coins have masses 1 through 8, but they do not know which one is which. After one measurement, the mathemagician must be able to select a single coin and say "I have now proven this one is the x" for some value of x. You may also assume the audience is a bunch of mathematicians, they will not be tricked by some sort of lies.

Labeled Masses

2010-06-22T15:25:00.000-07:00

So, Mark seems to be quite the source of new puzzles recently, I guess its those crazy people in his office or something. Anyway, here is the latest one from him:

There are 6 coins on a table, having masses of 1,2,3,4,5,6 grams. They are also labeled 1 through 6. Using two weighings of a balance scale, you must prove if they are correctly labeled or that they are not.

It is the same balance scale as the counterfeit masses puzzle, that is to say, using the balance scale to make a measurement can be visualized as follows: The scale has two places to put coins, you put as many coins as you like in each of those two places, then you push a button and the scale tells you which of the two places has more mass on it, or that they are balanced. The button will work 2 times and then the scale will break.

Board Of Hamming

2010-06-13T10:54:00.000-07:00

OK, I think the checkboard puzzle has been up for long enough now. Time for the solution.

Mark managed to find the solution much faster than I did, but thats because I managed to confuse myself for quite sometime with Hamming codes, because I have gotten far too used to that stuff doing these other puzzles. To construct the solution, let us assume that the geometry of the board will play no part, and that there simply are N squares that have stones (or not) on them. Alice must remove or add a stone to be able to communicate a single square to Bob. A solution seems possible at least, since Alice has N possible moves and must communicate one of N possible choices, so there is theoretically enough room, but there can be no room wasted from any position.

First let us try to solve the N=2 case. The board configuration is represented by an element of {00,01,10,11}, where "1" means that square has a stone and "0" means it does not. Bob must have a function that maps from that set to {A,B} where "A" is the square on the right and "B" is the square on the left. From any given configuration, Alice must perform exactly 1 bitflip and specify "A" or "B" to Bob. Alice needing this ability puts restrictions on Bobs possible functions.

A function that works for Bob is f(00)=f(10)=A, f(01)=f(11)=B. The first bit is ignored and the second bit specifies which square is being pointed at. Alice simply looks at the board, if it already pointing at the correct answer, flip the first bit, if instead it is pointing at the incorrect answer, flip the second bit. This will always give Alice a move to make. Note that Alice needed to reserve a move as the "nothing move" just in case The Adversary chose a position that she didn't want to move from.

Let us try the N=3 case. Now we need a function from {000,001,010,011,100,101,110,111} on to {A,B,C}. Let us assume that The Adversary has set up the board in position 000 and has pointed at one of the squares A,B, or C. Alice must change the board to one of {001, 010, 100}, so without loss of generality, we might as well assume f(001)=A, f(010)=B, and f(100)=C. Next, assume The Adversary has set up 110, meaning Alice must choose from {010,100,111}, since f(010)=B and f(100)=A we must have f(111)=C or The Adversary will defeat us. Next, assume The Adversary has set up 011, so Alice must choose from {111,001,010} since f(111)=C, f(001)=C, and f(010)=B, The Adversary can select square A in this case. This proves there cannot exist a function that solves the puzzle on a board with 3 squares.

The failure in the N=3 case is not surprising if you realize that f has to map from a set with 8 elements on to a set with 3 elements, and this cannot be done symmetrically to the set with 3 elements (3 does not divide 8, that is). In general, we will have to find a function from a set with 2^N elements to a set with N elements, so this will only divide evenly if N is a power of 2. For the full problem N=64, so there is still hope.

You can try out the N=4 case next if you like, just by explicitly constructing the function, it all works out if you do it right, but its not especially illuminating as it is difficult to see how to generalize it just from one particular function (at least it was difficult for me).

For general N, one can get a hint of the solution by remembering that from any position there must be a "dummy move", that is, suppose you have a strategy f (mapping from board positions to special squares). If the adversary set up a position x that has the feature f(x) is already the special square, Alice must be able to make a "nothing move", a move that does not change the value of f. Let us assume that there is one square on the board that f is not sensitive to, so Alice can always just toggle that one if she needs. Then there really are only N-1 squares on the board that f looks at, and Alice has the choice of if she wants to toggle one of the N-1 squares or not. The adversary still has N choices of special squares though. We suspect that N should be a power of 2 for a solution to exist, so N-1 is 1 less than a power of two, of course. This immediately made me think of Hamming codes, as those only exist of length M when M is 1 less than a power of 2.

Let us go over what Hamming codes are again. Consider the set of all binary strings of length M (call this set S). We want to construct a set H that is a subset of S with the following feature. For every element x in S there exists an element y in H such that y is no more than 1 bitflip away from x. In the Sam and Ray problem, this was used so that Sam could specify a member of S accurate to 1 bitflip by only specifying a member of H (and it took fewer bits of data to specify an element of H than to specify an element of S).

For our game, let us try the following strategy for Bob. Bob will look at the N-1 squares on the board (ignoring the agreed-upon "dummy square"), this specifies a binary string of length N-1, which will either be a hamming code exactly or be 1 bitflip away from one. If it is 1 bitflip away from one, then the location of that bit that needs to be flipped is the special square. If it is 0 bitflips away from a Hamming code, then the dummy square is the special square.

Can Alice always manage to communicate any square to Bob? If The Adversary sets up a Hamming code exactly, then it is trivial, Alice simply flips the bit on the special square. If The Adversary chooses the dummy square as the special square, the Alice can always do 1 bitflip to put the board into a Hamming code position (unless it is already in one, in which case she just flips the dummy square). The remaining cases (which are, admittedly, the majority of the cases) still need to be checked. First let us reexamine how the Hamming codes actually look.

Consider the set S, binary strings of length M, where M is one less than a power of two, so M+1=2^K. Number the bits 1 through M, and divide them into "parity bits" and "data bits" as follows: a parity bit is one whose number is a power of 2, all others are data bits. We can see that there are K parity bits and M-K data bits. We will construct the set of Hamming codes, H, by letting the data bits run over all possible values, and the parity bits will check the parities of the data bits. The parity bits are labeled with the powers of two, so they are bits 1,2,4,8,16,... The parity bit labeled 1 will check the parities of data bits 3,5,7,9,... (all the numbers with a 1 in the ones place of their binary expansion). The parity bit labeled 2 will check the parities of data bits 3,6,7,10,11... (all the numbers with a 1 in the twos place of their binary expansion). The parity bit labeled 4 will check the parities of data bits 5,6,7,12,13,14,15... (all the numbers with a 1 in the fours place of their binary expansion). The check the parities of a bunch of bits means to XOR them together.

To reuse a section of an earlier post, with some slightly changed notation..."for the case M=7, the set H looks like

0000000
1101001
0101010
1000011
1001100
0100101
1100110
0001111
1110000
0011001
1011010
0110011
0111100
1010101
0010110
1111111

Note that bits 3,5,6,7 run over all possible values. Bit 1 checks the parity of bits 3,5,7. Bit 2 checks the parity of bits 3,6,7. Bit 4 checks the parity of bits 5,6,7.

Further note that every bit is being checked by a unique combination of at least two parity bits. Bit 5 is being checked by 4 and 1 (because 5 in binary is represented as 4+1) and only bit 5 is being checked by bits 4 and 1 alone. This idea will hold in general."

"if we are given a binary string of length M, we can find an element of H that is different in no more than 1 spot through the following method: Find the element of H with the same data bits, it will differ in one or more parity bits. If it differs in one parity bit, we are done. If it differs in more than one parity bit, add of the values of those parity bits to find a value j. You will find that if you flip data bit j, all of the parity bits will now be correct and you will have exactly an element of H. Thus you either differ in only one parity bit, or the incorrect parity bits specify what data bit is off from an element of H."

Anyway, you can try this explicitly in the case N=4 and you will find it works out, great, Alice always has a bit she can flip to inform Bob of the special square, how do we prove it works in general? Well, first we need to look at the Hamming codes a bit differently.

Consider a typical Hamming string, like 0110011, this has ones at 2, 3, 6, and 7. the data bits {3,6,7} look like {011,110,111} in binary, their 1's place XORs to 0, their 2's place XORs to 1 and their 4s place XORs to 0, or more simply, they together XOR to 010. Actually, the full thing {2,3,6,7} is {010,011,110,111}, which XORs to 000. In general an element of H will do that, so that whole construction was a bit over the top.

Suppose you are given an element of S, to find the corresponding element of H you just XOR the values of all the 1's together, and flip that bit. For example 1101110 is {1,2,4,5,6} is {001,010,100,101,110} XORs to 100, thus you must flip bit 4 to get a hamming code, we can see that 1100110 does XOR to zero, it is a hamming code.

This gives us a more succinct strategy for Alice and Bob (and a proof that it works). Alice and Bob number the squares 0 through N-1 (0 will serve the job of the "dummy square"). Alice then looks at the squares where The Adversary places stones and XORs them together, getting a number y. She then XORs the value of the special square with y, and performs her bitflip on the result. Now the values of the squares with stones on them will XOR together to the special square, this works just by symmetry of XOR (that is, if A XOR B = C then A XOR C = B, even if A,B,C are binary strings). It is easy to see that the solution only works if N is one less than a power of two, suppose N was 45 or something. Then when Alice XORs everything together, she might get a result of 59 (or any number as high as 63 is possible) and she cannot flip that bit, it does not exist.

This more succinct wording of the strategy is actually the strategy that Mark found initially. I found it rather amusing that we both found the same solution, but had each had a rather different formulation of that solution.

Game On A Board

2010-06-07T15:37:00.000-07:00

Its a bit quick for me to post a new puzzle, but Mark actually gave me a pretty cool one recently. Also I have a bit of a backlog of puzzles to put up, so I might as well fire this one out:

Alice and Bob are going to play a game against The Adversary. The game is played on an 8x8 checkerboard, and there is a collection of featureless stones alongside the board. The game begins with Bob being removed from the room, and The Adversary selects one of the squares on the board and declares it the "special square", showing his choice to Alice. The Adversary then places any number of stones on the checkerboard, such that each square has either zero stones or one stone on that square. Alice is then required to either remove exactly one stone from the board or add one stone to any empty square. Bob is then brought into the room and is shown the final configuration of the board. Bob must then successfully identify the special square. Before the game, Alice and Bob may strategize. Find a strategy that guarantees Bob can find the square that was chosen by The Adversary.

In case it wasn't obvious, you may assume The Adversary is an adversary.

Alone At The Party

2010-06-03T12:51:00.000-07:00

Time for the solution of the follow up to the shaking hands problem.

I came up with the puzzle itself upon realizing that the people in the initial problem naturally pair up. If one person shook everybodys hand and one person shook nobodys hand, those two people are naturally partners, and everybody shook exactly one hand of that partnership.

To see how this puzzle solves out, lets consider a simpler case. With N=1, there are 3 people at the party, including yourself. You asked the other two people how many hands they shook, and they each gave you a different answer. The possible answers are in the set {0,1,2}, so you must have heard the answers {0,1}, {0,2}, or {1,2}. It is easy to see that {0,2} is impossible, since 2 shakes hands with everybody and 0 shakes hands with nobody, they couldn't have both gone to the same party. In the case {0,1} it must have been you who shook hands with the 1, since it wasn't the 0 who did, thus, you shook one hand. In the case {2,1} 2 must have shaken hands with 1 and with yourself, and so again, you shook hands with exactly 1 person. Therefore we see that for N=1, the answer to the puzzle is 1.

One can arrive at this answer much faster by simply seeing that the two other people shook hands with a different total number of people, thus exactly one of them must have shaken hands with you. You don't know if they shook hands with eachother, and don't care, you get the answer of 1.

Now, generalizing to N, the 2N people we asked must have given answers from the set {0,1,2,...2N}, and so exactly one of those must not have appeared. There is no way both 0 and 2N appeared though, so the answers were either {0,1,2,...2N-1} or {1,2,3,...2N}. In the former case, 0 shook hands with nobody, and 2N-1 shook hands with everybody but 0, so lets remove that pair and reduce everybodys number by 1, after which the answers we have heard are {0,1,2,...2N-3}. N has been reduces by exactly 1 and the total answer has also, so if F(N) is the answer we seek, F(N)=F(N-1)+1. In the other case {1,2,3,...2N}, 2N shook hands with everybody, and 1 only shook hands with 2N, so lets remove that pair and reduce everybodys number by 1 again, after which the answers we have heard are {1,2,3,...2N-2} again we see that F(N)=F(N-1)+1. Since F(1)=1, we can see that F(N)=N again, just like the last puzzle.

Note that if there are an even total number of people at the party, the puzzle cannot be solved. The same reduction down to a simpler case still holds, but when you get down to yourself and 1 other person, you have no way to know if you shook hands with that other person or not. Basically, the two cases split the puzzle into whether or not partners shook hands. When you are a member of a partnership you need some additional information on the puzzle to finish things off, but if you are the odd man out, then you do not care if partners shake hands with eachother.

More Is Less

2010-05-28T16:08:00.000-07:00

So, I find it to be rather unfortunate that the night after posting my puzzle about shaking hands from last time, I managed to come up with a similar problem that I consider to be more interesting. This leaves me with the issue of either solving that puzzle from last time and then posting the new puzzle as a follow-up, or just posting the new puzzle and solving them both at once next time. The problem with the former is that after the first puzzle is solved, the second puzzle is very easy to do (its the exact same logic), but it does have one extra thing one needs to notice in order to solve it, so it still is not trivial. The problem with the latter is that I find it unappealing for aesthetic reasons that don't really make sense.

Going with aesthetics, I guess I might as well solve the puzzle from last time now. The logic is very simple, first of all notice that each person has 2N people available to shake hands with (of the 2N+2 people, they cannot shake their own or their partners), and so the number of hands each person shakes is between 0 and 2N. You asked 2N+1 people how many hands they shook, and you received 2N+1 unique answers, thus you must have received every answer between 0 and 2N, pigenhole principle and all that. We will identify each person by the number of hands they shook, that is, person k shook k hands, and this assignment gives each person a unique number.

Person 2N must have shaken hands with every person they could, and person 0 must have done the opposite. These two people must be partners, or those two people did not go to the same party. Thus, (0,2N) is a pair. Now, each person at the party outside of that pair must have shaken hands with exactly one person in that pair (2N, to be specific), so lets just remove pair (0,2N) and reduce everybodys number by 1. This has now set up the exact same situation as the original problem, but we have reduced N to N-1. Everybody's number is 1 lower, but they are all still unique. This means that whatever the solution is to the problem with N (call that F(N)) it will be 1 lower when N is instead N-1. That is to say

F(N) = F(N-1)+1

Which means

F(N)=F(1)+N-1

so we just have to solve the N=1 case.

When N=1, the answers you were told were 0,1, and 2. 2 and 0 must be partners by the same logic as before, and 1 must be your own partner. Since 2 shook hands with 2 people, the other hand must have been yours, and 0 did not shake your hand. This means that F(1) is 1 and therefore F(N) is N. Proving that you shook hands with N people, exactly 1 person from each couple.

Now for the follow-up puzzle:

You go to a party with 2N other people (so there are 2N+1 people in total at this party). At the party people shake hands with other people. No person shakes hands with themselves. After the party, you ask each person that was at the party how many different people they shook hands with, and each person gives you a unique answer. How many different people did you shake hands with?

Very much the same setup, but the "couples" concept has been stripped away.

Shaking Hands

2010-05-22T15:42:00.000-07:00

New puzzle time. Mark told me this one a week or two ago, and since he is approximately 90% of my readership I'm not sure why I'm posting it, but here we go:

You and your partner go to a party with N other couples (so there are 2N+2 people in total at this party). At the party people shake hands with other people. No person shakes hands with themselves or with their partner. After the party, you ask each person that was at the party how many different people they shook hands with, and each person gives you a unique answer. How many different people did you shake hands with?

Mark initially asked me this with N=5, and then found it wasn't more interesting to generalize it to N. I will initially ask it with N and find it isn't any more interesting to specify it to 5.

Less Gladiators

2010-05-18T13:12:00.000-07:00

Time for the solution to the second gladiator problem. As before, I guess the thing to do is start with a simpler case.

Suppose Alice has a single gladiator of strength A, and Bob has two gladiators of strengths B₁ and B₂. Again, Bob needs only decide which of the two gladiators to send first and the whole match is set.

If Bob sends gladiator 1 first, he wins with chance B₁/(A+B₁) and loses with chance A/(A+B₁). If he loses the first game, he then has a B₂/(A+B₂) chance to win the second game.

This gives Bob's chance of winning as:

B₁/(A+B₁)+AB₂/(A+B₁)(A+B₂)
=1-A²/(A+B₁)(A+B₂)

unsurprising, its one minus Alices chance of winning both matches. This is symmetric in B₁ and B₂ again, so it is independent of Bobs strategy. Its true that the full game is also strategy-independent, but it is actually a bit weirder to prove this one. I was not able to come up with a proof myself, this was in the paper where I found this problem.

Let us consider to replace the gladiators with lightbulbs that have a fixed burn out time. The burn out time of one of these idealized lightbulbs is memoryless, and if the lightbulbs expected lifetime is x, then the probability that it is still burning after time t is given by e^-t/x.

If we have a lightbulb with lifetime x and a lightbulb with lifetime y both burning at the same time, the chance that y burns out first is given by x/(x+y). So two gladiators fighting can be appropriately replaced by a "lightbulb match" where both Alice and Bob must turn on one of their bulbs and whichever goes out first is defeated. Since the burnout time is memoryless, the chance that a given lightbulb will burn out in the next five minutes is the same as the chance it had to burn out in the past five minutes, so it is enough that the winner simply leave their light on and the loser must turn on a new bulb. In the end whoever runs out of lightbulbs is the loser of the match.

We can see this game could just be replaced by Alice and Bob showing up on separate days, Alice turns on one of her bulbs until it burns out, then she turns on another one and so on until she runs out of bulbs, when she is out of bulbs she records the total lifetime of her team. Bob then comes by and doe the same thing. Whoever has more total lifetime wins the gladiator match. Its pretty clear there is no strategy in this game, but it is the same as this gladiator match game.

This game is a bit less fun than the other one, since human intuition arrives at the "all strategies are the same" result much faster than the other game. I guess thats because in the simpler case its very obvious. If our opponent has only one gladiator, then it does not matter what order we send ours in, our opponent must defeat them all anyway. In spite of the result being more obvious though, the proof is actually trickier to think of, because the setup does not have as much of an obvious "zero expectation value" minigame.

More Gladiators

2010-05-15T10:41:00.000-07:00

Alright, this one is the final problem from "Games People Don't Play":

Alice and Bob are competing team managers in a gladiator competition. Alice's gladiators have strength a₁, a₂, a₃...a_n and Bob's have strength b₁, b₂, b₃...b_m. Each round, Alice will select a gladiator from her team and then Bob will select one from his team and the chosen gladiators will fight.

If a gladiator of strength x fights a gladiator of strength y, the chance the one with strength x wins is given by x/(x+y). The losing gladiator is eliminated and then a new round begins with Alice and Bob selecting gladiators to fight. The competition ends when one of the teams has run out of gladiators.

What is the optimal play? In particular, suppose Alice always chooses to send in her strongest gladiator, how should Bob respond?

Its the exact same as last time, but this time the gladiators strengths are constant, rather than gaining confidence from the fights.

Bob Wins?

2010-05-07T12:23:00.000-07:00

People still read my blog, right? Whatever, I'm sure history will look back and thank me for all this, or something like that. Anyway, the gladiator battle problem has been up for long enough, lets take a look at the solution.

First, lets consider the a simple case, where Alice has one gladiator of strength A, and Bob has two gladiators of strength B₁ and B₂. Bob needs only decide which of the two gladiators to send first and the whole match is set.

If Bob sends gladiator 1 first, he wins with chance B₁/(A+B₁) and loses with chance A/(A+B₁). If he loses the first game, he then has a B₂/(A+B₁+B₂) chance to win the second game.

In total, the chance Bob has to win is given by:

B₁/(A+B₁)+AB₂/(A+B₁)(A+B₁+B₂)
=(B₁(A+B₁+B₂)+AB₂)/(A+B₁)(A+B₁+B₂)
=(A+B₁)(B₁+B₂)/(A+B₁)(A+B₁+B₂)
=(B₁+B₂)/(A+B₁+B₂)

Symmetric under exchanging B₁ and B₂, meaning that it does not matter who Bob chooses first. Actually, it is also equivalent to what Bob's chance of winning would be if he could merge his two gladiators into a single one of strength B₁+B₂ and just have that one fight.

This suggests that the whole "gladiator battle" this is just a complication of a much simpler problem. Lets replace the gladiators strengths with amounts of money. Now Alice and Bob each have total sums of money A and B, and each round they each place some money on the table, Alice placing x and Bob placing y. Alice is then given an x/(x+y) chance to win and Bob has a y/(x+y) chance to win. The winner of the round takes the money sitting on the table and then a new round begins. The game ends when one person has all the money. Now, in the "gladiator battle" version of the game, the players have restrictions on what amounts they are allowed to bet, but if we can prove that all betting strategies are equally good then we will have proven that the gladiator game restrictions do not matter.

Alright, when Alice places x, and Bob is choosing y, what y maximizes his potential gain? Bobs expected gain is x with probability y/(x+y) and -y with probability x/(x+y), so Bobs expected gain is:

x*y/(x+y)+(-y)*x/(x+y)

Clearly zero.

This means that all strategies for Bob are equally good, Bob can play the gladiator battle randomly and his probability of winning is just given by

&Sigma b_i/(&Sigma a_j+ &Sigma b_i)

Where a_j are the strengths of Alice's gladiators and b_i are the strengths of Bob's gladiators.

There is another, slightly more elegant, proof of this result. I like it a bit more because the first one felt very unsatisfactory, but this other one is very cool though rather weird.

Consider each gladiator to have an integer strength (this can be accomplished by approximating irrational strengths with rational ones, and then multiplying by denominators until everything is an integer). Each gladiator will have k beads assigned to them, where k is their strength. The beads are then all shuffled and placed on a string (you can imagine this as a bunch of coloured beads and each gladiator has their own colour). When two gladiators fight, whichever one has the furthest right bead wins the fight and then gets to claim all the beads owned by the defeated gladiator. It is not hard to see that this gives the correct probabilities of the battles and is a suitable representation of the entire tournament. In the end, only the rightmost bead matters, and the strategies are irrelevant.

Human intuition on this problem is a bit funny. Most anybody will tell you that it is obvious that you must always send your strongest first, and the occasional person will actually be convinced that you must use your weakest first, but the idea that it is irrelevant which you do is very hard for people to grasp intuitively.

Gladiator Battle

2010-04-30T12:12:00.000-07:00

Been some time since I had a new puzzle, and there are still two left in the paper "Games People Don't Play", though they are basically the same with a slight variation. Here is the first one:

Alice and Bob are competing team managers in a gladiator competition. Alice's gladiators have strength a₁, a₂, a₃...a_n and Bob's have strength b₁, b₂, b₃...b_m. Each round, Alice will select a gladiator from her team and then Bob will select one from his team and the chosen gladiators will fight.

If a gladiator of strength x fights a gladiator of strength y, the chance the one with strength x wins is given by x/(x+y). The losing gladiator is eliminated and the winning gladiator gains confidence from the fight, increasing the winning gladiator's total strength to x+y. Then a new round begins with Alice and Bob selecting gladiators to fight. The competition ends when one of the teams has run out of gladiators.

What is the optimal play? In particular, suppose Alice always chooses to send in her strongest gladiator, how should Bob respond?

It seems needlessly elaborate, especially given that in theory you have to solve for all possible values of a₁ through a_n and b₁ through b_m. It actually has a fairly elegant solution, but requires something of a mathematical transformation of the puzzle to reduce it to an easier setup.

XOR Solution

2010-04-17T11:36:00.000-07:00

OK, anybody who cares has certainly solved the number puzzle from last time. Lets work through the solution now.

For convenience, I'll state the five facts here

1. N has 2 digits XOR N is even
2. N contains the digit "7” XOR N is prime
3. N is the product of two consecutive odd integers XOR N is one more than a perfect square
4. N is divisible by 11 XOR N is one more than a perfect cube
5. N is a perfect square XOR N has 3 digits

Notationally, I'm going to use each statement with a letter 'a' or 'b' to refer to the first part or the second part of the statement. Specifically, when I say "statement 4a" I mean "N is divisible by 11", and "statement 2b" means "N is prime" and so on.
Alright, most people latch right onto 1 and 5 right away, to figure out how many digits the number has, and that is a sensible thing to do. Also note that 5a and 3b are exclusive, since a number cannot be a perfect square and one more than a perfect square (except for 1, I suppose, but it is easy to verify that 1 is not a solution to the puzzle). Looking at 3a, being the product of two consecutive integers means N=m(m+2) for m odd. That is N=m²+2m=(m+1)²-1 for m odd. So 3a says that N is exactly one less than a perfect even square. Thus, by 3, N is next to a perfect square, and so 5a is false.

This gives us that 5b is true and so 1a is false and 1b is true. But since N is even, and 3a says it is odd, 3b must be true. So we have N is even, has 3 digits, and is one more than a perfect square. Letting K=N-1, K=m² for m odd. Consider 4b now, if that is true then K is a perfect cube and so being a perfect cube and a perfect square means it is a perfect sixth power. We know 2⁶=64, 3⁶=729, and 4⁶=4096, so the only consistent thing would be if K=729. This would be N=730, which satisfies 2a and not 2b, while satisfying 4b and not 4a. This is the answer.

I recall some more elegant method of eliminating the false statements in 2 and 4, but I cannot remember it now. As usual, feel free to comment with any alternate methods you have.

Number Puzzle

2010-04-13T16:00:00.001-07:00

Time for another puzzle. This is a somewhat simple one I found somewhere random on the internets:

There exists an natural number, N, for which all of the following statements are true:

1. N has 2 digits XOR N is even
2. N contains the digit "7” XOR N is prime
3. N is the product of two consecutive odd integers XOR N is one more than a perfect square
4. N is divisible by 11 XOR N is one more than a perfect cube
5. N is a perfect square XOR N has 3 digits

What is N?

For the statements where the puzzle refers to digits, it is meant to be digits in a base ten representation of course.

When I found this puzzle, I dismissed it as being stupid and probably not worth the effort. I'm glad I gave it another shot though, the answer is somewhat pleasing to find. I'll admit its not amazing, but it shouldn't take more than 10 minutes and it is nice to work through the details.

Cards and Birthdays

2010-04-05T12:40:00.000-07:00

Time for an aside from puzzles that I got from "Games People Don't Play", and an aside from puzzles in general. This post is going to be about the birthday paradox and human intuition on probability.

You are probably familiar with the birthday paradox, but I will state it anyway, just to be clear. The paradox (as with most "paradoxes" it isn't really a paradox, but just something unexpected) is the answer to the question:

How many people do you need to have in a room before there is a greater than 50% chance that two of them have the same birthday?

If you ask this question of an average person, they will probably state something like 100 or so. If they have some basic math behind them, they might guess 365/2, so about 180. The actual answer is around 20 (i'll derive it later). The basic misunderstanding comes from the difference from the question posed and the following question:

How many people do you need to have in a room before there is a greater than 50% chance that one of them shares your birthday?

Note the difference, in the first question you just needed any two people to share a birthday, in the second question you needed somebody to land on a specific birthday. This results in a big difference since in the second case each person has a 1/365 chance of having your birthday, but in the first one each person has a k/365 chance of landing on somebodys birthday, where k is the number of people in the room before them.

I always say that humans have no good sense of probability, evolution never gave us a need to understand things like the Monty Hall scenario on an intuitive level. We also have a bad habit of noticing patterns where none exist, another byproduct of our evolutionary history. It is fortunate that we have developed the mathematical capabilities to handle probability for us, or science would never have gone anywhere.

The birthday paradox came up in a conversation I was having with my officemate the other day. He found a site that asked the question

What are the odds that you will ever see a shuffled deck of cards in the same order twice in your life?

Ignoring the fact that this question isn't really well-posed, it is something of an interesting question. The site basically gave an argument involving 52! (the number of ways to arrange the cards in the deck) and concluded the answer was "very small". Actually, I guess most of the post was on deriving 52! rather than the analysis of what to do with that number. My instinct was to agree with this conclusion, but then a part of my brain said "birthday paradox" and I had to wonder. The other part of me saying back "52! is like 10⁶⁵" was a persuasive counterargument though. It basically depended on what the 20 was to the 365 in the birthday paradox... was it the logarithm? the root? just plain old linear with a coefficient? seems it is time to do the calculation.

Suppose we have a list of N outcomes of some experiment, all equally likely (N=365 for the birthday paradox, or N=52! for this card problem) and we check the experiment k times. What are the odds that we see the same result twice? Alternately, how large does k have to be for the probability we have seen the same result twice to be greater than P?

For the card situation lets assume that k is about 30000, this is an approximation of checking once a day for 80 years. So for approximation purposes, N>>k>>1. Now, what is the probability that none of our experiments ever get the same result? the chance that the first result is new is 1 (or N/N), the chance the second result is new is (N-1)/N, the chance the third one is new is (N-2)/N and so on up to the chance that the k^th one is new is (N-k+1)/N. So the probability that we never see the same one twice is given by

p=N!/((N-k)!N^k)

We can use Stirling's approximation on this (since Stirling's approximation for n! is embarrassingly good by the time n is 10) to get

p=N^Ne^-N&radic (2&pi N)/((N-k)^N-ke^-N+k&radic (2&pi (N-k))N^k)
=(1-k/N)^k-N-1/2e^-k

This is basically in a form that is ready to solve for the birthday paradox. Setting N=365 you find that for k=20, p=0.589 (remember p is the chance that none of them share a birthday) for k=21 p=0.556, for k=22 p=0.524 for k=23 p=0.492. So we see that at 23 people it is more than 50% that two of them share a birthday.

In the case of N=52! we need a few more approximations. I initially tried to use the fact that (1+x)^m=1+mx for small x (since k/N is certainly small) but there is a problem with that. Writing out the next term it is actually (1+x)^m=1+mx+m(m-1)x²/2, so if m is as big as x is small (specifically m²x² is not negligible compared to mx) then this is not going to be valid. For our problem, x=k/N and m=k-N-1/2, so m²x² is like k² which is not small at all.

We can approximate the term (1-k/N)^k-1/2 as 1-k(k-1/2)/N as long as the next term is small. The terms look like 1, k²/N and k⁴/N², so the third term is small compared to the second as long as k² is small compared to N. This is true for our case, but I'll come back to that later.

Given the approximation (1-k/N)^k-1/2 = 1-k²/N, we have

p=(1-k/N)^-Ne^-k(1-k²/N)

We need to figure out what to do with (1-k/N)^-N, which is a number very slightly smaller than 1 to a very large negative power, so its a bit unpredictable. If you remember your first year calculus course, you will see quickly what to do, the limit as m goes to infinity of (1+x/m)^m is e^x (this is sometimes a definition of the exponential function). So we may approximate (1-k/N)^-N as e^k, giving us

p=1-k²/N

Thus, the probability that you see the same event twice is approximately k²/N. For k=30000 and N=52! this is about 10^-59, so we can confidently say it won't happen. Turns out the human intuition is correct in this case, the birthday paradox won't overcome crazy scenarios like 52!.

Asking the other question of "how large does k have to be to achieve some fixed P" like the birthday paradox's 50%, the answer is a bit funny. You find that to achieve a 50% chance of seeing the same result twice you get k=&radic (N/2), so it would appear that the birthday paradox goes as the square root on N, rather than the logarithm or something else. However, this is technically mistaken, since we needed k² to be much smaller than N in our approximations, this answer is invalid. It is correct to say that the birthday paradox asymptotes to something similar to &radic N, since if it is much weaker than that (like logarithm or cube root or something) our approximations become good again and you get the answer of square root.

More Frungy

2010-04-01T13:02:00.000-07:00

Time to slack from work, and instead post the solution to the card problem from last time. In standard form, it is easiest to simply solve the simpler case first. For general notation, we will assume the deck has N red cards and N black cards, the final goal is to solve N=26.

First, the N=1 case. There is little point in betting on the first card, the adversary will just make you wrong anyway, so after the first card comes by, you know what the second card is. You bet everything on the second card, are correct, and end with $2.

Now for N=2. There is actually still no point in betting on the first card (this is a pretty general result), so lets say the first card is red. Now there is 1 red and 2 black in the deck. One might be inclined to say there is no point in betting here, but then the adversary will surely show us a black card the second time and we are in the N=1 case. Really, the fact is we would be very happy is the adversary showed us the second red card on the second round, so happy that we might be willing to pay him a small amount of money to make it happen.

Suppose you bet $0.1 on the second card being black, then if it is black, you have $1.1 and are in the N=1 case, so you get to double that to $2.2. If the second card is red, you have $0.9, but now there are only black cards in the deck, so you get to quadruple that and end with $3.6. Clearly the adversary will let you end with $2.2. Now suppose we instead bet $0.5 on the second card being black. If it is black we have $1.5 and get to double that to $3. If it is red we have $0.5 and get to quadruple that to $2. Clearly the adversary will let us have $2.

Alright, we need a middle ground. Bet x on the second card being black. If it is, we have 1+x and we get to double that to 2+2x. If it is not black we have 1-x and we get to quadruple that to 4-4x. The adversary will give us whichever is lower, and since one is an increasing function and the other is a decreasing function, the lowest one is maximized when they are equal. Solving 2+2x=4-4x we have x=1/3. So we should bet 1/3 on the second card being different than the first one and we are guaranteed to end with $8/3.

Note that in the solution to the N=2 case the answer comes out path independent, in that after two black cards and one red card have come by, you have $4/3 no matter if it was BRB or BBR (I'm sort of assuming that the adversary chooses to show black cards rather than red when the situation is symmetric). Naturally it has to be path independent, if the different paths gave different amounts of money, the adversary would send you on the worst path he can find. Due to this, it is a general feature that the solution for general N be path independent.

Now let us try to solve with general N. As we have seen, since the solution is path independent on how the adversary shows us cards, there must be a function f(r,b) that represents how much money we have when r red cards have gone by and b black cards have gone by. Clearly f(r,b) could depend on the specific value of N we use, so it really should be f(r,b,N), but I'm going to suppress that last variable. We also know that f(0,0)=1, and f(r,b) must equal f(b,r) by a similar argument to the one that shows path independence, and f(N,N) is the answer we seek.

Suppose we have see r red cards and b black cards go by, so we have f(r,b) money according to our strategy, and we now bet x on the next card being red (if we are instead betting on black, we just let x run negative). If the next card is red, we have f(r,b)+x money and if it is black we have f(r,b)-x money. This means that:

f(r+1,b)=f(r,b)+x
f(r,b+1)=f(r,b)-x

For some value of x. Eliminating x, we have

2f(r,b)=f(r+1,b)+f(r,b+1)

Similar to the relation for Pascal's triangle. To make it look a bit more familiar, lets define g(r,b) by f(r,b)=2^r+bg(r,b), then g obeys the relation

g(r,b)=g(r+1,b)+g(r,b+1)

Now that looks like the Pascal relation, but its backwards. Next lets define h(r,b)=g(N-r,N-b), so h counts how many cards are left in the deck rather than how many cards we have seen go by. Then h obeys

h(r,b)=h(r-1,b)+h(r,b-1)

Perfect for solving as a previously solved problem. But since we knew f(0,0)=1, this means we know h(N,N)=1, so h is a bit backwards. We simply modify this by defining p(r,b)=h(r,b)/h(0,0). Now p obeys

p(r,b)=p(r-1,b)+p(r,b-1)

and p(0,0)=1, so p is the Pascal function, that is

p(r,b)=(r+b)!/(r!b!)

We can find h(0,0) by noting that p(N,N)=h(N,N)/h(0,0)=1/h(0,0), so h(0,0)=1/p(N,N), giving

h(0,0)=N!N!/(2N)!

so that we have h

h(r,b)=p(r,b)h(0,0)
=(r+b)!N!N!/(r!b!(2N)!)

This gives us g

g(r,b)=h(N-r,N-b)
=(2N-r-b)!N!N!/((N-r)!(N-b)!(2N)!)

Finally, we get f

f(r,b)=2^r+bg(r,b)
=2^r+b(2N-r-b)!N!N!/((N-r)!(N-b)!(2N)!)

ugh.

At least we really only care about 1 thing, f(N,N), its simple enough:

f(N,N)=2^2NN!N!/(2N)!

Which is just 2^2N divided by _2NC_N. For N big enough to use Stirling's approximation (which 26 is), we have

f(N,N)=2^2NN^2Ne^-2N(2&pi N)/((2N)^2Ne^-2N &radic (2&pi 2N))
=&radic (&pi N)

Actually comes out quite simple. For N=26 this is about 9.

So this actually is the complete construction of the strategy. At any given time you have seen r red and b black cards come by, you have f(r,b) money left, and you should bet f(r+1,b)-f(r,b) on red (or, equivalently, f(r,b+1)-f(r,b) on black) and you will end with f(N,N) money. Actually performing the strategy can be done in a slightly different way though.

Suppose you have K assistants, where K is the number of possible configurations of the cards in the deck (that is, K=_2NC_N). Each assistant is given 1/K money to start and is told a list of R's and B's that could correspond to the cards in the deck (for N=2, the assistants are told RRBB, RBRB, RBBR, BRRB, BRBR, BBRR), and you let them all bet simply assuming that their own list is correct. Precisely one of them will be correct and will double his money 2N times (once for each card). The rest all lose their money. The correct assistant ends with 2^2N divided by _2NC_N money, exactly f(N,N).

Lets try this for N=2, we have our 6 assistants which will be labeled as follows:

1.RRBB
2.RBRB
3.RBBR
4.BRRB
5.BRBR
6.BBRR

Each assistant is given $1/6.

This game starts, and assistans 1,2,3 bet their $1/6 on red while assistants 4,5,6 bet their $1/6 on black. We (the real holder of the $1) add this up and bet a net zero. Suppose the first card is red. This eliminates assistants 4,5,6 and assistants 1,2,3 now all have doubled their money to $1/3. We have a total money of $1.

Next card, assistant 1 bets his $1/3 on red and assistants 2 and 3 bet their $1/3 on black. We add this up and bet $1/3 on black. Suppose the next card is black. This eliminates assistant 1 and doubles assistants 2 and 3's money to $2/3. We have a total money of $4/3.

Next card, assistant 2 bets his $2/3 on red and assistant 3 bets his $2/3 on black. We add this up and bet nothing. Suppose the card is black. Assistant 2 is eliminated and assistant 3 doubles his money to $4/3. We have a total money $4/3.

Final card, assistant 4 bets his $4/3 on red. We add this up and bet $4/3 on red. We double our money to $8/3.

This game also has one other neat feature if you actually play it. All betting strategies are fair, as long as you never bet on a card that does not remain in the deck. That is to say, in any given position of red and black cards left, no matter what you bet on what card coming next, your expectation of final money (against a shuffled deck, not an adversary) is the same, as long as when the deck is out of one type of card you bet maximally on the card colour that is left.

Card Betting

2010-03-27T11:48:00.000-07:00

Continuing on my plan of posting the puzzles I found in the paper "Games People Don't Play", I have a card flipping puzzle this time. Back when I started this blog I posted a card flipping problem that Bart had told me, and the puzzle this time is something of a continuation of that one:

There is a deck of 52 cards, 26 red and 26 black. You will be playing a game where you bet on what is the next card in the deck. You begin with $1 and can make a bet of any real number between zero and the amount of money you have on whether the next card in the deck is red or black. The top card of the deck is then revealed and if you were correct you gain the amount you bet, if you were incorrect you lose the amount you bet. Then the game continues with betting on the next card in the deck. The game ends when there are no cards remaining in the deck to bet on. What is the optimal betting strategy assuming that the deck is being arranged by an adversary?

I really like the sort of puzzle that seems flat out impossible to do anything at first, putting the player up against an adversary seems like a pretty insurmountable obstacle, but you still have some wiggle room.

Alice Wins?

2010-03-21T13:24:00.000-07:00

I guess I should put up the solution to the second two numbers problem. The fact that I ask for an equilibrium strategy sort of gives something away I suppose, because in the first one there is no equilibrium strategy (Alice can make Bobs winning chance 1/2+&epsilon for any positive &epsilon so there is no optimal one). To begin, what is the strategy space for Bob? Bob sees a number, x, and must decide if that number is larger or smaller based simply on that number. All Bob can do is select a function f(x) to give him the probability that he says x is the larger number. The solution to the last puzzle strongly suggests that f(x) should be a strictly increasing function, but it is worth noting that if f(x) is simply 1/2 everywhere, then Bob is certain to get 50% on this game, so there is no way Alice can push him lower than that.

Suppose Alice is given f(x) (Bobs strategy) and is given the two numbers y and z from (0,1) (also, we may as well assume z>y). Now, if Alice chooses to show Bob y, Bob has a 1-f(y) chance to win, and if Alice chooses to show z, Bob has a f(z) chance to win. Thus Bobs chance to win (if Alice knows f(x)) is given as:

min(1-f(y),f(z))

Now we must integrate this over all space of y and z. The natural integral would be &int &int dy dz with both going over (0,1), but this does not work because we have already assumed z is the larger of the two numbers. We should simply restrict the integral to z &isin (0,1) and y &isin (0,z) and multiply by 2 to take care of the other half of the region where y happens to be larger. Bobs chance to win is given as

2 &int &int min(1-f(y),f(z)) dy dz

with y from 0 to z and z from 0 to 1.

The next thing to know is that Bob is trying to maximize this integral. We must select an f(x) to make this as large as possible. Remember we already know that with f(x)=1/2, we trivially get 1/2 for the answer, so really we need only ask if we can make it larger than 1/2. You can try some functions out for a while, but in the end you will see that nothing will integrate to more than 1/2.

We can prove that Bob cannot get better than 1/2 by using 2 features about the min and max functions:

1.min(a,b)+max(a,b)=a+b
2.min(a,b) &le max(a,b)

Now we define

P=2 &int &int min(1-f(y),f(z)) dy dz
Q=2 &int &int max(1-f(y),f(z)) dy dz

integrated over y from 0 to z and z from 0 to 1 as before. We seek to prove that P &le 1/2 for all choices of f.

Fact 2 from before shows us right away that P &le Q, and fact 1 gives us

P+Q=2 &int &int (1-f(y)+f(z)) dy dz
=2 (&int &int 1 dy dz - &int &int f(y) dy dz + &int &int f(z) dy dz)

The first integral is simply 1/2 (the area of integration) and in the third integral you can do the y integral separately to get &int zf(z) dz integrated from 0 to 1. For the second integral we simply rewrite the integration region from y &isin (0,z) and z &isin (0,1) to z &isin (y,1) and y &isin (0,1) so we can do the z integral first to get &int (1-y)f(y) dy integrated from 0 to 1. We currently have

P+Q=1 - &int (1-y)f(y)dy + &int zf(z)dz

But using the substitution z=1-y the two integrals are trivially identical for any f(x). Therefore,

P+Q=1

Now since P &le Q we have (by adding P to both sides) 2P &le P+Q so 2P &le 1 therefore P &le 1/2 as we sought.

OK great, so if Alice knows Bobs f(x), there is no way Bob can choose an f(x) that guarantees to get any better than 1/2. So if there is an equilibrium strategy, it must be 50/50. But is there one? Can we construct a strategy for Alice that makes sure Bob cannot get better than 1/2 even if we have no idea what f(x) he chose? We can, and its actually what one would instinctively do if one were playing this game.

Consider you are Alice and you are handed the numbers 0.1 and 0.5, which one would you show Bob? The obvious choice is 0.5, 0.1 looks too obviously the low one. How about 0.8 and 0.4? Less obvious, but it would seem the rational guess is 0.4. How about 0.7 and 0.4? again 0.4, 0.7 has less space above it than 0.4 has below it. How about 0.8 and 0.6? 0.6 is pretty clearly better. How about 0.7 and 0.3? now it seems they are symmetric, no good way to choose. How about 0.6 and 0.4? again symmetric.

See what the strategy is? Just show Bob whichever number happens to be closest to 0.5. Now, if we obey this strategy, what is Bobs chance of winning? First let us rescale the numbers down by 0.5 so that the two numbers, y and z, range from -1/2 to 1/2 and we show Bob whichever one is closer to zero.

Consider the y-z plane in the box y &isin (-1/2,1/2) z &isin (-1/2,1/2). The numbers we get select a point in this region. Which number is y and which is z doesn't matter here, select which is which at random.

Divide up the region into 4 pieces using the lines y=z (from bottom left to top right) and the line y=-z (from top left to bottom right). The 4 regions are "top" (where z>0 and y is between -z and z) "bottom" (where z<0 and y is between -z and z) "left" (where y<0 and z is between -y and y) and "right" (where y>0 and z is between -y and y). If our two numbers put the point in either "top" or "bottom" we show Bob y. If the point is in "left" or "right", we show Bob z.

Suppose we have a point in "top". We show Bob y and he has to guess that y is the smaller number. The chance of him doing so is 1-f(y). For all points in "top", we would integrate this to get the total probability of Bob winning, given a point in "top". That is, when the point lands in "top", Bobs chance of winning is &int 1-f(y) integrated over "top". In "bottom" we show Bob y and he must guess it is the larger number. He does this with probability f(y) so, 1/4 of the time, Bobs chance of winning is &int f(y) integrated over "bottom". Note that &int f(y) in "top" is the same as &int f(y) in "bottom", since they both have the same y values.

Using the same argument for "left" and "right" we get Bobs chance of winning is (&int 1-f(y) over "top")+(&int f(y) over "bottom")+(&int 1-f(z) over "right")+(&int f(z) over "bottom"). The integrals of unknown functions all cancel, leaving &int 1 over "top"+&int 1 over "bottom" giving 1/4 each (their areas) for a total of 1/2.

Simply put, if Alice shows Bob 0.3 (say), and Bob knows this number is the one that is closer to 1/2, then the other number is equally likely to be in (0,0.3) or (0.7,1) and Bob cannot tell those apart.

Thus if Alice follows the strategy "show Bob whichever number is closer to 1/2", then Bob cannot do better than 1/2 no matter what f(x) he chooses. If Bob uses the strategy f(x)=1/2 (so, "flip a coin") Bob cannot do worse than 1/2 no matter how Alice chooses the number to show. So this gives the equilibrium strategy (or, at least, an equilibrium strategy).

I find it funny that if you do this game with real people, the Alice player will probably typically hit on the correct strategy naively, even though they will then likely try to follow it up by "out-thinking" the other player, because thats just what humans do.

Two More Numbers

2010-03-15T08:56:00.000-07:00

Alright, now that the two numbers puzzle is out of the way, time for the follow-up. I first learned this puzzle in a paper called "Games People Don't Play" which I found on the comments at the xkcd blag:

Two numbers are selected uniformly at random from the interval (0,1) and shown to Alice. Alice must select one of these two numbers and show it to Bob. Bob must then guess if Alice has shown him the larger of the two or the smaller of the two. What is the optimal (equilibrium) strategy for the players?

This time Alice does not get control of the two numbers, and Bob is aware of the distribution, but Alice gets to choose what number Bob sees, so who gains the advantage from those changes?

Only A Little

2010-03-13T11:47:00.000-08:00

Time for the solution to the Two Numbers problem. I suppose I could just state the solution right away, but I like to do something of a derivation first.

First of all, consider the results of the following strategy for Bob:

If the number you see is greater than zero, guess it is larger, if the number is less than zero, guess it is smaller

Easy enough to implement, if both numbers that Alice wrote down are positive, then you are still 50/50. If they are both negative then you are again 50/50, but if one number was positive and one was negative, then you are guaranteed to win.

Alright, thats all well and good, naturally if Alice knows you are doing this, then she won't ever write down a positive and negative number together of course, so this is not actually guaranteed to give you a better than 50% chance of winning the game. Now, instead of greater than/less than zero, why not use a random number K. Perform the following strategy:

Select a nonzero probability distribution over the reals f(z). After Alice writes down the numbers, select a number K using f(z). If the number you see is greater than K guess it is the larger one, if the number you see is smaller than K then guess it is the smaller one.

By nonzero probability distribution I mean that f(z)>0 always and &int f(z)dz = 1 when integrated over all the reals. Basically, the strategy is to assume that the unseen number is near K.

Suppose Alice writes down x and y with y>x, then if x>K or K>y you are simply 50/50, but if y>K>x you win the game 100%. The chance of you winning is therefore

&int f(z)dz+(1-&int f(z)dz)1/2
=1/2+1/2&int f(z)dz

Where the integral is between x and y (giving the chance K lands between x and y). Since f(z)>0 always, this is greater than 1/2 in all cases and is a valid solution. Naturally, if Alice knows f(z), she can make that integral as small as she likes, but she cannot make it non positive.

One can make a slightly more general (but not actually any better) solution as well. Consider that Bob looks at the number before choosing K. Then the chance that K will be less than x (and thus guess x is larger) is &int f(z)dz integrated from -&infin to x. Let p(x) be that number (the probability that we say x is larger). Clearly we have p(x) positive, increasing, and 0 at -&infin and 1 at +&infin .

Let Alice choose number x and y with y>x. Now the chance Bob wins given some function p(x) is 1/2 (the chance he is given y) times p(y) (the chance he says y is larger) plus 1/2 (the chance he is given x) times 1-p(x) (the chance he says x is smaller). thus giving

1/2 p(y)+1/2(1-p(x))
=1/2+1/2(p(y)-p(x))

Not surprising given that p is the integral of f from before.

Anyway, the only thing that we need to demand of p(x) is that is be strictly increasing and bounded between 0 and 1. It does not matter that it goes to 0 at -&infin or 1 at +&infin (though, I guess it might as well). So the strategy of saying the number you see, x, is greater with probability p(x) is more general than the strategy of picking K from f(x) (though not any better, even if it is more general). Again, given p(x) Alice has the power to make p(y)-p(x) as small as she wants, but she can never stop it from being positive.

Two Numbers

2010-03-11T12:31:00.000-08:00

So, about a year ago, I posted a puzzle based on the two envelope paradox. I had intended to finish that one off with another puzzle, but then I guess I forgot to. Now I have learned about a follow up to that puzzle, but I can't exactly post i until I have posted the original. Anyway, here we go:

Alice writes down two distinct real numbers and puts them into two separate envelopes. Bob then selects one of the envelopes to open randomly (50-50 chance) and looks at the number. Bob must then guess whether the number he is looking at is the larger of the two or the smaller of the two. Find a strategy for Bob that is guaranteed to succeed more than 50% of the time, no matter what numbers Alice chooses.

Its very similar to the final problem I posted a year ago, so I'll give the solution out in the next few days so we can move on to the real problem. Its trivial for Bob to do 50% simply by flipping a coin to decide his answer, but doing better just seems crazy. If you need, feel free to assume Alice is choosing her numbers from an unknown but well defined distribution over the reals.

Two Answers

2010-03-07T23:17:00.000-08:00

The puzzle of the three princesses has been up far too long for how simple it is, I suppose its time for the solution.

Its actually quite easy, first number the princesses 1, 2, and 3 and then ask princess number 1:

Is princess 2 older than princess 3?

Then, based on the answer you get

yes: marry princess 3
no: marry princess 2

Easy enough, if princess 1 was the truth teller, then you aim to marry the younger one. If princess 1 was the liar, you aim to marry the older one. If princess 1 was the middle sister, then it does not matter who you marry, as long as it is not her.

I suppose that it was a bit of a lie when I said this is not a meta-question, since asking about the "truthiness" of other sisters is something of a meta-question, and asking about their ages is equivalent to asking about how much they tell the truth in this problem. I don't know though, the answer seems elegant enough, and its hardly going to count as a trick or "communicating badly" to have an answer involve their ages when it is said so clearly in the problem.

Anyway, yea, thats the answer as I know it, if you have any other possible answers feel free to say them in the comments.

Three Princesses

2010-02-26T12:31:00.000-08:00

New puzzle time, I found this one some time ago on the forums at xkcd, but I wasn't sure if it was the style of puzzle I like to have here. Upon further consideration, and a lack of new puzzles to put up, I have decided that this is a good puzzle after all.

You are the most eligible bachelor in the kingdom, and as such the King has invited you to his castle so that you may choose one of his three daughters to marry. The eldest princess is honest and always tells the truth. The youngest princess is dishonest and always lies. The middle princess is mischievous and answers questions with either yes or no, however she pleases, ignoring the question asked.

As you will be forever married to one of the princesses, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with them.

The problem is that you cannot tell which sister is which just by their appearance, and the King will only grant you a single yes or no question which you may only address to one of the sisters. After your question, you must select a princess to marry. What yes or no question can you ask which will ensure you do not marry the middle sister?

Its mostly a standard "knights and knaves" scenario, and I typically dislike these sorts of puzzles because the answer is invariably some bizzare meta-question (that is, a question of the form "If I were to ask that person '(insert question here)', what would their answer be?"). However, the 'intended solution' to this problem has no meta-questions involved, actually it is quite elegant. Given the nature of the question, it probably has a bunch of other solutions too, so it could also be interesting to see if anybody posts an answer I haven't seen.

They'll Get There Eventually

2010-02-17T10:52:00.000-08:00

Alright, the Sending Scouts Into The Desert problem has been up there with no solution for far too long, I suppose its time to post the solution. I'm going to proceed assuming that you have not already read the solution over at cut the knot and basically steal their derivation.

We will do the solution case by case first. For N=1, it clearly takes two pieces, one on the first line and one on the second line. For N=2 it takes 4 pieces, 3 on the first line and 1 on the second line. N=3 is a bit less trivial, but it won't take long to find that you need 8 pieces. So, so far the pattern goes 2,4,8, so it looks like N=4 should take 16. This is actually not the case, if you try it you won't be able to get to N=4 with less than 21 pieces (cut the knot says you only need 20, but I am reasonably certain that they have made some error, I cannot find anything better than 5 on the first line + 5 on the second line + 5 on the third line + 5 on the fourth line + 1 on the fifth line).

For N=5 the situation is even more interesting though, you cannot get to the fifth line with any finite number of pieces. To see this, let us consider a function that maps board configurations onto integers. We will later arrange the function so that legal moves do not increase the value of the function, so you cannot reach a higher-valued configuration from a lower-valued one, and use this to prove that we cannot reach the fifth line.

Let us assign a number to each square of the checkerboard, and the function will simply add up the numbers at the locations where we have pieces. We will arrange the numbers so that legal moves never increase the value of the function. Let us assume that somebody claims to have reached a particular square on the N=5 line of the board. We will assign that square a value 1. The four squares that neighbor it will be assigned a value x (we will fix x later). The next 8 neighboring squares will be assigned value x². The next 12 neighboring squares will have value x³ and so on out to infinity. More concisely put, we have the "master square" of value 1 and a square that is K spaces away (taxicab metric) from the master square has value x^K.

Let us consider a generic legal move, where piece A jumps piece B. There are three types of things that could have happened from this. First, A could have landed closer to the master square than it was before. In this case, A started on x^m, while B started on x^m-1, then A ended on x^m-2. To ensure that the function is nonincreasing, we need

x^m-2 ≤ x^m-1+x^m

The second type of move has piece A moving further away from the master square. In this case, A started on x^m and B on x^m+1, with A ending on x^m+2. For a nonincreasing function, we need to have

x^m+2 ≤ x^m+1+x^m

The third type of move has piece A staying the same distance from the master square. In this case, A started on x^m and B started on x^m-1, with A ending on x^m. So we need to satisfy

x^m ≤ x^m-1+x^m

This condition is satisfied easily if x is a nonnegative number.

Let us assume that the first condition is an equality (this means that moves toward the master square will conserve the value of the function, rather than decrease it). Dividing out x^m-2, this equation solves to 1-x-x²=0, meaning that

x=(√5 - 1)/2

There is another root, but it was discarded because x must not be negative. This x is actually the inverse of the golden mean. The last equation remaining is also satisfied by this choice of x, as you can confirm easily.

Now, supposing as before that the master square is on the fifth line, it is the place on the fifth line that somebody claims that they can reach using some path of legal moves. This configuration has value 1 (or more, if they had extra pieces lying around), so their initial configuration must also have value 1 or more. What is the maximum value you can get with a configuration of pieces in your base to start? You have at most 1 piece on x⁵, at most 3 pieces on x⁶, at most 5 pieces on x⁷, at most 7 pieces on x⁸, and at most 2n+1 pieces on xⁿ⁺⁵. Thus, the most value of pieces you can have is

Σ (2n+1) xⁿ⁺⁵

the sum running from 0 to infinity (actually this isn't really the most you can have, its actually more than you can have with any finite number of pieces, but its how much you could have with an infinite number of pieces).

We can simplify the sum to

2x⁶Σ nx^n-1 + x⁵Σ xⁿ
= 2x⁶ d/dx Σ xⁿ+x⁵Σ xⁿ

Of course, the sum &Sigma xⁿ is 1/(1-x) (since x is between -1 and 1) so we have

2x⁶/(1-x)²+x⁵/(1-x)

Now we use 1-x=x² (the quadratic that x solved) to simplify this to

2x²+x³
=x²(2+x)
=(1-x)(2+x)
=2-x-x²
=1

Therefore, no finite number of pieces can have total value 1, so no finite number of pieces can make a series of legal moves that ends with a piece five lines deep.

I suppose one can still imagine an infinite number of pieces doing it, but it will also take them an infinite number of moves, so its not clear that it really makes any sense to talk about such a thing.

Sending Scouts Into The Desert

2010-02-02T15:49:00.000-08:00

The problem I have this time is a bit of a weird one, I mostly only show it because it has an amazing solution and proof. I first found this puzzle at Cut The Knot, which is something of a math puzzle page.

Consider an infinite 2-dimensional checkerboard. The upper half of the board is called the "desert" and the lower half of the board is called the "base", and there is a line across the middle that divides the two (just to be clear, there are no squares between the desert and the base, every square is either in the desert or the base).

You will be playing a one player game on this board. First you set up as many checkers anywhere you want in the base (each square may only be occupied by one checker). Then you begin making your moves. A move consists of a checker jumping another single checker that is orthogonally adjacent to it and landing on the space on the other side (which was unoccupied before). The checker that is jumped over gets removed.

The goal is to get one of your pieces as far into the desert as possible. Find how many pieces it takes to get N spaces into the desert.

That may have been a bit awkward to read, however there is a nice applet at Cut The Knot that will allow you to play this game. That page also has the solution to this problem, so don't scroll too far down unless you are ready to see the solution. The solution that is there is quite well written though, and when I post the solution to this next time I'm basically just going to be following his derivation.

The Value Of One Bit

2010-01-18T13:03:00.000-08:00

I was looking over my "solution" threats, and it seems that about 90% of them begin with "time to post the solution to", so I figure I'm about sick of that. Sick of it this week anyway, next time I'll be back to it. Anyway, now that I have actually began the post with something different, time to post the solution to the bit in a bottle problem.

First I will give my formulation of the solution, and then I will show that it is optimal in a sense (a pretty convincing sense as well, not just some esoteric one). First, consider what happens if you just bet heads all the time. Your total money will simply preform a random walk on the integers starting with N, and will terminate if it ever hits zero. With probability 1, it will hit zero in finite time.

Now, I will construct two strategies, first define the following strategy

Strategy H: Every game, bet heads until you have reached $0 or $2N. If you ever reach $0 or $2N, quit playing.

Similarly, define a strategy for tails

Strategy T: Every game, bet tails until you have reached $0 or $2N. If you ever reach $0 or $2N, quit playing.

Now, we can show that one of these strategies will hit $0 and the other will hit $2N (this should be pretty intuitive, but lets prove it anyway). For a particular sequence of flips, let M(S,k) be the amount of money that strategy S will have after k flips. Then I claim that

M(H,k)+M(T,k)=$2N

This is easy to prove by induction, as it is true when k=0 and every time strategy H gains $1, strategy T loses $1 and vice-versa. The strategies also terminate at the same time, as failing to do so would violate the equality. It is theoretically possible that the strategies do not ever terminate, but that has zero probability of happening.

Now, the question we ask the genie is simple. First define strategy H for the genie, then ask:

If I follow strategy H, will I end with $0?

If the answer is yes follow strategy T, if the answer is no follow strategy H. This guarantees that you will end with $2N (where "guarantees" means "with probability one"). You can also change strategy H to any specific betting sequence rather than all heads if you like, as long as strategy T is the compliment of that sequence, this will still work.

Next I want to prove that this solution is optimal. It might seem surprising that we can optimize over the space of all possible questions, since math usually is not very good at handling human language. To deal with this, first consider C to be the set of all the possible coin flip results, so C contains things like HHTHH..., THTTH.., TTTHT..., and so on. Next consider a possible yes or no question, denoted Q, that for every element of C the question must answer exactly "yes" or "no". Thus Q partitions C into two disjoint subsets, called Y and N. Really, any Q is equivalent to selecting the sets Y and N and asking the genie "is the coming sequence of coin flips in Y?" So, to optimize over all questions Q, we really just need to optimize over choice of sets Y and N, and it is less surprising that math can handle that.

Before moving on, I must state an obvious but important fact of probability theory. Consider we have two disjoint events, X and Y (that is to say, exactly one of them must happen (thats not actually what disjoint means, but I don't know the correct term)), and a third event called A. Let P(x) is the probability that event x happens, and P(x|y) is the probability that event x happens given that event y happened. Then, the probability that event A happens can be written as:

P(A)=P(A|X)P(X)+P(A|Y)P(Y)

That is, A must happen with X or Y, so we calculate the chance it happens with X plus the chance it happens with Y. We need not subtract the chance it happens with both, as X and Y are disjoint. It is easy to generalize this to more disjoint events X,Y,Z,... We can also make a similar statement about expectation values, let E(A) be the expectation value of some variable A and E(A|x) is the expectation value of A given that event x is true. Then for disjoint events X and Y we have:

E(A)=E(A|X)P(X)+E(A|Y)P(Y)

An intuitive result, to be sure, but an important one anyway.

OK, now that that is out of the way, the next important step in the proof is to consider what will happen with no genie. Suppose you have some strategy S, and after k flips the strategy has an expected value E(S,k). The expected value will be determined by the chance that you went up a dollar on that flip (call that P(+)) and that chance that you went down a dollar on that flip (call that P(-)), and the chance that your strategy had told you to stop (call that P(O)). Specifically:

E(S,k+1)=(E(S,k)+1)P(+)+(E(S,k)-1)P(-)+E(S,k)P(O)

It is clear that P(+)+P(-)+P(O)=1 (since every round you either gain a dollar or lose a dollar or stop), and also P(+)=P(-) since without access to a genie we have no knowledge about the coin flips. This means that:

E(S,k+1)=E(S,k)

So, E(S,k) is a constant, and that value must equal $N, since E(S,0) is $N. This proves that with no genie, all strategies have the same expectation value after a fixed number of flips. Note that something funny happens if you just let k=∞ since strategies such as "play until I run out of money" are guaranteed to have zero money at the end, even though after a finite number of flips there is a chance of the player having a large amount of money for the time being (this is known as the "gamblers ruin").

Alright, now let us find what is the best we can do given our genie scenario. First let x represent the coming sequence of coin flips, the genie knows the value of x. Consider that we have a strategy specified by a question Q (which simply selects the sets Y and N), a strategy S(Y) (which is what we will do if the genie tells us x is in Y), and a strategy S(N) (which is what we will do if the genie tells us x is in N). We want to find E(S,k), the expectation value of our strategy S (=(Q,S(Y),S(N))) after k flips. Letting Y represent the event "x is in Y" and N represent the event "x is in N", we see that Y and N are disjoint events, so that:

E(S)=E(S|Y)P(Y)+E(S|N)P(N)

I really should have some k's in there also, but they are going to get cumbersome so I am just going to drop them for now. Now, E(S|Y) is just E(S(Y)|Y), since S says to play S(Y) when Y is true, also E(S|N)=E(S(N)|N) for the same reason. That is to say

E(S)=E(S(Y)|Y)P(Y)+E(S(N)|N)P(N)

To get any more information out of this, consider again what would happen to us with no genie. We could just play S(Y) anyway, but we already know that E(S(Y))=$N (one would expect that E(S(Y)|Y) would be higher, since then we also know that x is in Y, but if we just play S(Y) with no other information then its expectation value is $N) (I must say this is only true after k flips, if the number of flips is infinite weird things might happen). How else could we calculate E(S(Y))? we could just consider if x is in Y or N, specficially

E(S(Y))=E(S(Y)|Y)P(Y)+E(S(Y)|N)P(N)

That is the value of strategy S(Y) when Y is true plus the value of strategy S(Y) when N is true (remember, we have no genie right now). Now since E(S(Y)|N) cannot be negative, and P(N) cannot be negative, that second term cannot be negative. Thus we have a bound on E(S(Y)|Y)P(Y), given by

E(S(Y)|Y)P(Y) ≤ $N

Similarly, switching Y for N we have

E(S(N))=E(S(N)|Y)P(Y)+E(S(N)|N)P(N)

and therefore

E(S(N)|N)P(N) ≤ $N

We can put this together in our last equation for E(S) to get

E(S) ≤ $2N

Proving the optimality of the solution presented earlier. It appears that the value of one bit is to exactly double your cash. If you can instead ask the genie a question with possible answers 1,2,3,... up to some fixed K then you can extend this proof to show it is optimal to multiply your money by K.

Naturally, it is possible to get other strategies to end with more than $2N, they just cannot guarantee ending with that much. Even with no genie one can simply play the game and only quit if you hit $0 or $3N, you might end with $3N in this case, but it cannot be guaranteed. I will also point out that the proof relied on the game not taking an arbitrarily long amount of time, my intuition is that the result is still valid even without that assumption, but I do not see a good proof.

I do like this solution in that it is practical, one would reasonably use it if actually presented with this situation, and the genie does not even need to do an infinite amount of work (probably not anyway, its possible that the random walk never terminates, but thats probability zero). The genie can even be replaced by a mathematically competent human who simply has access to the coming flips.

There is a harder problem posed of the xkcd forums where losing a flip costs you a $1 and winning a flip gains you $(1-q) where q is a small positive number. I have not made any real progress to finding a solution to this problem, but anything involving random walks seems risky, so another approach might be needed.

Bit In A Bottle

2010-01-14T13:58:00.000-08:00

New puzzle time I suppose. This one looked like it was a bit of a silly one, but it turns out that there is a bit more interesting math in it than I expected. I first found this on the forums at xkcd:

You are playing a game where you are betting on the outcome of coin flips. Playing the game costs $1 and you get to guess either heads or tails. A coin is then flipped and if you guessed correctly you win back your $1 and another $1, if you guessed wrong you lose your $1. You may play the game as many times as you want as long as you have the money to continue, or may quit anytime. Before the game, you have access to a genie that will answer any one yes/no question about the coin flip game. The genie knows the results of all the coming flips. Given that you start the game with $N, find a strategy that maximizes your winnings.

Earlier I had posed the problem stating that the genie knew the future, but that can cause weird possible questions involving not having a well posed question. Anyway, the intention is that the genie be capable of answering your question solely knowing what the coin flips are going to be. If a genie who knows the outcome of random events bothers you, we can instead suppose all the flips have been determined ahead of time and the genie simply has access to all the results.

Clearly with no genie, the only thing you can do will have an expected final outcome average of $N, since the game is fair for all strategies, so the question is to find out how much the one bit of information the genie gives you is worth. One thing I found interesting about this problem is that you can also prove optimality of the correct answer.

Giving Cards

2010-01-11T16:29:00.000-08:00

Time for the solution to the card game from last time. I suppose the standard thing to do is consider simpler cases.

In the case when N=1, the start player must simply take the card (if they are playing optimally, anyway). Next, if N=2 it is optimal to give the 1 card and take the 2 card.

For N=3 we have a real choice. We can simply take the 1 card, in which case the opponent will give us the 2 so they can keep the 3 (ending with 3 vs. 3 total utility). If instead we give the 1 card we will be left in the 2,3 case and it is clearly optimal to give the 2 and take the 3 (again, a 3-3 ending).

Next we must study N=4. This gets a bit trickier, as in order to choose what to do with the top card we must first find the optimal play in the 2,3,4 case. This is not particularly difficult, but it does show that in general we must solve a subgame with cards K,K+1,K+2,...N left in the pile.

Consider a situation where the top card is K and there are L cards left. Specifically the remaining cards are numbered K through K+L-1 (To convince yourself of that -1 consider L=2). Now let us inductively solve this on L. When L=1 we take (this is obvious). When L=2, we give then take, getting K+1 utility instead of just K. When L=3 we have a choice. If we choose to take, we will get card K and the opponent will give us K+1 to take K+2. If we give when L=3, we must also give when L=2 and take the last card, getting K+2 instead of K and K+1. So when L=3, choosing take gets 2K+1 vs choosing give getting K+2, comparing these we can see that 2K+1>K+2 iff K>1, and 2K+1=K+2 iff K=1. In a typical case K>1, so we should keep, and in the exceptional case K=1 we can do whatever (and might as well keep). In particular, being the active player when L=3 and card K is on top is worth K-1 utility.

Next, consider L=4. If we keep, then we get to keep card K, the opponent will keep card K+1 allowing us to give card K+2 and keep card K+3. If we give K we will keep K+1 (L=3 then, so we keep at that point) and the opponent will give K+2 to keep K+3. In the end, keeping gets us K+K+3 vs giving getting us K+1+K+2. These are the same, this result is somewhat clearer when you note that it is worth K utility to be the active player when L=3 and K+1 is on top, but keeping the top card of L=4 is worth exactly K, so keeping the top card of L=4 and being the next active player are worth exactly the same amount, so we do not care. Note that a result of this is that being the active player when L=4 is worth zero utility.

Next, L=5 (hopefully this goes somewhere soon). When L=5, we do not care who is the active player on the coming turn, being active when L=4 is worthless anyway. Thus, when L=5, we might as well keep. For L=6, whoever gets to go on the following L=5 turn will just take the top card worth K+1, so we should give K to the opponent and take K+1 when L=6.

When L=7, we get a similar analysis to L=3. We can take K and receive K+1, watching the opponent take K+2 (because the following initiative on L=4 is worthless). Or we can give K and K+1 to take K+2 (sounds sad unless K=1). This means we should take when L=7. L=8 comes out the same as L=4, being a worthless turn to have the initiative, we can keep or give, it does not matter.

We can see a pattern here. We need only look at how many cards are left mod 4. If the number of cards is 0 mod 4, this turn does not matter. If it is 1 mod 4, keep because the next turn does not matter. If it is 2 mod 4, give so you can keep the next card. If it is 3 mod 4, keep because the opponent is going to give then keep (unless the top card is K=1, then you can give it if you want).

So, if the total number of cards left is odd, you should always keep. If the total is even then give if it is not a multiple of 4, and play random if it is, alternately, you can just always give when the number of cards left is even and you will not be making any mistakes.

This means that the optimal play will have the players constantly performing give-keep actions. There is another way to see this, consider a pair of players that constantly keep the top card. They will divide the deck between them until one of them takes the last card. It is not hard to see that the person who gets the last card has a much higher utility than the other person, as their cards are all 1+ the other persons card. That is to say, the person who got to keep on the turns with odd numbers of cards left is much happier. Two optimal players are just taking turns trying to be the person who gets to take the cards when there are odd numbers of cards left.

The result of the game is that the players divide up the utility quite evenly. Let n be N mod 4. If n=0, the players will split the utility evenly. If n=1, then the first player gets a 1 utility advantage, but the rest is even. If n=2 the active player again gets a 1 utility advantage, by giving the 1 and taking the 2. If n=3, then the players split it evenly again.

How much utility is in the deck? With N cards, there is N(N+1)/2 in total (the N^th triangle number). Exactly one of N or N+1 is even, so the total utility in the deck will only be even if that number is also a multiple of 4. So, the only way that the utility can be split evenly is if N or N+1 is a multiple of 4, that is n=0 or n=3. In the other two cases, there is an odd utility out and the first player to take a turn will always get it.

Taking Cards

2010-01-05T15:14:00.001-08:00

So, while I was away for new years stuff, I played boardgames (as I usually do) and while playing a game of Strozzi I came up with a new logic puzzle. It turned out that that puzzle sucked, so I modified it into a different one. That one was less sucky but more boring, so I changed it again to come up with this:

There is a stack of N cards numbered 1 to N in order, with 1 on the top and N on the bottom. Two players are going to play a game where they will each wind up keeping some of these cards. The utility a player gets from playing the game is equal to the sum of the numbers on all the cards the player kept.

The game works by the players taking turns. On a turn, the active player may either keep the top card or give it to the other player. If the active player kept the card, then the other player gets the next turn. If the active player gave the card away, then the active player gets to take another turn. The play continues until the deck is empty.

Assuming optimal play, what is the result?

If you don't like utility, instead assume that the cards are worth $1 to $N, in order, with the $1 card on top and the $N card on the bottom. A player gets to cash out all of the cards that that player kept at the end of the game. People like money, right?

Walking In Puzzletown

2009-12-12T13:40:00.000-08:00

Figure its about time to finish of the discussion of the follow-up puzzle for the puzzletown problem, and of course, by discussion I mean my typing and you reading.

The basic solution was posted in the comments last time, it has to do with infinite family sizes. Consider each family measuring the variable #girls-#boys, which I will call x. At any given time, x is performing a random walk on the integers, increasing by 1 with probability 1/2 and decreasing by 1 with probability 1/2. The random walk starts at 0 and stops if it ever hits -1, on average how many steps does the random walk run for?

Initially, I tried to let F(x) be the number of steps it takes to get from x to -1 on average, write down the recursion relation, and solve. This sort of fails, and it is related to the fact that F(x) is actually infinite everywhere in our problem, so you have started with something of a non-function.

In an attempt to make the function converge, let us consider a random walk on the integers between a and b, starting at some point and stopping when we ever hit either a or b. In effect, a=-1 and b is some large number where the family will "give up" if the girls outnumber the boys by at least b.

Let f(x) be the average number of steps it takes to get from x to either a or b (I initially defined this as f(a,x,b), but that was far too cumbersome). Clearly we have f(a)=0=f(b), and we also have the recursion relation:

f(x)=1/2 (f(x+1)+1)+1/2 (f(x-1)+1)

That is, half the time f(x) is 1 more than f(x-1) and the other half the time it is 1 more than f(x+1). This can be written as:

f(x)-f(x-1)=f(x+1)-f(x)+2

So, defining d(x) as the derivative function, d(x)=f(x+1)-f(x), we have

d(x+1)-d(x)=-2

So, it appears that the second derivative of f is -2, giving the impression f is a quadratic with leading coefficient -1. Anyway, lets see what it actually is. Our last equation tells us:

d(x)=d(a)-2(x-a)

I didn't have to use 'a' for my constant in that equation, I could have used any value, but 'a' made the most sense.

Next, f is the "integral" of d:

f(x)=f(a)+Σ d(n)
=Σ (d(a)-2(n-a))

The sum over n runs from a to x-1. You might expect it to run to x (an intuition you get from integrals), but you can confirm that running to x-1 is the correct expression, from d(x)=f(x+1)-f(x). Naturally, f(a)=0 is one of our boundary conditions.

Performing the sum, we get:

f(x)=(x-a)(d(a)-2a)-2Σ n

The sum &Sigma n from a to x-1 can be broken into two sums, from 1 to x-1 and from 1 to a-1, giving x(x-1)/2-a(a-1)/2, so that

f(x)=(x-a)(d(a)-2a)-x(x-1)+a(a-1)

So, indeed f is a quadratic with leading coefficient -1. We know that f(b) must be 0, so that:

0=(b-a)(d(a)-2a)-b(b-1)+a(a-1)
(d(a)-2a)(b-a)=b²-a²-(b-a)=(b+a-1)(b-a)
d(a)-2a=b+a-1

Might be worth noting that I assumed (b-a) was nonzero there, so this whole thing collapses if we don't have that.

Anyway, new we can see that f is given by

f(x)=(x-a)(b+a-1)-x(x-1)+a(a-1)
=x(b+a)-x²-ab
=(b-x)(x-a)

Demonstrating the (well known) result that if you have a random walk between -a and b starting at 0, the average time it takes is ab.

Anyway, if we have a family that will stop having children when they have more boys than girls, or they will quit if the girls outnumber the boys by 100, the average family size is 100. If instead they will give up when the girls outnumber by a million, then the average family size is a million. If they will never give up, then the average family size diverges to infinity.

This means that the average family size in our puzzle scenario is infinite. Had we worked out that the average family was size n, it would have (n+1)/2 boys and (n-1)/2 girls (every family has exactly one more boy than girl). And the fraction of children that are boys would be (n+1)/(2n). As n tends to infinity, this is 1/2.
Some might say that it is absurd to believe that the average family size is infinity, you can run this experiment with as many families as you like, and never once will you find that the average family size is infinity. Whats more, you will never end the experiment with a town were the boys are exactly 1/2 of the children, they will always be more than 1/2 of them. This is quite correct, and actually raises an interesting point about probability.

When we say that something happens with probability 1/2, we do not mean it will happen exactly 1/2 the time. We really mean that if you were to perform the experiment n times, and you found that you got k occurrences of the event, in the limit as n goes to infinity, k/n would go to 1/2. For example, consider the first problem, when families stopped when they had 1 boy. If you ran this with some number of families, you probably would not get that exactly half the children were boys (they might be, but that would be a coincidence, really). You would get something reasonably close to 1/2, but probably not 1/2. All you can do is find the fraction of children that are boys when you have n families, and then take the limit as n goes to infinity. I will say with confidence that that will tend to 1/2 (subject to replicating the conditions of the problem, odds are that humans actually do not produce each gender equally likely).

In this problem you have something similar, if you run the experiment with any finite number of families, you will not get that boys are 1/2 the population, they will always be slightly greater than 1/2. But if you take more and more families for the experiment, you will find that the fraction of children that are boys gets closer and closer to 1/2. In the limit as the number of families goes to infinity, the fraction will tend to exactly 1/2. There is nothing wrong with a sequence of numbers that is strictly greater than 1/2 tending to 1/2, that happens all the time, and it is happening here.

I would also like to mention that this "n goes to infinity" interpretation of probability is also important when we talk about something happening with probability zero or probability one. If a mathematician says an event in an experiment will happen with probability zero, they do not mean that it cannot happen (though it might mean that), they mean that if you were to try the experiment n times and measure k occurrences of the event, that k/n will get arbitrarily small as n goes to infinity. So, for example, if you were to spend $1 per experiment and won $X every time the event occurred, no matter how large you set $X to, you will wind up losing money in the long run. They also call this probability zero because they have nothing else to call it. There is no positive number that is small enough to correctly represent the situation, and for most anything that matters in probability, we always have to clarify things by saying "after a large number of trials" anyway, so zero is the most correct number we can use to describe the probability of such events.

The Children In Puzzletown

2009-12-09T13:40:00.000-08:00

OK, time for the simple solution to the puzzletown problem. It was an interesting problem to pose to my officemate, who immediately thought that there would be more boys than girls (every family has at least one boy, after all), but then he realized that since the parents stop as soon as they have one boy, they will never have two boys, but sometimes they will have multiple girls before having a boy. Naturally this led him to conclude that there would be more girls than boys. Lets see what the math gives us.

First, since every family has exactly one boy, we need only ask how many girls a family has on average. We could similarly ask what is the average family size. A family is size 1 with probability 1/2 (they had a boy right away) size 2 with probability 1/4 (girl then boy) size 3 with probability 1/8 (GGB) and size N with probability 1/2^N. The average family size is therefore

Σ N/2^N

N summed 1 to infinity.
A sum of the form

Σ N/x^N+1

Is just

d/dx Σ -1/x^N
=d/dx Σ -(1/x)^N
=-d/dx 1/x*1/(1-1/x))
=d/dx 1/(1-x)
=1/(1-x)²

(If my sum confused you, remember the sum is running 1 to infinity, not 0 to infinity). So the average family size is

2 Σ N/2^N+1
=2

So, an average family has 1 girl and 1 boy. Thus the ratio is 1:1.
When this was posted on the xkcd forums, some people said that this answer is obvious, that since each child has expectation 1:1 value of boy:girl ratio, that no matter what criterion the parents use to decide to stop having children, the ratio will be 1:1, simply by linearity of expectation. This argument is quite correct, and is quite similar to the logic from the card flipping problem some time ago.

Some people on the forums then refuted this method of arriving at an answer by posing the following problem:

Each family will have children until they have had more male children than female children, then they will stop having children. On a given birth, it is equally likely that the child will be a boy or a girl. What is the ratio of boys to girls among the children in puzzletown?

This is a slight difference, as now every family will be guaranteed to have more boys than girls. Since it is true for each family, it must be true for the average of the families. One might ask the question of "what if they keep having children and they never have more boys than girls?" however this is not an issue, random walk theory will guarantee that given enough children, every family will at some point have more boys than girls.

The question here is, in this new problem, what happened to the linearity of expectation argument? Every family will have more boys than girls for certain. Therefore, the town will have more boys than girls, what went wrong?

The People In Puzzletown

2009-12-06T11:44:00.000-08:00

Time for a new problem. This one is not very difficult, you should be able to solve it in a matter of minutes, but it has a pretty neat follow-up, so I want to post it. I first learned this on the forums at xkcd.

The parents in puzzletown all want to have boys. Each family will have children until they have had at least one male child, then they will stop having children. On a given birth, it is equally likely that the child will be a boy or a girl. Assuming a large number of families, what is the ratio of boys to girls among the children in puzzletown?

Forward Is Backward

2009-12-02T11:19:00.000-08:00

Some time ago, I had presented Jon with the balls in a bag puzzle, and he had suggested the following reverse puzzle:

Consider a bag with N red balls. At each step, you select two balls from the bag and if they are the same colour, you repaint one of them a new unique colour. If they are different, then do nothing. Either way, place the two balls back in the bag and begin a new step. Given long enough, eventually all the balls in the bag will be of different colours, on average how many steps does it take?

Its clear that this is some sort of reverse of the original problem, however, it is not clear that this is actually the "best" reverse. One could also give the newly coloured balls "random colours from the list of N colours" instead of new unique ones, but it turns out this problem is much more awful.
Anyway, I'm going to just solve this reverse problem on the spot, it seems like the thing to do. Let F(k) be the average number of steps it takes to get from a state with k red balls to a state with one red ball. Note that knowing the number of red balls totally specifies a state, since all non-red balls are of unique colours. F(1)=0 trivially, and we seek F(N), the state with N red balls. The probability that we move from a state with k red balls to a state with k-1 red balls (I will call this P(k)) is the chance that we draw exactly two red balls from the bag, that is:

P(k)=k/N*(k-1)/(N-1)

Of course, if something happens with probability p, then on average we need 1/p tries to have it happen once (I proved this back in the post where I gave the solution to the prisoner problem). Naturally then, we have:

F(k)-F(k-1)=(N-1)N/(k-1)k

and since F(1)=0, we can just express F(m) as F(m)-F(m-1)+F(m-1)-F(m-2)+...+F(2)-F(1), to give

F(m)=Σ N(N-1)/k(k-1)

summing k from 2 to m.
Therefore, for F(N) we have:

N(N-1)Σ 1/k(k-1)
=N(N-1)Σ [1/(k-1)-1/k]

summed k from 2 to N. This series telescopes, the terms look like 1/1-1/2+1/2-1/3+1/3-1/4+...-1/(N-1)+1/(N-1)-1/N. The final result is then that:

F(N)=N(N-1)[1-1/N]
=N(N-1)[(N-1)/N]
=(N-1)^2

Weird.
Alright, so this (much easier) problem has the same answer as the "forward" ball problem. I guess in some sense it is the correct reversal of the initial problem, since it has the same answer. I would love to find a way to show that these two problems have the same answer (that does not rely on using the fact that they both give (N-1)^2), so that way we can solve the harder one just by doing the easier one. Anyway, thats all I got here, if you can find a way to show that these problems are equivalent, feel free to give it in the comments.

Its All Red

2009-11-26T12:49:00.000-08:00

Time to post the solution to the balls in a bag problem from last time. The solution actually gets pretty crazy, and I actually had to make up a tiny amount of new math (new to me, anyway) in order to justify the solution that Matt came to me with, but all in all it was a good adventure.

First of all, we are going to select a single colour of ball from the bag (let it be called "red") and only watch the progress of that colour. If red is ever eliminated we will declare the experiment a failure and try again, if red is ever the only colour left we ask how many steps it took. Naturally this means that only 1/N of our experiments even end in success, so I will have to account for that at the end, but we will cross that bridge when we come to it. Next, let us define a function F(k,m) as the probability that we are in a state with k red balls after m steps. Naturally F(1,0)=1, F(k,0)=0 for k &ne 1, and the asymptotic behaviour of F in m is

lim_m->∞F(N,m)=1/N
lim_m->∞F(0,m)=(N-1)/N
lim_m->∞F(k,m)=0 for all other k

In words, this is that our initial condition has exactly 1 red ball, and in the long run we will either have all red balls (probability 1/N) or no red balls (otherwise). It is worth noting that we expect that there are no experiments that run forever (that would be lim_m->∞F(k,m)=nonzero for k neither N nor 0), that have a nonzero probability. This is to be contrasted with the chance that the expectation value of the path length being infinity, which I have not ruled out yet. Of course, summing F(k,m) over k always gives 1.

Alright, now that we have that, we need to find the recursion relation on F. If we are entering the (m+1)^th step, the chance that we get to having k red balls is given by:

F(k,m+1)=[(k-1)/N]*[(N-(k-1))/(N-1)]F(k-1,m)
+[(N-(k+1))/N]*[(k+1)/(N-1)]F(k+1,m)
+[k/N*(k-1)/(N-1)+(N-k)/N*(N-k-1)/(N-1)]F(k,m)

that is, the chance we drew a red then non-red from k-1, plus the chance we drew a non-red then red from k+1 and the chance we drew two red or two non-red from k. This can be written as:

F(k,m+1)=1/(N(N-1))*
[(k-1)(N-k+1)F(k-1,m)+
(N-k-1)(k+1)F(k+1,m)-
2k(N-k)F(k,m)]
+F(k,m)

Why I separated out that F(k,m) term will be apparent later.

Let us now make a series of vectors, V_m with N-1 elements so that the k^th element of the vector V_m is given by F(k,m). Then the recursion relation gives us

V_m+1=MV_m

and the matrix M is specified by the recursion relation. Note that V only keeps track of having 1 through N-1 red balls left, so information "leaks" out the ends of it and the sum of the elements of V is not conserved. It is also worth noting that V_m tends to the zero vector as m tends to infinity, no matter how the initial data for V looked (that point will turn out to be extremely important later, make sure you convince yourself of it now).

Ok, let us try to get a feel for the matrix M that iterates on V. The diagonal of M is the term that keeps F(k,m) at F(k,m+1), that is to say that the k^th element on the diagonal is 1-2k(N-k)/(N(N-1)). There are also off-diagonal terms adjacent to the diagonal, but everything else is zero. For notational convenience, I will denote N(N-1)=Z. For some large N, the first part of the matrix looks like:

[1-2(N-1)/Z, 2(N-2)/Z, 0, 0, 0, ....]
[(N-1)/Z, 1-2*(2(N-2))/Z, 3(N-3)/Z, 0, 0, ....]
[0, 2(N-2)/Z, 1-2*(3(N-3))/Z, 4(N-4)/Z, 0, ....]
....

The k^th diagonal element is 1-2*k(N-k)/Z, above and below the k^th diagonal element is k(N-k)/Z. Every column adds to 1, except for the first and last columns, which represent probability leaking out the ends.

Now that we have this, what the heck do we do with it. Well, we want to find the probability that we end on the m^th step, times m, summed over all m. That gives us the expectation value of what step we end on. The probability that we end on the m^th step is the last element of V_m-1 (the penultimate state) times (N-1)/N (the chance we draw a red ball) times 1/(N-1) (the chance we draw the final non-red ball). So we want

Σ m/N [0,0,0,....0,1]V_m-1

summed over m. Actually this is not quite right, since only 1/N of the experiments even end the way we want, we must also multiply by N. Anyway, we know that V_m-1=M^m-1V₀, and V₀ is given as the column vector [1,0,0,0,...] (which I will write as [1,0,0,0,...]^T, for lack of ability to write column vectors).

To put it together, we seek to find

Σ m [0,0,0,....0,1]M^m-1[1,0,0,0,...]^T

summed over m=0 to ∞ of course.

Much of that is just constants relative to the sum, and we really just need to evaluate

Σ m M^m-1

Now, if instead of a matrix M, we had a real number, x, we could easily use

d Σ x^m/dx = Σ m x^m-1

so we would like to say:

Σ m M^m-1=d Σ M^m/dM

Ok, so can we take the derivative with respect to a matrix? Well, its not at all uncommon to do that in physics, we often consider scalar function S(M) as define the derivative (dS/dM)_ij as the derivative of S with respect to the ij^th component of M. This means dS/dM is a matrix. Following this up, we would expect that if we have a matrix function T(M) with two component indices (such as M² or M^-1), then dT/dM would have four indices. If we define the derivative dT/dM to have two indices by using the definition

dT/dM_ij=Σ (d/dM_ik)T_kj

summing over k (as we do in matrix multiplication), then using

(d/dM_ij)M_kl=δ _ikδ _jl

it is easy to show that

dMⁿ/dM=nM^n-1

for all integers n (to get the inverses, you must use that d/dM (M^-1M)=0).

Alright, se we can now say with confidence that

Σ m M^m-1=d Σ M^m/dM

So now we just need a way to evaluate Σ M^m. Again, if this were a real number x, we would simply say that

Σ x^m=1/(1-x)

(as long as |x|<1) so how can we do something similar for a matrix?First of all, let us consider the p^th partial sum, &Sigma M^m summed m from 0 to p. It is easy to see that

(1-M)Σ M^m=1-M^p+1

so as long as we have (1-M) being invertible and lim_p->∞M^p+1=0, then we can say that Σ M^m=(1-M)^-1

Remember when I said that V_m tends to zero no matter what the initial data is? this fact can prove both of the statements that we need. A matrix is really just defined in terms of how it acts on vectors (this is an important point, understand it), thus if a matrix obeys the relationship lim_p->∞M^pV=0 for all vectors V, then it means that lim_p->∞M^p=0, since it really apparently is the zero matrix. We knew from before that this is true for our matrix M. I'll admit that I have not really proven it, but it is apparent from the physics of the problem (people who know me will understand that when I say something is "apparent from the physics of the problem", I really mean "I don't know how to prove this, but it is so obvious from the way things are set up, I feel no need to").

So we can now say with confidence that

(1-M)Σ M^m=1

when we take the sum to infinity. Now, can we invert the matrix (1-M) (which I will call W)? Well, first let us assume that W has no inverse. This means that W must have a null space, that is to say there is a nonzero vector U such that WU=0. This naturally implies that (1-M)U=0 so MU=U, U is an eigenvector with eigenvalue 1. But this means that M^pU=U for all p, and so that is even true in the limit of large p, but for large p we have M^p must vanish. This is a contradiction proving that W (=(1-M)) is invertible.

So, earlier, we had seen that the answer to the question we seek was given by

Σ m [0,0,0,....0,1]M^m-1[1,0,0,0,...]^T

which we can now rewrite as

[0,0,0,....0,1]W^-2[1,0,0,0,...]^T

That is, we seek the inverse of the matrix (1-M) and we want the element in the last row and first column in the square of said matrix.

W looks like

[2*(N-1)/Z, 2(2-N)/Z, 0, 0, 0, 0,.....]
[(1-N)/Z, 2*2(N-2)/Z, 3(N-3)/Z, 0, 0, 0,.....]
[0, 2(N-2)/Z, 2*3(N-3)/Z, 4(N-4)/Z, 0, 0,.....]
.....

Z being N(N-1) as before. We can actually just factor out 1/Z now, and get

[2*(N-1), 2(2-N), 0, 0, 0, 0,.....]
[(1-N), 2*2(N-2), 3(3-N), 0, 0, 0,.....]
[0, 2(2-N), 2*3(N-3), 4(4-N), 0, 0,.....]
[0, 0, 3(3-N), 2*4(N-4), 5(5-N), 0,.....]
.....

as the expression for WZ.

Now, if we want the last element in W^-2, we want the last row and the first column of W^-1 and we need no other information about W^-1 except that it exists (and it does). Find a row vector that gives 1 when it acts on the last column of W and gives 0 for all other columns (you might want to write W on paper now, to get a feel for it). We find that the last row in the matrix W^-1 is [1,2,3,4,5...,N-1], you might want to try out W in a few simple cases of N=3,4,5 to convince yourself of this. We also need the first column in the matrix W^-1, that is, we need a column vector that gives 1 when it acts on the first row of W, and 0 when it acts on any other row. The vector is [Z/N, Z/2N, Z/3N, Z/4N, ....., Z/(N(N-1))]^T. Naturally, the last element of the first column and the first element of the last row agree.

Finally, we multiply this last row and first column to get the element of the last row and first column of W^-2 Z/N+Z/N+Z/N+..., and we have a total of N-1 terms, but Z is N(N-1).

So we have (N-1)^2, our final answer. I have a bit more to write about this puzzle, but this seems like quite enough as it is.

Balls In A Bag

2009-11-21T11:35:00.000-08:00

I have been pretty consistent in posting just once a week, and thats mostly just been so I don't run out of blogging material, but Matt recently solved a problem that we have been working on for nearly 3 years so I really wanted to post the solution as soon as I was able to work out the wrinkles. This is the problem as I first learned it on the forums at xkcd:

Consider you have a bag filled with N balls, each with a different colour. At each step you will randomly select a ball from the bag, look at its colour, and select another ball from the bag, and repaint the second ball to the colour of the first one. After doing that, place both balls back into the bag and begin a new step.
After doing this enough times, it will eventually happen that all the balls in the bag will have the same colour. On average, how many steps does it take for this to happen?

Doing the problem "properly" is very difficult, and I would only suggest it if you are crazy. However, solving it in the cases of N=2,3,4 is not particularly hard, and from that you will be able to guess what the answer should be.

Equilateral Roads

2009-11-19T15:45:00.000-08:00

Time for the solution to the Houses on a Square problem, in spite of the fact that all (both, it seems) of my readers have already solved it.

Not much is gained by building up to the solution, so I'll just sort of blurt it out. I should use pictures here, but rather than figure out how pictures work on blogger, I'd prefer to just use words:

Place a node at the center top and center bottom of the square, connect the top node to each of the top two houses with roads, and connect the bottom node to the bottom two houses with roads and connect the top node and the bottom node to eachother. I assume that you have a picture in your head that looks like a capital i. Now we are going to move the top and bottom nodes, and the edges that terminate on them will move with them. Move the top node down a distance x, and the bottom node up a distance x. Now it is simply a matter of finding the x which optimizes the solution.

The total length as a function of x is

L=1-2x+4√(1/4+x²)

1-2x is the length of the center piece and √(1/4+x²) is the length of one of the diagonals. Maximizing L(x), we find the derivative is

L'(x)= -2+4*x/√(1/4+x²)=0
x=1/(2√3)

Giving a value of L=1+√3. At this point we haven't exactly shown that this is the optimal solution, however, we have shown that it is the optimal solution of this form. Before I go into more about that, first let us consider the rectangular case.

Consider a rectangle, with side lengths A and B. We will assume that A>B for defeniteness, and we will visualize that the longer side is the vertical one (I do this so that when I refer to "the top side" or something, we all have the same picture in mind). Trying the same form of solution as last time, we can see that we want our middle line to be vertical rather than horizontal, it will save more space that way. Letting x once represent the amount that the top node is down from the top, the total road length is given by

L=A-2x+4√(B²/4+x²)

Extremizing this gives that x=B/2√3, and L=A+B√3 (we can see that the length is minimized when A>B rather than B>A, as anticipated). Note that the ratio of x to B is the same in the rectangle case as it is in the square one. This means that the angle that the diagonal line hits the vertical line at is independent of the measurements of the rectangle. In fact, the vertex where the lines meet has angles entirely of 120 degrees. This is not surprising, because if we just had 3 houses we were trying to connect, we would place a point somewhere in the middle of them and have the lines connecting them to the point meet at 120 degrees. There is an exception if the triangle has an internal angle of greater than 120, then it is optimal to just draw straight lines (as the relevant point is outside of the triangle).

Actually, this is a feature of any solution, all angles involved in connections are at least 120 degrees. If you draw a solution with an angle of less than that, you are better to add a point and draw 3 lines connecting to it. I found a paper that talks about this problem at http://www.denison.edu/academics/departments/mathcs/herring.pdf. The full proof is nontrivial, but one conclusion is that to connect N nodes together, you will never need more than N-2 extra nodes, so for the square there are no solutions that involve needing 3 extra nodes, 2 is optimal.

You can also see that for any regular polygon with 6 or more sides, the internal angles are 120 degrees or larger, so it is optimal to just connect along the edges. A pentagon is a bit funny though, since the internal angles are 108 degrees, you do need to find a solution with extra verticies on the inside. The actual solution looks sort of funny, and isn't hard to find after some thinking, anyway, thats all I got on this problem.

Houses On A Square

2009-11-13T12:00:00.000-08:00

Guess we once again find ourselves in the "new puzzle" part of the cycle. This particular one I heard a long time ago, can't recall when exactly, but I was recently reminded of it by James:

Consider 4 houses located at the corners of a square with side length 1. We must build roads so that one can drive from any house to any other house along the roads. What is the minimum total length of road that needs to be built?

Just to get you started through the first few layers of solution, you can easily solve the problem with road length 3, connect 3 of the houses along sides of the square, and you have connected them all. You can do better with a 2√2 solution, by drawing in the diagonals of the square, this will connect all the houses to eachother by roads. As amazing as it might seem, you can do even better than that.

As a generalization of this problem, try solving it on a rectangle. You can further generalize it to other shapes, and even arbitrary distributions of points, but I wouldn't suggest it.

Triangular Hypermarbles

2009-10-31T11:34:00.000-07:00

Due to some discussion in the solution to the breaking marbles puzzle, I have decided to make a post of the extension problem. Now let us suppose we have K marbles and N floors, what is the minimum number of moves it takes to find the critical floor, assuming you are minimizing the worst case scenario.

For some definiteness, we will assume that if you eliminate all the floors but the end one, you must still check the end one. This is so that, say, in the 2 marble 3 floor case, you can do it in 2 steps optimally by checking floor 2, then checking floor 3 if it does not break, and checking floor 1 if it does (specifically you cannot just assume that if it didn't break on floor 2 it will then break on 3, and that if it broke on floor 2 it can't break on floor 1). The reason for this "handling of the endpoints" is so that in the two marble case, you cannot do better than Triangle(M) floors with M steps. Triangle(M), the M^th triangle number, will be denoted T_M, and is given by M(M+1)/2.

Now, lets try the 3 marble case. Let us suppose we have N floors, and we have a solution that works in never more than 5 steps (I'll generalize 5 to M later). Then with our first move, we might as well go to floor 11. If we go any higher, then if it breaks we cannot solve the remaining case with over 10 floors with only 2 marbles and 4 steps (2 marbles, 4 steps, 10 floors is optimal), and nothing is to be gained by going any lower. Next, we move 7 more floors, since if it breaks we can solve through the 6 we skipped with 2 marbles and 3 steps. Next, we will move up another 4 floors, so that if it breaks, there are 3 floors unchecked which we do can with the remaining 2 steps and 2 marbles. Next up 2 more floors, because we will only have 1 step left (now steps is more limiting than marbles, one gets the impression that when you have at least as many steps as you have marbles, binary search will be best). And finally we get 1 last step.

The result is 11+7+4+2+1=25 (looks like powers of 2 at the end, neat), this is better written as 10+1+6+1+3+1+1+1+0+1, that is T₄+1+T₃+1+T₂+1+T₁+1+T₀+1. Which is the same as P₄+4+1 (P_K is the K^th pyramidal number, the sum of the first K triangle numbers). The general statement, which is easy enough to verify by induction, is that with 3 marbles and M steps, you can do at most P_M-1+M floors. We will denote this as F(3,M), the maximum you can do with 3 marbles in M steps.

We already know that

F(1,M)=M
F(2,M)=T_M=M(M+1)/2

And now we know

F(3,M)=P_M-1+M
=(M-1)M(M+1)/6+M
=(M²+5)*M/6

The formula P_M=M*(M+1)*(M+2)/6 can be found either by induction or by realizing the connection between Pascal's triangle and the generalized triangle numbers (more on that in a moment).

Next we want to try 4 marbles. With M steps, we cannot go higher than F(3,M-1)+1 for our first step, and there is no sense in going lower. We then move up another F(3,M-2)+1 steps and so on until we are out of moves. The result is that

F(4,M)=Σ F(3,M-i)+M

The sum being i from 1 to M-1. This argument will hold quite generally, to get the result of

F(N,M)=Σ F(N-1,i)+M

i now being summed from 1 to M-1, or if we define F(N,0)=0 (the most number of floors you can do with N marbles and zero steps) we can start i from 0.

Before going further into F, I would like to consider another function. Let us define the "hypertriangular numbers" H(N,M) so that each one is the sum of the first M previous ones. Specifically,

H(0,M)=1
H(N,M)=Σ H(N-1,i)

i being summed from 0 to M-1. These generalize the triangle numbers cleanly, H(1,M)=M+1, H(2,M)=T_M+1, H(3,M)=P_M+1. One can easily confirm that

H(N,M)=H(N-1,M)+H(N,M-1)
H(N,0)=1
H(0,M)=1

So these numbers basically form up Pascal's triangle, so that

H(N,M)=(N+M)!/(N!M!)

Note that in the definition, N and M were not symmetric, but in the end they are.

I'll come back to that function later, but the connection between hypertriangle numbers and Pascal's triangle will be important in a bit. Recall F's recursion relation is:

F(0,M)=0
F(N,0)=0
F(N,M)=Σ F(N-1,i)+M

(i summed from 0 to M-1). One can start filling this in, its slightly illustrative to do this. Labeling x-axis as M value and y-axis as N value, we get (apologies for formatting issues):

0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
0 1 3 6 10 15
0 1 3 7 14 25
0 1 3 7 15 30
0 1 3 7 15
0 1 3 7
0 1 3 7

and so on. Each number is the sum of the numbers in the row above it from 0 to M-1 and then adds the number M. This results in the first non-zero row coming up just as M, the second row comes up as triangle numbers, but then the third row comes up funny. Note that when N gets bigger than M, the numbers just turn into 2^M-1, somewhat demonstrating the fact that having more marbles than steps means the marbles breaking isn't an issue, and then you get the result of a binary search.

One can construct Pascal's triangle in a similar way, starting with 1's and letting each element be the sum of the row above it, from that one can prove the relation H(N,M)=H(N-1,M)+H(N,M-1) (I'm going to start calling this the Pascal relation). In this case, one can find by inspection of the graph that F will obey a similar linear relation:

F(N,M)=F(N-1,M)+F(N,M-1)-F(N-2,M-1)

It isn't exactly clear to me how to prove this formally, but I am confident in it. You should confirm for yourself that it is true, it is somewhat pivotal. Anyway, we now have a semi-Pascal relation that F obeys, and now our relation is linear in F. At this point, I asked myself, "what would Matt do?" and got the only obvious answer, define the derivative function:

D(N,M)=F(N,M)-F(N-1,M)

I suppose its the derivative with respect to N, but its one nonetheless.

Using our semi-Pascal relation on F, we can find a similar one on D, rewrite the F one as:

F(N,M)-F(N-1,M)=F(N,M-1)-F(N-2,M-1)
=F(N,M-1)-F(N-1,M-1)+F(N-1,M-1)-F(N-2,M-1)
=> D(N,M)=D(N,M-1)+D(N-1,M-1)

This is almost a Pascal relation on D, but things are shifted over slightly, to fix this we will define a new function K according to

K(N,L)=D(N,N+L)
K(N,M-N)=D(N,M)

I'm really just defining L=M-N and considering a function of N,L rather than N,M (this is logical, since D sort of "breaks down" if N>M, thats were F stopped varying). Anyway, from D's relation, we can find that K obeys the relation:

K(N,M-N)=K(N,M-N-1)+K(N-1,M-N)
K(N,L)=K(N,L-1)+K(N-1,L)

Hurrah, K obeys the Pascal relation, now we need to find its boundary conditions. Trying to check K(0,L) immediately causes problems involving D(-1,L), so lets try K(1,L)

K(1,L)=D(1,L+1)=F(1,L+1)-F(0,L+1)
=L+1

Good, next lets check K(N,0)

K(N,0)=D(N,N)=F(N,N)-F(N-1,N)

Uh oh, this could put a stop to all of our fun right here. Fortunately, we can handle this, it turns out (one can inspect the chart) that F(N,N)-F(N-1,N)=1. We can prove this using the earlier recursion relation for F to show that

F(N,N)=F(N-1,N)+F(N,N-1)+F(N-2,N-1)
F(N,N)-F(N-1,N)=F(N,N-1)+F(N-2,N-1)

Next, we must handle F(N,N-1) by considering the "physics" of the problem. Consider F(N,M) when N>M, so you have more marbles than you have steps remaining. In this case, the extra marbles are irrelevant, so you can just ignore their existence, F(N,M)=F(M,M) when N>M. This is also present in the table of F. Thus we have F(N,N-1)=F(N-1,N-1), therefore

F(N,N)-F(N-1,N)=F(N-1,N-1)+F(N-2,N-1)

So apparently F(N,N)-F(N-1,N) is constant in N (shifting N by 1 has no effect, so shifting it by 100 won't either). Evaluating when N=1 gives us

F(N,N)-F(N-1,N)=F(1,1)-F(0,1)=1-0=1

Proving that K(N,0)=1.

Ok, current data on K:

K(N,L)=K(N,L-1)+K(N-1,L)
K(1,L)=L+1
K(N,0)=1

We can extend K to K(0,L) using its Pascal relation on N=1:

K(1,L)=K(1,L-1)+K(0,L)
L+1=L+K(0,L)

Demonstrating that it is consistent to take K(0,L)=1. so, K has the same initial conditions as H (the hypertriangle function) and the same Pascal relation, so K=H must be the case.

K(N,M)=(N+M)!/(N!M!)

Now we can find D as D(N,M)=K(N,M-N)

D(N,M)=M!(N!(M-N)!)

So it seems D is just M choose N, naturally if N>M then D(N,M)=0.

Finally we are ready to construct F. D was the "derivative" of F, so F is the "integral" of D. Specifically,

F(N,M)-F(0,M)=Σ D(i,M)

The sum running i from 1 to N. We know F(0,M)=0, and D(N,M) is zero if N>M, and so we have

F(N,M)=Σ M!/((M-i)! i!)

Summing i from 1 to min(N,M). Note that the summation starts at 1, where a typical summation over choose functions would start at 0.

So when N is less than M, F(N,M) is the sum of the first N elements in the M^th row of Pascal's triangle, minus 1. In words, one can consider a set of M elements and ask how many nonempty subsets with at most N elements are there. I'm not sure if there is a clean form for that.

Finally, if N>M, F(N,M)=F(M,M), the number of nonempty subsets of size at most M in the set of M elements. A set with M elements has 2^M subsets, and one of those is the empty set. So, F(M,M)=2^M-1, as one would expect from a binary search solution.

This completes the solution for how many floors you can cover with N marbles in M steps. If somebody asked your the reverse (and more standard) problem of solving K floors with N marbles, you simply look for the minimal value of M such that F(N,M)>K, and that gives you the worst case M.

Invisible Ants

2009-10-30T16:10:00.000-07:00

Time for the solution to the ants on a line problem. The solution is actually stupidly simple, it really just is about one realization: Two pointlike ants bouncing off eachother is identical to two pointlike ants passing through eachother. At this point, you can easily see that there theoretical maximum is that you have an ant right on the left end initially walking to the right. No matter how the other ants are distributed, it will take exactly 100s for the last ant to fall off.

Pretty dumb puzzle, to be honest, but I thought it was a bit of a cute trick.

Ants On A Line

2009-10-23T14:52:00.000-07:00

New puzzle time, though this one is a bit strange. I first heard it somewhere random on the blagosphere:

You have a one dimensional meterstick that you distribute 100 pointlike ants on, at random locations. Each ant will select randomly to begin walking right or left, and keep walking that direction at until it bumps into another ant. If two ants bump into eachother, they will each turn around and go the other direction. If an ant reaches the end of the meterstick, it will fall off. The ants have a constant speed of 1 cm/s. Given enough time, eventually all of the ants will fall off the stick, and for different initial distributions and choices of initial directions this will take a varying amount of time. What is the theoretical maximum length of time it will take for all the ants to fall of the stick?

So, find the distribution and set of left/right choices that maximizes the time the ants spend on the stick. Or the class of distributions, I suppose, no guarantee that it is unique.

Gambling Solution

2009-10-16T15:50:00.000-07:00

Time to solve the gambling puzzle from last time. When I told this problem to Matt, his immediate reaction (which I found rather amusing) was to say "OK....hmm, what would Kory do?................. ah yes, consider a simpler case." That seems to be the right approach, so lets assume that the frungy tournament is best or 3, first team to 2 games wins.

We already know that we should not bet all $400 on Blue in the first game, because then Red might win the first game and suddenly we are out of money. Blue then might go on to win the tournament and we are in trouble. Taking the other extreme strategy of not betting on the first game at all, if Blue wins the game, we have no choice but to bet everything on Blue now (else if Blue wins again we are done). But now if Red wins we are out of money for the final game (which, if we are unlucky, Blue will win).

The next obvious thing is to take the middle ground and bet $200 on Blue in the first game. Now if Blue loses we have $200 left and Red is up 1-0. Since Red winning again is auto-victory for us anyway we might as well bet everything we have left on Blue. If Blue wins now we have $400 and they are tied 1-1. At this point it is simple. OK, instead suppose Blue wins the first game, now we have $600 and Blue is up 1-0. We need only bet $200 on Blue this next game, so that if they win we end with $800, so now if they lose we have $400 left and the teams are 1-1 again. Good, this is a full solution, it is also nice to see that it is 100%, rather than just a probabilistic solution.

A few things to notice about that solution. First of all, we never ended with any excess money, in all strategies we came out with exactly $800. Another thing is that the result was "path independent", that is, no matter if Blue won first or Red won first if the game got to being tied at 1-1 it did not matter how we got there, we had exactly $400. Both of these facts are general about the full solution (assuming it is a 100% solution, that is).

First of all, the "no excess money" result. Let us begin by supposing that we have a full strategy for how to bet in the games as the tournament progresses. Note that every game is a bet on a coin flip, therefore no matter what your planned strategy is you will have an expectation of $400 after each game. The side bet is an even chance split of $800 and $0, so it has an expectation of $400. Thus, at the end of the week, no matter your strategy, you have an expected final amount of money equal to $800. If there is any possible path through the game tree that ends with more than $800, there is also a path through the game tree with less than $800, so no solution that works 100% of the time can ever end with excess money.

Now for the "path independent" result. Suppose we have a betting strategy for the whole week. Further suppose there was a node in the game tree (for example, Red is up 3-1 on Blue) that depending on how you got there you will have different amounts of money (so for one path you have $x, and for the other you have $y). Assuming x>y then if we get there with $x, we can simply throw away $(x-y) to leave ourselves with $y and still have a planned out strategy for the rest of the game. This strategy will apparently have had excess money, which we know is impossible.

Alright, we are almost ready to make the full solution. The final step is that if your strategy knows how much money it has at each step, you know how much you need to bet. So if you know you have $400 now and if Blue wins you need to have $600, but if Red wins you need to have $200, the it is time to bet $200 on Blue. We will describe a strategy as a chart of the amount of money we need at each step in the game tree. Consider the tree for the three game case as follows (This is going to format like crap, but it will be readable):

AAA BBB
CCC DDD

OK, AAA represents the amount of money we start with (so, 400), BBB is the amount of money we have if Red is up 1-0, CCC is the amount of money we have if Blue is up 1-0 and DDD is the amount of money we have if the game is tied 1-1. So, my notation is that if Red wins we move a step right, if Blue wins we take a step down.

We know that if Blue wins two games we must have exactly 800, and if Red wins we must have exactly 0 (no excess money), so we can add those values in:

AAA BBB 0
CCC DDD 0
800 800

Now, we know that DDD must be exactly 400, there is no other amount of money it can be that will be consistent with this. But then we know that CCC is 600, and BBB is 200. Finally we get that AAA is 400, which is really just a consistency check.

You can now easily see the general answer, but lets just go through it anyway, for the full 7 game case we have:

AAA BBB CCC DDD 0
EEE FFF GGG HHH 0
KKK LLL NNN PPP 0
QQQ RRR SSS TTT 0
800 800 800 800

Great, we can now see that TTT is 400, PPP is 200, HHH is 100 and DDD is 50. Also we get that SSS is 600, RRR is 700 and QQQ is 750. Sort of a neat symmetry here:

AAA BBB CCC 050 0
EEE FFF GGG 100 0
KKK LLL NNN 200 0
750 700 600 400 0
800 800 800 800

Its simple enough to continue filling this all in now:

400 275 150 050 0
525 400 250 100 0
650 550 400 200 0
750 700 600 400 0
800 800 800 800

So, apparently the correct solution begins with placing a $125 bet on Blue in the first game.

Gambling Puzzle

2009-10-07T18:42:00.000-07:00

I suppose I could have titled this one "gambling problem", but that carries all sorts of other implications that we won't bother with here. Anyway, this puzzle I first learned on the forums at xkcd:

Alex has decided to start a widget company with his $800 savings. He has put in an order for a widget machine that will be delivered next week and will cost him $800, to be paid on delivery. However, when he went back to check on his money he found out that last night, in a drunken stupor, he placed a $400 bet on Red in the upcoming Red vs. Blue Frungy tournament.

A Frungy tournament is a seven game tournament, one game played each day, and the first team to win 4 games wins the tournament. Red and Blue are equally skilled teams, and each game is 50-50 between them (and there are no ties in Frungy). Alex decided to go to the betting office to simply bet his remaining $400 on Blue so that they would cancel and he would be guaranteed to get back his $800 at the end of the week, but he has found out that that part of the betting is closed, now he can only bet on the individual games each morning.

Each morning, Alex may place as much money as he likes on an even bet for either Red or Blue. The bet is resolved that evening, and he will receive any winnings before the next day. Find a betting strategy that guarantees that Alex will end the week with at least $800 so he can make the payment for his widget machine.

Assuming that all made sense through the "theme", you basically have to guarantee that if Blue wins 4 games, you have made at least $800 from your bets. If Red wins 4 games, then your side bet kicks in and you are safe no matter what.

Alex would just like to bet all $400 on Blue in the first game, but Blue might lose the first game and then go on to win the tournament. Find a strategy that maximizes the probability of ending the week with at least $800.

Triangular Marbles

2009-09-28T12:20:00.000-07:00

Time to post the solution to the marble problem from last time. First of all, lets just try some naive strategies. When I introduced the problem, I had suggested the idea of just moving up the floors one at a time until the marble broke. Since we have two marbles, we can try to do better by moving up two floors at a time. We try floors 2,4,6,8,10,... and when the marble breaks on floor k, we simply use the other marble to try floor k-1 and confirm which was the critical floor. This strategy is much less wasteful that the last one (at least it makes use of the second marble), and the worst case scenario is if the critical floor, N, is 99 or 100, in which case we need to try all the even floors (50 of them) plus floor 99 for a total of 51 tries.

Alright, if two floors at a time improved our position, lets try three. Now we will test floors 3,6,9,12,... and when the marble breaks on floor k, we try k-1 and k-2 to confirm. I suppose if we get to floor 99 and the marble doesn't break, we don't actually need to try floor 100, but whatever. The worst case scenario is if we go all the way to 99 and must do 97 and 98. In this case we did 3,6,9,12,...99 for 33 floors and 97 and 98 for a total of 35 tries.

So taking larger steps seems to be better, we could try something silly like 25 floors at a time and then your worst case is 27 (easy to confirm). It is pretty clear that you will get the optimal strategy of this form if you just do 10 at a time (the square root of 100), and the worst case is 19.

Now the next thing to notice is that if you were to make a bigger step at the beginning, you don't make your life any worse. In particular, if you start with floor 15 and then go 25,35,45,..95, then go back, the worst case won't be N=100 anymore (that would take only 11 tries), the worst case will be N=94 or 95 for a total of 18 floors (its one better than the last case because you basically skipped a set of 10).

This idea of skipping a bunch of floors at the beginning will only work so far, of course. If you try to move all the way up to 20, then if it breaks right away you must try all 20 initial floors. So we see that if the actual worst case scenario is that it takes M tries, then you cannot start on a floor higher than M (because if the critical floor N is M-1 you are in trouble). Next, you can move up another M-1 floors at most, because if you move up M more and N is 2M-1 then you will need M+1 total tries to find it. Clearly we must move up by M-1 floors to floor 2M-1. Next we can move up by M-2 floors at most. You can see what is happening here.

If the total number of floors is the K^th triangle number, then you can solve the problem most efficiently in K steps by moving up K floors then K-1 then K-2 and so on. The 13^th triangle number is 91, so we cannot do more than 91 floors in 13 steps. Thus we can just treat our 100 floor building as a 105 floor building (the 14^th triangle number) and use that solution.

Breaking Marbles

2009-09-23T16:37:00.000-07:00

Time for a new puzzle, I'm not sure where I first learned this one, it was somewhere randomly on the internets:

Consider there is a building with 100 floors. You have a pair of identical marbles which you are going to drop from the windows of this building. There is a height at which the marbles are broken if they are dropped from that height. The marbles will break if they are dropped from that height or more, and take no damage if they are dropped from any lesser height. The objective is to determine what floor is that height using as few drops as possible. You may assume that a broken marble is useless, and that you are to minimize the worst case scenario.

To put this problem into "math", there is an integer X between 1 and 100. You may guess an integer and I will tell you if X is " ≥ " or " < " your guess. If I ever say " ≥ " twice, you cannot guess again and must tell me what X is. You are to minimize the worst case for the number of guesses.

A clear naive strategy is just to go up the floors, one at a time, and when the marble breaks you know exactly what floor it happened on. Of course, the worst case here will need 100 drops and you didn't even try to make use of the fact that you have two marbles (actually, that solution is optimal if you only have one marble).

Two Spheres In One

2009-09-17T12:32:00.000-07:00

I suppose in recent posts involving the Axiom of Choice, I promised that I would give a proof of the Banach-Tarski paradox here. Not that anybody actually cares to read it, but the point of this blog is for me to feel smart while I rant about math, so I will do that.

First of all, we need to do a bit of group theory, because really all of the important math is just group theory. First, consider rotations of the three dimensional unit ball. These rotations form a non-commuting group, as you should know. Specifically, let A be a rotation of the sphere around the x-axis by 1 radian, and let B be a rotation of the sphere around the y-axis by 1 radian. A and B do not commute, and Aⁿ and Bⁿ are never equal to the identity (since there are 2&pi radians in the full rotation and 2k&pi cannot ever be rational for rational k). It is also important to know that no string of A's and B's and their inverses (for example AB³A^-2BA²) will ever be equal to the identity, unless the inverses cancel exactly (so A^-2BB^-1AB^-1BA is the identity trivially, but ABA^-1B^-1 will not be).

Alright, now let us consider S to be the set of all strings involving A, A^-1, B, B^-1 with no term right next to its own inverse (so if there were to be any of those, cancel them). The empty string is also in S, to be the identity element. The strings in S can be arbitrarily long, though none of them are actually infinitely long. S clearly forms a group (the free group on two elements, to be specific).

Next, let us decompose S into 5 sets. S(A) will be elements of S staring with A, S(B) will be elements of S starting with B, S(A^-1) and S(B^-1) defined similarly, and S(e) has the last element, the empty string. Clearly S is the union of these 5 disjoint sets. Next, let us denote multiplication of an element x by a set P as the set you get when you multiply x by each element in P (so A times {A^-1, BA, A, B^-1} = {e, ABA, A², AB^-1} with e as the empty string).

Now, one can see that A times S(A^-1) gives you every element of S, except the ones that start with A (as S(A^-1) never has an element that starts A^-1A, but it will have plenty that start A^-1B , for example). Even the empty string is in A S(A^-1). So we can say that S is the union of the disjoint sets S(A) and A S(A^-1). Similarly, S is the union of the disjoint sets S(B) and B S(B^-1).

Something a bit weird has happened here, since now we see S = S(A) &cup S(B) &cup S(A^-1) &cup S(B^-1) &cup S(e) = S(A) &cup A S(A^-1) = S(B) &cup B S(B^-1). Technically, this isn't a problem, as all of those sets (except S(e)) are infinitely large anyway, so there isn't a problem with S being one-to-one with some of its own subsets. Anyway, enough group theory, back to the sphere.

Now, consider a point on the surface of the sphere. Consider all the places you can reach from that point by using elements of S. There is an element that is A away, an element that is B away, an element that is ABA^-3B²A away, and so on. These elements cannot cover the entire sphere (there are only countably many elements of S, and uncountably many places on the sphere to reach). We will consider an equivalence class on the sphere (as we always do when we are about to use the axiom of choice), two points on (or in) the sphere will be equivalent if you can move one into the other just by using rotations in S. Now use the Axiom of Choice to select one element from each equivalence class and put them into a set V. So for each point on the unit ball (the solid sphere, that is), there is exactly one element of V that can reach that point with exactly one of the rotations in S, and no two elements of V can reach eachother using rotations in S.

We will break the unit ball U up into 5 pieces. Places in U that can be reached from an element of V and a rotation in S(A) will be called U(A). Places in B that can be reached from an element of V and a rotation in S(A^-1) will be called U(A^-1). Similarly we define U(B), and U(B^-1). U(e) is just V itself. So U is the union of the 5 disjoint sets U(A), U(B), U(A^-1), U(B^-1), and U(e).

Now is where the "magic" happens. Since we know that A^-1S(A) is S(A) &cup S(B) &cup S(B^-1), then A^-1 applied to U(A) gives us U(A) &cup U(B) &cup U(B^-1) &cup U(e). Similarly, B^-1 applied to U(B) gives us U(B) &cup U(A) &cup U(A^-1) &cup U(e). Thus, U(B) and U(B^-1) can construct the entire unit ball, and U(A) and U(A^-1) can also give us the entire unit ball.

I suppose I have dropped off U(e), as well as the issue of the fixed points under rotations A and B (specifically, the x-axis and the y-axis). I'm not going to handle those properly, but the main point has already been made anyway.

It may seem very strange that you can rotate U(A) and get U(A) unioned with other sets, but this actually can happen without the Axiom of Choice. Consider the unit circle on the 2-plane. Starting with the point (1,0) on the x-axis, consider the set of points that you hit by rotating that point counter-clockwise 1 radian at a time. So you get a countably infinite set of points, as that list never crosses itself, but does not cover the whole circle (it never hits the point at -1 radian, or the point at &pi radians, for example). Now rotate that set clockwise by 1 radian. The point at 1 radian moves to the point at 0, the point at 6 radians moves to the point at 5 radians, and the initial point at zero radians moves to the point at -1 radians. This new set covers all the points in the old set, and has one extra point also, very strange (actually, this is how you can handle the set U(e), you basically "rotate it out of existence" by combining it with U(A) or something). Cardinality and measure are not an issue here, as the set is countable with measure zero both before and after the rotation.

Anyway, thats really it for the proof. You can also extend the proof to take any finite sized object, cut it into finitely many pieces, and reassemble them into any other finite object (the standard example is to arrange a pea into the sun). Note that this does require three dimensions or more, as you need two non-commuting rotations.

Infinitely Powerful Logicians

2009-09-01T12:29:00.000-07:00

Time to post the solution to my last problem involving the Axiom of Choice. First off, the mere existence of a solution to this problem should terrify you. The reason is that if only finitely many people are wrong, that means that there is a last person that is wrong. So, if you were to look at the guesses of the logicians, you would find that they have some right and some wrong for a while, but then suddenly there is a last person who is wrong and everybody after that is just magically right, in spite of the fact that those people had no special information. Somehow, they were able to use the infinite hats in front of them to deduce their own hat colour, even though it was independent.

It is also worth saying that in most problems like this, where everybody must guess simultaneously, you try to arrange the peoples guesses so that when something goes wrong, it goes maximally wrong. This is needed because each person on their own has a fixed probability of being wrong, so you simply try to make those fixed probabilities non-independent so that you minimize the chance that things go wrong.

In this problem, each person has a 50% chance of being wrong at the time they make their guess. This is a bit of a problem, as that means that on average half of the people will be wrong and there is very little one can do about it. Fortunately, the Axiom of Choice destroys usual notions of probability. It does this by creating sets of non-defined length. Simply put, length can be defined in terms of the probability that you were to pick an element of the set. Specifically, if you have a subset S of [0,1], and you were to pick an element of [0,1] at random, the probability that you would get an element of S would be L(S), the sets length. If the Axiom of Choice allows for sets with no length, it also allows for sets that we have no well defined probability of picking an element of.

Alright, time to start constructing the solution. Consider the sequence of hats that the logicians are wearing to be an infinite binary sequence, starting from the back of the line (x₁, x₂, x₃...). Use that binary sequence to construct a real number, y, between zero and one, represented in binary as y=0.x₁x₂x₃...

Next, construct an equivalence class on the reals between zero and one. We will consider two real numbers, a and b, to be equivalent if, when expressed in binary, a and b differ in only finitely many decimal places. Now we use the axiom of choice to select one element from each equivalence class and call the set V. So, for all z between zero and one, there is exactly one element of V that differs from z in only finitely many decimal places. Also, no two elements of V differ from eachother in finitely many decimal places. Have the logicians agree on the set V and memorize it.

Now, each logician is to look at the hats in front of them, and they know "most" of the binary sequence of the actual number they are in (calling that y). That is to say, logician number 6 can consider y=0.x₁x₂x₃x₄x₅x₆x₇x₈x₉.... The first 6 digits are unknown to him, but all the rest are known. Every single logician knows all but finitely many of the digits in the binary expansion of y. As a result, every logician is aware of what equivalence class y is in, and they all have agreed on an element in V (call it k) that differs from y in only finitely many places. Thus, if everybody guesses assuming that y actually is k, then only finitely many of them will be wrong.

Naturally, this requires that the logicians be capable of an infinite amount of work, they must find a choice function, then they must memorize all the elements in the set V (or just memorize the choice function, its the same). Next they must examine all of the (infinite) hats in front of them to figure out what equivalence class they are in to select an element of V.

But, if they can do all of that, they can accomplish the rather miraculous task of solving this problem.

It is also worth saying that they can solve this problem even if the hats are not restricted to being white or black. As long as they know the set of colours that the hats can come from, they can do the exact same thing. Instead of considering binary sequences, they simply consider trinary sequences, or hexadecimal, or whatever it takes to get as many digits are there are hat colours. If that doesn't make you think the Axiom of Choice is crazy, I don't know what will.

The Axiom Of Choice

2009-08-24T16:56:00.000-07:00

So, when I started this blog, the intention was to do mostly logic puzzles with the occasional math rant. I suppose I have done a few mathematical rants, but they have always been about logic puzzles themselves, as opposed to just random rants about stupid things that exist in set theory. For those who just want a logic puzzle, you can skip to the end of this rant and read the one I am putting up this week, but I'm going to warn you, you aren't going to be happy with it. Anyway, back to stupid things in set theory.

By far, the stupidest thing that exists in set theory is the Axiom of Choice. Anybody who reads this blog is already familiar with it, but I might as well give my formal statement of it:

Given a collection of nonempty sets S, there exists a function f such that for all sets X in S, f(X) is an element of X.

Specifically, f is a function that chooses exactly one element from each set X in S, and f(X) tells you specifically which element the function has chosen.

This can sound innocent enough, all it says is that if you have a bunch of sets, it is possible to choose one element from each of those sets. The problem can come if the collection is infinitely big, its not clear that there would be a "rule" to tell you exactly how to select exactly one element from each of those sets.

For example, consider that we are only using the natural numbers, {0,1,2,3,...}. Then if we are told that S contains only nonempty subsets of the naturals, it is easy to find a choice function, simply always choose the smallest element of X (as it turns out, the Axiom of Choice is trivially true in a universe that only has the natural numbers). However, now let us suppose that we are using the real numbers, S might be the set of all nonempty subsets of real numbers, the function that would allow us to select exactly one element from each of these sets would be difficult to construct indeed. The Axiom of Choice is the postulate that there is such a function that would allow us to do just that, even though it gives no hint as to what such a function would look like.

How about some sort of middle ground, let us consider the integers, {....-3,-2,-1,0,1,2,3,.....}. If S contains nonempty subsets of the integers, you can still come up with a choice function without the Axiom of Choice. Specifically one can just use "If X contains any nonnegative integers, pick the smallest nonnegative one. If X contains only negative integers just use the largest negative integer." This rule will always pick out an element, so the Axiom of Choice is also not needed for the integers.

This is actually as if we had rearranged the order of the integers to be {0,1,2,3,....-1,-2,-3,....}, lining up all the positive integers in correct order, and then saying that -1 is greater than all the positive ones and then moving 'up' with the negative integers. Now under this new ordering of the integers, the rule is simply to "pick the smallest one". One could imagine that if there was some way to line up the reals such that every subset had a smallest element that the Axiom of Choice would then be unnecessary.

This leads us to a pretty general statement about the Axiom of Choice. Specifically, we ("we" being basically every set theorist on the planet) will consider orderings on sets, a concept of "greater than". First, an ordering will be called a "partial order" if whenever a>b and b>c then a>c follows. This is a reasonable demand to make on something you would want to call a concept of "greater than". Next, a partial ordering will be called a "total order" if for all a and b in the set, exactly one of these is true: a>b, b>a, a=b. Note that a partial ordering did not demand this, partial orderings can have elements where two elements are incomparable. Most orderings that one deals with in math are total orderings (like the usual one on the reals). Finally a total ordering is called a "well order" if for any subset there is a smallest element. The only well ordering that one deals with normally is that on the naturals, but one can see that you can give the integers a well ordering as well.

We can see that if you can find a well ordering for a set, you get a choice function right away and the Axiom of Choice is not needed. The "Well-ordering theorem" is the idea that every set can be well ordered (and needs that Axiom of Choice to prove). We have seen that if the Well-ordering theorem were to be true on its own, the Axiom of Choice would come for free, so you can see that the Axiom of Choice will be true if and only if the well-ordering theorem were true.

Alright, that is all fun and good (and probably most of you stopped reading ages ago), but what is really the problem with the Axiom of Choice? I mean, it seems intuitive enough, and probably helps prove some things (like the Well-ordering theorem), what could go wrong?

One of the basic problems shows up with the Banach-Tarski paradox. You can go look it up if you like, and I'll give a proper proof of it in the next few weeks, but the paradox is that it is possible to take a solid sphere, divide the sphere up into a number of disjoint pieces and, using only translation and rotation of the pieces, reassemble them into two copies of the original sphere, each the size of the original sphere. It seems like it might be a trick using an infinite number of pieces or something, but you can actually do it using just 5 pieces.

One might be concerned about conservation of volume in the Banach-Tarski paradox, how you could cut up a sphere of fixed volume and make something with twice as much volume using just translation and rotation. The trick is that the pieces do not have any well defined volume, and so conservation goes out the window. Actually, it is convenient to show how to use the Axiom of Choice to construct an object with no well-defined volume.

We will constrain ourselves to the one dimensional real line here, and we will have a concept of length. The length of a set S will be denoted L(S). We will denote adding a number to a set to mean that we construct a new set by adding that number to each element of the set, se {1,2,4}+5 is the set {6,7,9}. It is clear that we would want our length function to be translation invariant, so that L(S+x)=L(S) for any real number x. Next, if we take the union of two disjoint sets we want the lengths to add, so that L(S ∪ P)=L(S)+L(P) if S and P are disjoint (this also means that if P is a subset of Q then L(P) ≤ L(Q)). Finally, we want the length of intervals to be what we expect them to be, that being L([a,b])=b-a for b>a. Note that there can be nonempty sets with zero length, such as a set with only single point elements.

Alright, this is enough properties of length to prove that (with the Axiom of Choice) there exists a set that cannot be evaluated with this function. Let us consider an equivalence relation on the real numbers, two real numbers will be said to be equivalent if they differ by a rational number (this means that for each number, the set of numbers equivalent to it is a pattern that looks like the rationals). The set V will be constructed by choosing one element from each equivalence class that is also between 0 and 1. So, every real number differs from exactly one element of this set by a rational number, and does not differ from any other elements of this set by a rational number.

Next, list all the rational numbers between -1 and 1 and assign then each to a natural number, so that x_n represents the list of all rationals between -1 and 1. It is clear that for every real number y between 0 and 1 there is an n such that y+x_n is an element of V, so that y is an element of V-x_n. V-x_n will also spill out past (0,1) and hit some reals between -1 and 2, but will not get all of them. We also know that V+x_n is disjoint from every V+x_m for n and m different, as V had only one number from each equivalence class.

Now, we can consider E to be the union of the disjoint sets V+x_n. It is clear that (0,1) is a subset of E and E is a subset of (-1,2). Thus 1 ≤ L(E) ≤ 3, but we also know that L(V+x_n)=L(V). So If L(V) is zero, then E is the disjoint union of sets of length zero, and it has length zero, but if L(V) is nonzero, then E is the disjoint union of infinitely many sets with nonzero length and has infinite length.

Thus, we cannot have a function L that consistently assigns length to every set that exists in a world with the Axiom of Choice. This sort of thing will come up again later when I show the proof of the Banach-Tarski paradox and have to deal with the issue of volume conservation.

For now, its time for a logic puzzle (using the word "logic" loosely here), I first learned this one on the forums at xkcd:

You have a countably infinite number of logicians standing in a semi-infinite line. Each of them is wearing a hat which is either white or black. They can all see the (infinite number of) hats in front of them, none of the (finitely many) hats behind them and not their own hat and they all know their own position in the line. They must each simultaneously write down a guess about their own hat colour. They win the game if only finitely many of them are wrong, they lose if an infinite number of them guess wrong. Before the hats are assigned they may strategize. Using the Axiom of Choice, prove the existence of a strategy that guarantees their victory.

Numbers Are Crazy

2009-08-21T12:30:00.000-07:00

Probably enough time has passed since my silly math problem. If you have spent some time working on it, you will see that you can basically create every number around 21 easily, but getting to 21 is a bit harder.

To start, we might as well try to make 21 by constructing 7x3, thats basically all 21 is, getting there by any sort of addition is going to be pretty tricky. We already have a 7, so how can we make a 3 from {1,5,6}? Well, basically we can't. We do have a 6 though, so if one considers 21 to be 7x6/2, we just need to use the 5 and the 1 to make a 2 (also clearly impossible). The real trick though is to use grade school division trick that a/(b/c)=ac/b, so 21 is also 6/(2/7). We now need to use {1,5,7} to make 2/7, and that one is pretty easy to do. Of course, the solution is:

6 ÷ (1 - (5 ÷ 7))

The neat blind spot is that people tend to dismiss division right out when they are given this puzzle. There is no division that you can do with these numbers that will not exit the integers, and people tend to assume that once you leave the integers you won't get back.

The double division is also the solution for the "{3,3,8,8} makes 24" puzzle, so I won't bother saying the solution specifically, its pretty simple now.

Silly Math

2009-08-11T13:47:00.000-07:00

Alright, I've once again run out of standard "find the optimal strategy" type problems, its time for a seemingly simple math problem. I can't recall when I first learned this one, I've known it since at least grade 9:

Using the numbers 1, 5, 6, and 7, each once and only once, and +, -, x, and ÷ as much as you like, construct a formula for the number 21. You may also use as many brackets as you like.

To be clear, there are no stupid tricks in this problem, like sliding the 1 and 5 together to make 15. The solution is exactly of the form _*_*_*_, where _ is replaced by the numbers from {1,5,6,7} each used once, and * is replaced by {+,-,x,÷} (and can use repeats). You also have as many brackets as you need to control order of operations.

I always find this problem rather interesting because typically this sort of problem is either trivial or impossible, but this one is neither. There is a funny blind spot people tend to have with this.

Also, if you are in the mood, try using 3,3,8,8 to make 24 with the same rules. This one will be much easier after you have solved the first one.

Two Is Not Enough

2009-07-30T13:46:00.001-07:00

Alright, I'm going to be gone for a week soon, so I better post the solution to the latest hats in a line problem.

The solution starts with the standard thing of spending the ones you can afford to get wrong right off the bat and then having everybody else correct. Surprisingly, you can use the two people in the back to tell the next three people their hat colours. Numbering the people from back to front, person 1 can see all the way to person 5. First, person 1 will volunteer if person 3's hat colour is black, and person 2 will volunteer if person 3's hat colour is white. Person 1 will make his guess equal to person 4's hat colour, and person 2 will make his guess equal to person 5's hat colour. In this way, we now have the back three people knowing their hat colour and we cannot afford any more incorrect answers.

If you had tried solving this problem but did not notice a way to get three people to know their hat colours, you might want to stop reading and go try again, that first step is crucial.

Alright, now for the rest of the solution:

Call the current back people A,B,C,D,E,F, and G. A can see all the way to E. A and B will guess their hat colours next, A will guess first if D and E have the same colour hat, B will guess first if D and E have different colours of hat.

Now D knows his own hat colour (he can see E's), and E knows his hat colour relative to D's. Next C and D will guess. C will guess first if F and G have the same hat colour, and D will guess first if F and G have different hat colours. When D makes his guess (either first or second), E will learn his hat colour. F knows his hat colour (he can see G's) and G knows his hat colour relative to F. The part of the solution in this paragraph is stable and can propagate all the way forward.

And at the end, when everybody knows their own hat colour, everybody can just volunteer and finish things off.

Slightly Less Myopic Hats In A Line

2009-07-22T11:40:00.000-07:00

So, you can tell that I've been wandering through the xkcd forums for puzzles when I manage to make four posts in one month after having done about one post a month for so long. Anyway, here you go:

One hundred people are standing in a line, each of them wearing either a black hat or a white hat. They all can see the hats on the four people directly in front of them, no hats behind them and not their own hat. Each round, a man in a black suit will ask each person in the line if they would like to guess their own hat colour now, the answer they give is secret, nobody else in the line can hear. The man will then select one of the people who volunteered and ask their hat colour. That person is then removed from the line and a hole in left in the line. Everybody in the line is made aware of who was selected to guess their hat colour and what they guessed. The people may only guess "black" or "white". Then a new round starts with the man asking who would like to guess their hat colour now.

The players lose the game if ever more than two people get their hat colour wrong, or if during any round nobody volunteers to guess. The players win if everybody has finished guessing their hat colour and no more than two people are wrong. Before the hats are assigned the players may strategize, find a strategy that is certain to win assuming the man in black (who also assigned the hat colours) is an adversary.

Its the same as the other hats in a line problem (I basically copy-pasted it), but now holes will be left when people leave and they have a sight range of 4.

Just to be clear, if we number the people starting from the back, person 1 can see the hats on each of {2,3,4,5}. If person 3 now makes a guess and leaves the line, person 1 can now see the hats of {2,4,5}, but still cannot see the hat on 6.

Two Is Enough

2009-07-20T11:21:00.000-07:00

Time for the solution to the hat problem from last time. Not really much to the solution, as Mark pointed out in the commentary its just about parity.

To start, we will number the people from 1 to 100, with the person at the back on the line numbered 1, so N can see the hats of people N+1 and N+2. First thing we need to do is have the two people at the back of the line know their hat colours:

First, person 1 volunteers to guess, and guesses the hat colour of person 3. Next, person 2 volunteers to guess and guesses the hat colour of person 4.

The adversary will ensure that both of those guesses were wrong, so now we have a new problem where the back two people know their own hat colour and we cannot afford anybody to guess wrong. Fortunately, they can now see the hat colour of person 5. They use that to decide who guesses next:

If person 5 has a white hat, person 3 guesses what he knows his own hat to be. If person 5 has a black hat, person 4 guesses what he knows his own hat colour to be.

They are no longer transmitting information by what they guess, it is instead done by who makes the guess. Naturally, whatever happens, the line will shift back and you have the two people at the back of the line with full knowledge of their own hat colour. The person at the very back guesses if the next "unknown" hat is white, and the second person from the back guesses if it is black. The solution works by induction, until only two people are left in the line, when they both know their own hat colour and both of them volunteer to guess (letting the adversary helplessly decide how it ends).

If one states the problem differently, so that instead of a "win-loss" scenario there was some sort of bet based on how many you got wrong, this solution also has the advantage that a mistake by one of the players only results in one extra person being wrong, rather than an entire chain.

Actually come to think of it, that would be a better way to word the problem, to minimize the number of people who guess wrong rather than saying outright how many you can afford. When I post the harder version of this problem I might word it that way.

Myopic Hats In A Line

2009-07-15T10:51:00.000-07:00

That counter thing on the right for my blog posts seems to suggest that its been some time since I've had more than one post in a given month... I guess its time to do something about that. Anyway, this puzzle is one I found on the forums at xkcd:

One hundred people are standing in a line, each of them wearing either a black hat or a white hat. They all can see the hats on the two people directly in front of them, no hats behind them and not their own hat. Each round, a man in a black suit will ask each person in the line if they would like to guess their own hat colour now, the answer they give is secret, nobody else in the line can hear. The man will then select one of the people who volunteered and ask their hat colour. That person is then removed from the line and the line is shifted back a step to fill the hole. Everybody in the line is made aware of who was selected to guess their hat colour and what they guessed. The people may only guess "black" or "white". Then a new round starts with the man asking who would like to guess their hat colour now.

The players lose the game if ever more than two people get their hat colour wrong, or if during any round nobody volunteers to guess. The players win if everybody has finished guessing their hat colour and no more than two people are wrong. Before the hats are assigned the players may strategize, find a strategy that is certain to win assuming the man in black (who also assigned the hat colours) is an adversary.

Its some sort of variation on "standard line hat rules", the people are also short-sighted.