Impossible Masses

Man, two weeks without posting, who's driving this thing? Anyway, time for a new puzzle. I first learned this one from the math room on KGS:

Consider you have a collection of 11 weights, each with a rational mass. This collection has the property that if you remove any one weight the remaining 10 can be sorted into two piles of 5 weights each, and each with the same total mass. Prove that this is impossible unless every one of the weights has the same mass.

By "a rational mass" I really mean that the ratio of any two of their masses is rational. It feels a bit weird to ask for a proof in a logic puzzle, but the proof is really quite elegant, and understandable without complicated math.

It can also be proven when the masses are real instead of rational, but it is much more abstract to do that.

Notation, Notation, Notation

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

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

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

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

Move 1: D

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

Move 2: H

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

Move 3: D

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

Move 4: S

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

Moves 5-7: D,H,D

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

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

Blind And Numb

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

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

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

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

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

Blind Man Winning

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

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

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

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

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

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

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

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

Now you win.

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

Blind Man Walking

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

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

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

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

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

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.