Labeled Masses

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

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

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

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.