## The Most Difficult Hunt Puzzle: 50/50

The puzzle titled “50/50” was the most difficult puzzle in MIT Mystery Hunt 2013. It is a puzzle in which information is hidden in the probability distribution of coin flips. I consider it the most difficult puzzle of the hunt because it took the longest time to test-solve and we were not able to solve all * four* layers of the original puzzle. As a result, one of the layers was removed. I think this puzzle is very important and should be included in statistics books and taught in statistics classes. If I were ever to teach statistics, I would teach this puzzle. By the way, this elaborate monstrosity (meant as a compliment) was designed by Derek Kisman.

I am not sure that the puzzle is working on the MIT server. The puzzle is just a coin flip generator and gives you a bunch of Hs (heads) and Ts (tails). Here is the solution.

When you flip a coin, the first thing to check is the probability of heads. In this puzzle it is fifty percent as expected. Then you might check probabilities of different sequences of length 2 and so on. If you are not lazy, you will reach length 7 and discover something interesting: some strings of length seven are not as probable as expected. The two least probable strings are TTHHTTH and HTHHTTT, with almost the same probability. The two most probable strings are TTHHTTT and HTHHTTH, with the matching probability that is higher than expected. All oddly behaving strings of length 7 can be grouped in chunks of four with the same five flips in the middle. In my example above, the five middle flips are THHTT. Five flips is enough to encode a letter. The probabilities provide the ordering, so you can read a message. In the version I tested it was “TAXINUMBLOCKS.” In the current version it is “HARDYNUMBLOCKS.” Keep in mind that the message encoded this way has to have all different letters. So some awkwardness is expected. The message hints at number 1729, a famous taxicab number, which is a clue on what to do next in the second step.

What do you do with number 1729? You divide the data in blocks of 1729 and see how the k-th flip in one block correlates with the k-th flip in the next block. As expected, for most of the indices there is no correlation. But some of the indices do have correlation. These indices are close together: not more than 26 flips apart. Which means the differences will spell letters. Also, there is a natural way to find a starting point: the group of indices spans only a third of the block. In the original version the message was: “PLEASEHELPTRAPPEDINCOINFLIPPINGFACTORYJKHEREHAVEAPIECEOFPIE.”

Now I want to discuss the original version, because its solution is not available online. Here is Derek’s explanation of what happens in the third step:

So, this punny message is another hint. In fact the sequence of coin flips conceals pieces of the binary representation of Pi*e. These pieces are of length 14 (long enough to stand out if you know where to look, but not long enough to show up as significant similarities if you compare different sessions of flips), always followed by a mismatch. They occur every 1729 flips, immediately after the final position of the 1729-block message. The HERE in the message is intended to suggest looking there, but you can probably also find them (with more effort) if you search for matches with Pi*e’s digits.

The 14-flip sequences start near the beginning of the binary representation of Pi*e and continue to occur in order. (ie, every 1729 flips, 14 of them will be taken straight from Pi*e.) However, between sequences, either 1, 3, or 5 digits will be skipped. These lengths are a sequence of Morse code (1=dot, 3=dash, 5=letter break) that repeats endlessly, with two letter breaks in a row to indicate the start:

– …. ..- ..- ..- – ..- -..- ..- ..- ..- …. ..- …. – ..- ..- …. ..- ….

Translated, this gives the message “THUUUTUXUUUHUHTUUHUH”.

(Aside: I didn’t use Pi or e individually, because one of the first things I expect some teams will try is to compare the sequence of flips with those constants!)

As I said before, we didn’t solve the third step. So Derek simplified it. He replaced “PIECEOFPIE” by “BINARYPI”, and made it the digits of Pi, rather than of Pi*e. We still couldn’t solve it. So he changed the message from the second step to hint directly at the fourth step: “PLEASEHELPTRAPPEDINCOINFLIPPINGFACTORYJUSTKIDDINGTHUUUTUXUUUHUHTUUHUH.” But the binary Pi was still trapped in the coin flipping factory.

Here is Derek’s explanation of the fourth step:

Almost there! This message looks like some sort of flip sequence, because it has several Ts and Hs in there, but what of the Us and Xs? Well, U just stands for “unknown”, ie, we don’t care what goes there. And there’s only one X, so it seems significant!

The final step is to look for every occurrence of this pattern in the sequence. The flips that go where the X is are the final channel of information. You’ll find that they repeat in an unvarying pattern (no noise!) with period 323=17*19. There’s only one way to arrange this pattern into a rectangular image with a blank border, and it gives the following image:....................X..XXX.XXX.......X..X...X.X.......X..XXX.XXX.......X..X...XX........X..X...X.X.......X.....X..........X.....X..........X....XXX.........X.....X..........X................X.....XXX...X....X....XXXXX.XX...X....XX.XXXXX...X......XXXXXX....X...X.XXXXXXXX....XXX...XXXXX.XX..........XXX...X..................The final answer is the French word for fish, POISSON, a word heavily related to statistics!

The answer POISSON didn’t fit in the structure of the Hunt. So Derek was assigned a different answer: MOUNTAIN. He changed the picture and it is now available in the official solution to the puzzle. He adjusted his code for coin flips so that the picture of a mountain is hidden there. But the digits of Pi are still trapped in the flips. They are not needed for the solution, but they are still there.

Derek kindly sent to me his C++ program for the latest version of the puzzle. So if the MIT website can’t generate the flips, you can do it yourself. And play with them and study this amazing example of the use of statistics in a one-of-a-kind puzzle.