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.