Blind Man Walking

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

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

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

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

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

Pascal's Modified Triangle

Well, time to post the solution to the coins in a bucket problem. First, just to get an idea of how I got to the solution, consider the answer in the case where the coins go into the bucket randomly, with 50/50 chance, rather than that weird weighted probability that was actually used in the problem. Let P(n,m) represent the probability that you arrive in the situation where there are n coins in the left bucket and m coins in the right bucket. P(1,1) is clearly 1. Next P(2,1) and P(1,2) are both easily found as 1/2. Then P(3,1) and P(1,3) are 1/4, since you must first get to (2,1) or (1,2) and then there is a 1/2 chance that the coin goes in the right place, while P(2,2) is 2/4, as the probabilities must sum to 1.

You basically wind up writing out Pascal's triangle, normalized so that the sum of the elements in any row comes out to 1. P(n,m) will be _n+m-2C_n-1/2^n+m-2. Each element of P(n,m) is the average of the two above it.

Now, in the case of the actual problem, we will still let P(n,m) denote the probability that you arrive in the situation where there are n coins in the left bucket and m coins in the right bucket. As before, P(n,m)=P(m,n), and the sum over all values of n and m such that n+m is held constant should be &Sigma P(n,m)=1.

So, as before P(1,1)=1 and P(2,1)=P(1,2)=1/2. Now, to get to (3,1) you must be at (2,1) and there is a 2/3 chance the coin goes in the right place. So P(3,1)=2/3*P(2,1)=1/3 also P(1,3)=1/3 by symmetry, and by normalization P(2,2)=1/3. Next, for (4,1), you must be first at (3,1) and then there is a 3/4 chance the coin falls into the right place, so P(4,1)=3/4*P(3,1)=1/4 and P(1,4)=1/4 so by normalization and symmetry we must also have P(3,2)=P(2,3)=1/4. So, our triangle has 1, then 1/2,1/2, then 1/3,1/3,1/3 and then 1/4,1/4,1/4,1/4.

Weird, it appears that P(n,m) depends only on n+m and not on the particular values. All distributions of n and m are equally likely across constant n+m. Let us try to prove the guess P(n,m)=1/(n+m-1). We know that this is true for n+m equal to any of {2,3,4}. P(n,m) must obey the relation:

P(n,m)=(n-1)/(n+m-1) P(n-1,m) + (m-1)/(n+m-1) P(n,m-1)

The first term is the chance you got to (n,m) by a coin falling into the left from (n-1,m) and the second is from a coin falling into the right from (n,m-1). Now we can prove our general formula for P(n,m) by induction on n+m. Assume it holds true for n+m=K, then for n+m=K+1

P(n,m)=(n-1)/(n+m-1)*1/(n+m-2) + (m-1)/(n+m-1)*1/(n+m-2)
P(n,m)=1/(m+n-1)

Alright, so for the 1000 coin case, the 999 differet cases (1,999), (2,998), (3,997),.....(998,2), (999,1) are all equally likely. So the bucket with less coins has any of {1,2,3,...499} coins with probability 2/999 and 500 coins with probability 1/999. The solution is then

2/999*&Sigma n +1/999*500
=(2/999)*(499*500/2)+500/999
=500^2/999
=250+250/999

Slightly more than 250. It would be 250.5 if not for the fact that 500 coins in the lesser bucket is slightly less likely.

Coins In A Bucket

Time for a random new puzzle. I managed to solve this one last week, its not very hard but has a really neat solution. I first learned this one from the forums on xkcd:

You have two buckets that you are throwing coins into. The probability that a coin goes into a particular bucket is proportional to the number of coins currently in that bucket. The buckets are initially seeded each with one coin. You have 1000 coins in total, and after you have thrown all of those coins into the buckets you look into the bucket which has fewer coins in it. On average, how many coins are in that bucket?

In particular, just so you understand the whole "probability that a coin goes into a particular bucket is proportional to the number of coins currently in that bucket" thing, if the two buckets have 5 and 2 coins in them currently, then the next coin will go into the bucket with 5 coins with probability 5/7 and the one with 2 coins with probability 2/7.

The solution itself isn't actually all that neat, but there is something about this situation that you find along the way that is really cool.

End Of The Line

So, its time for the solution to the Hats in a line problem. I've always like this problem, because when I first learned it I got lucky and managed to solve it in under an hour. Its not uncommon though to take a few days.

Anyway, the solution is easy enough:

Treat the hat colours as 0 or 1, the person at the back states the value you get by taking the XOR of the front 99 hats. The next person from the back can see the front 98 hats and knows the parity, so that is enough for them to be correct. The next person can see the front 97 hats and knows that the person second from the back was correct, and knows the parity of the first 99 hats, so that is enough information for them. It is easy to see that each person will be correct now except possibly the one at the back, who is 50/50 to survive.

Its not hard to see this is optimal, as the person at the back cannot possibly do better than 50/50 with zero information, and everybody else is 100%. Its also interesting to note that having on "idiot" in line will not kill everybody in front of them. They will be wrong, and they will screw up the person in front of them, but after that the two mistakes will cancel out. This is even true if the person at the back of the line is incorrect for some reason.

Hats In A Line

Alright, time for a new puzzle. I haven't put much thought into what puzzle I wanted to post next, so I guess I'll just go with one I have known for ages. Possible that most of my readership has already seen this also (all two of you), but I'm also just posting it for my own archiving purposes.

Anyway, I first learned this one from Bart:

There are 100 people in a line wearing hats. Each hat is either white or black, and each person can see all the hats in front of them, not their own hat or any hat behind them. Then, some disreputable men in black suits will come and ask each man a simple question: "What colour hat are you wearing?". They begin asking at the back and move forward in the line one person at a time. The people can only answer with "white" or "black". For each person, if that person is correct they are silently released, if that person is incorrect they are silently killed. Every person in front of them can hear their answer.

The people may get together and plan before the hats are assigned. What strategy guarantees the maximum number of people survive?

I would like to call the rule about seeing all the hats in front of you and none behind you "standard line hat rules", but theres only one other problem I know of that even uses that rule, and it involves the axiom of choice.