Tanya Khovanova's Math Blog

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.

When the MIT Mystery Hunt was about to end, I asked my son Sergei, who was competing with the team “Death from Above,” what his favorite puzzle was. I asked the same question to a random guy from team “Palindrome” whom I ran into in the corridor. Surprisingly, out of 150 puzzles they chose the same one as their favorite. They even used similar words to describe it. Calling it a very difficult and awesome puzzle, they both wondered how it was possible to construct such a puzzle.

The puzzle they were referring to is “In the Details” by Derek Kisman, which you can see below.

TWELEVELTWONSHELMUMUOERAIYRANL
QAPIUNPIQAYDPEPIRPRPKVOYESOYOR
ELRATFDTELDTTFDTBWNLMUTFONYDWJ
PIOYJMHAPIHAJMHAAOORRPJMYDANFC
MUOZCGTFBWIRYDHIRAIRTFNCUENCUE
RPVQUHJMAOHKANJUOYHKJMZKBNZKBN
IRONSHOZGOTFUEELTFOEELUEYDOETF
HKYDPEVQDNJMBNPIJMKVPIBNANKVJM
BWIYNLTFSHHIELTWGOYDONDTYDHIOE
AOESORJMPEJUPIQADNANYDHAANJUKV
SHDTYDRPBWUEBWIYTWTWTFYDMUELMU
PEHAANAJAOBNAOESQAQAJMANRPPIRP
ONTWELBWLMSHELTFUEBWBWLMOZEVHI
YDQAPIAOGIPEPIJMBNAOAOGIVQUNJU
DTCGUEYDRPEVNCIREVIRTWUEUETWON
HAUHBNANAJUNZKHKUNHKQABNBNQAYD
IRUERAMUTFELTWONTFOEOEEYDTNLYD
HKBNOYRPJMPIQAYDJMKVKVHWHAORAN
ELGORPNCTFDTYDSHYDELPKTFOZRACG
PIDNAJZKJMHAANPEANPIDFJMVQOYUH
DTMUWJOETFYDELMUMUGORAONIRDTCG
HARPFCKVJMANPIRPRPDNOYYDHKHAUH

_ _ _ _ _ _ _ _

The puzzle looks like a word search, but I can tell you up-front: you can’t find all the words in the grid. You can only find six words there. So there is something else to this puzzle. I will discuss the solution later. Meanwhile I will ask you very pointed questions:

• Where are the other words?
• What is the meaning of LEVEL TWO staring at us from the first row?
• Where is LEVEL ONE?
• What do these very non-random words have in common?

The easiest of the puzzles I made for the MIT Mystery Hunt 2013 was “Something in Common.” I collaborated on this puzzle with Daniel Gulotta. Ironically, it was the most time-consuming of my puzzles to design — well over a hundred hours. I can’t tell you why it took me so long without revealing hints about the solution, so I will wait until someone solves it.

I received a lot of critique from my editors for suggesting puzzles that were too easy. When, during the test-solve, I realized that this puzzle was one of the easiest in the hunt, I requested permission to make it harder. It would not actually have been difficult to make it harder: I could have just replaced some specific words with more general ones. Unfortunately, we didn’t have time for a new test-solve, so the puzzle stayed as it was. That turned out to be lucky.

This puzzle was in the last round. By the time the last round opened, we knew that the hunt was much more difficult than we had anticipated. I was afraid that people were getting angry with difficult puzzles and so I was very happy that I hadn’t changed this puzzle. By the time the teams started submitting answers to it, people were exhausted. Manic Sages increased the speed with which options to buy answers to puzzles were released. I was ecstatic that this puzzle was one of the few puzzles in the last round that was solved, not bought with options. Here is the puzzle:

• While everyone was discussing which color to paint the room, the counselor was dreaming about a real chocolate sundae. A walk-in walked into the reception in honor of a regular phenomenon visible every four hours or so. The client just wanted to find his dog in order to provide a permanent shortcut to another part of space; instead, he found something else.The Federation didn’t want to buy a lemon, so their lawyer used a spider to type the password. They discovered that the creatures glow in the dark and the perceptive negotiator won the bid. While they were waiting for the results of the shuttle trip, they turned the lights off to hunt them. The bird-like sounds were coming from under the floor. They used alcohol to save the woman’s life, which was a big mistake. She refused to be his conscience, instead she used her new untapped power of light to save the world; she already had a job as a counselor.
• Their daughter disappeared two months ago, whereas they needed to keep the wounded survivor steady. The African activist was kidnapped by rebels when she was a teenager. While some people were building a boat on the beach, she escaped from her kidnappers. He said that the reward had been withdrawn to eliminate the financial incentive to lie. They needed to perform a blood transfusion, but they didn’t have the proper instruments. By his false statement, he removed over-claimers: people lying to get attention. He needed to write vows. They read surprise at the unexpected labor in the woods in the boy’s face. It was clear that the boy had never looked into the backpack.She described horrors she had seen: rape, torture, massacres carried out by child soldiers, the doctor losing his own blood to help the wounded survivor. There was no deception leakage, but she seemed anxious, so the doctor couldn’t go and deliver the baby. They needed to find the other girl before noon, and the crushed leg made blood transfusion impractical. His vows were self-referential. He talked about how he couldn’t write the vows. While the doctor played 20 questions one man died and another was born. The girl wasn’t answering, but the doctor read her micro-expressions. The writer touched her ear and exposed her lies. At the end the doctor suspected murder, and the book was withdrawn.
• She took pictures in an abandoned house and jumped off the roof. Two girls came back to investigate. He was surprised by a basket of cookies and a statue that was in the wrong place. A new drug hit the streets making people see things, like old pictures of a woman who looked exactly like her friend. He started seeing his dead father: when people die in the past, they produce energy in the present.They were the two most powerful people on the planet. For wedding preparations she got a list of 17 DVDs. His partner started hallucinating about her ex. People do not understand time. Naomi’s ability caused all this mess: the box left them behind. The only place where she didn’t use gloves was her garden. The dinner guests tried her chicken, and, as a consequence, they were stuck looking at each other forever. The drugged cookies were a gift to help resolve their issues. Because of that, she gave him the shorthand transcripts to complete the cycle.
• Did she fall asleep while they were discussing the dead boy’s name? The price tag was exorbitant for a witness to identify the defendant. The woman would be everything he wanted and needed. She was a security guard chewing gum. The witness changed her testimony: they went to the woods and were water-rafting, rock-climbing, and arrow-shooting. As she was not the first girl he brought to the woods, the jury gave a verdict of “Not Guilty.”The detective was in court, though it wasn’t his case. She needed to stop talking and start running. Shit always rolls downhill. Poisoned water made her see things she was not supposed to remember like a shitty orange couch outside. In spite of the background check the client was a psychopath who was moved from uptown to the fucking low-rises. Shoulder to the wheel. Dead witness, mother-fucker.
• A little girl was humming about the dark side. The Wicca group was boring, and the new invention was making whooshing sounds. While a laryngitis epidemic took over the town, the noise-eater got turned on by accident.The princess’s scream would kill the monsters, while the monster machine killed its own remote control. She and her future boyfriend discovered each other’s secrets. The dark side is waiting.
• The experiment in the gay club was very important to him. He was a semi-cute boy-next-door type and his shuttle trip was supposed to be easy. There is more to a guy than cock size, and he was being pulled. He was injected with something and started to understand everyone. They were a bald priestess and a warrior with a very nice butt. They offered you a discount if you bought the butt and the bulge together.They were approaching a commerce planet in Pennsylvania. They escaped and were standing on the roof of a hospital. She was sending a transmission, while the older man was running his tongue along the young man’s spine. The girl tried to protect him, believing his story, but was arrested for contamination. Fuck. He had a baby, two babies. He distracted the guards with a puzzle ring. And while they were painting his black car with a pink derogatory word, they escaped.
• He was drinking before operating on his fiancée. What kind of a father kills people? Tonight was the night he would finally sleep, and drinking was the only way for him to stop his hands from shaking. The limo driver kidnapped him while she watched herself die in the mirror. While being sleep-deprived he conducted a test. Nothing was wrong, except he brought the wrong documents to court. The criminal walked, but, unexpectedly, he couldn’t feel his leg and couldn’t walk anymore. There was a lot of blood and the body was not filtering iodine. He took a picture of the actor falling into a coma with his blood-spatter camera.His girlfriend wanted to buy a firm mattress to have sex. He preferred to sleep on a water-bed and told the secret of his bloody hobby to his baby. It was not an infection, it was an allergy, so he changed his plan of where to grab the victim. The case was solved because of the bubbles in the glass. He was killing for his son now. The patient was indeed allergic and crashed his car.
• The woman died two weeks ago, but her car accident was yesterday. There was so much blood and, for some reason, ice. Jane Doe wasn’t the girl’s sister. Melting speed and surface tension could help the calculation. They came to pay their respects but the celebration was postponed. They brought personal effects to drop off. If the couple’s daughter was like their mother, then they themselves were like their grandparents. The idea to ask the grandmother resulted in a kiss.Their planet had been on the verge of a golden age, then everything fell apart. She brought some clothes, a toothbrush, shampoo and some other things to the detention center. “Don’t let the history repeat itself,” the worshiper of the second in command said. She didn’t know what the red string was for. The teen’s sister told him stories about another galaxy, and the war and the algorithm that might find the dead man’s favorite coffee place and, consequently, solve the case. The kidney operation was in a hotel. They didn’t expect to see the body, but there it was. She touched the body to reveal emptiness inside. At the end they gathered in his house for dinner as usual. He had to save Courtney’s future body before everything blew up and put the red sticker on his license.
• After retirement, he came back to an unsolved murder case; he remembered a kiss in flashbacks. He drove to the lake where the accidental drowning happened. He lured everyone involved to the lake, and, after having sex, he told her that he wanted a real marriage. They wanted their child to be born on the new planet. The doctor was one of the suspects. The couple was already in the cabin, and he doubted that he was the one who she really wanted.The young man was murdered, and everyone thought that the detective was the real target. The man went to look for sneakers during the boxing match. The nosy lady-writer dropped names to persuade the sheriff to look into the cabin. The admiral challenged the chief to join him in the ring. They didn’t find the sneakers, and they shouted this to the skies. The lady solved the murder, as usual, while the boxing match became too personal and people started leaving.

The second “instructioned” puzzle is Portals by Palmer Mebane. It is an insanely beautiful and difficult logic puzzle that consists of known puzzle types interconnected to each other through portals. Here Palmer Mebane explains how portals work:

“Each of the ten puzzles corresponds to a color, seen above the grid where the name of the puzzle is written. The grid contains nine square areas, one each of the other nine colors. These are portals that connect the puzzle to one of the other nine, as denoted by the portal color. Each puzzle’s rules define which squares of their solution are “black”. On the portal squares, the two puzzles must agree on which squares are black and which are not. For instance, if in the red grid the top left square of the blue portal is black, then in the blue grid the top left square of the red portal must also be black, and vice versa.”

On the Portals puzzle page you can find the rules for how each individual game is played and how to shade areas. The puzzle requires a lot of attention. It took us a long time to test-solve it. If you make a mistake in one grid it will propagate and will lead to a contradiction in another grid, so it is difficult to correct mistakes. If you do make a mistake, you are not alone: we kept making mistakes during our test-solve. Because of the difficulty of tracing back to the source of the error, we just started anew, but this time making sure that every step was confirmed by two people. Working together in this way, we were able to finish it.

If you do not care about the extraction and the answer, ignore the letter grid in the middle and enjoy the logic of it.

There were a couple of puzzles during the MIT Mystery Hunt that were not so mysterious. Unlike in traditional hunt puzzles, these puzzles were accompanied by instructions. As a result you can dive in and just enjoy solving the logic part of the puzzle without bothering about the final phase, called the extraction, where you need to produce the answer.

The first puzzle with instructions is Random Walk by Jeremy Sawicki. I greatly enjoyed solving it. In each maze, the goal is to find a path from start to finish, moving horizontally and vertically from one square to the next. The numbers indicate how many squares in each row and column the path passes through. There are nine mazes in the puzzle of increasing difficulty. I am copying here two such mazes: the easiest and the toughest. The colored polyomino shapes are needed for the extraction, so you can ignore them here.

Today I have a special treat for you. Here is the first of several puzzles that I plan to present from the 150 that we used in the MIT Mystery Hunt 2013. Keep in mind that although the puzzles have authors, they were the result of a collaboration of all the team members. In many instances editors, test-solvers and fact-checkers suggested good ways to improve the puzzles.

I wrote the puzzle Open Secrets jointly with Rob Speer. The puzzle was in the opening round, which means it is not too difficult. By agreement the answers to the puzzles are words or phrases. I invite my readers to try this puzzle. I will post the explanation in about two weeks.

I dropped my blog for two months. Some of my readers got worried and wrote to ask if I was okay. Thanks for your concern.

I am okay. I was consumed by the MIT Mystery Hunt. My team, Manic Sages, won the hunt a year ago, and as a punishment — oops, I meant as a reward — we got to write the 2013 hunt, instead of competing in it. I myself ended up writing about ten problems for the hunt. This was in addition to test-solving about 150 problems my whole team prepared for the hunt.

I could only think about the hunt. My mind was full of ideas for the hunt so I was afraid to write in my blog about something that I might later want to use for my problems. Or even worse, I was nervous that my blog posts might be unconsciously revealing hunt secrets. Moreover, I didn’t want to advertise the fact that I was working on the hunt, thereby drawing people to my blog to scrutinize my interests as they prepared for the hunt.

So I just disappeared.

I apologize; please forgive me.

The father of my son has four children. My son is my only child. How many children do we have in total together?

“I will win the next International Chopin Piano Competition.”

No matter how good I am at positive affirmations, that won’t work: I do not play piano.

I tried to read books on positive thinking, but they made me mistrust the genre. The idea that you can achieve anything by positive thinking makes no sense. For example:

• I can’t win a competition by thinking that I will win. Indeed, everyone can think positively that they are winners, but only one person actually wins.
• I can’t replace work with positive thinking. I will not improve at playing the piano until I take lessons and practice.
• I can’t create the impossible. I can’t turn my eyes blue, no matter how hard I think.

Positive thinking might actually be harmful. I can invest tons of time into trying to change my natural eye color by using my thoughts, when instead I could just use my money and buy some colored contact lenses. Or, if I think myself rich, I might start spending more money than I have and end up bankrupt.

However, perhaps I should not have totally dismissed the idea of positive thinking. While it does have logical inconsistencies, such as those in my examples above, maybe there are ways in which positive thinking is helpful.

First, we should treat these beliefs not as a guarantee, but probabilistically. For example, if you think that you can win the piano competition, the judges will feel your confidence, and may give you slightly better marks.

Second, positive thinking can work, if we choose our affirmations correctly. I recently discovered that I am deceiving myself into believing that I am hungry when I’m not. I should be able to reverse that. I should be able to persuade myself that I am not hungry when I am.

I decided to start small. I tried to persuade myself that tiramisu doesn’t really taste good. Once that seemed to be working, I got more serious. I bought a couple of CDs with affirmations for weight loss.

Unfortunately, they want me to lie down and relax. I do not have time to lie down. I could listen when I am driving or when I am cleaning my kitchen. Hey, does anyone know some good weight-loss affirmations CDs that do not require relaxation?

One of the 2012 PRIMES projects, suggested by Professor Jacob Fox, was about bounds on the number of halving lines. I worked on this project with Dai Yang.

Suppose there are n points in a general position on a plane, where n is an even number. A line through two given points is called a halving line if it divides the rest of n−2 points in half. The big question is to estimate the maximum number of halving lines.

Let us first resolve the small question: estimating the minimum number of halving lines. Let’s take one point from the set and start rotating a line through it. By a continuity argument you can immediately see that there should be a halving line through any point. Hence, the number of halving lines is at least n/2. If the point is on the convex hull of the set of points, then it is easy to see that it has exactly one halving line through it. Consequently, if the points are the vertices of a convex n-gon, then there are exactly n/2 halving lines. Thus, the minimum number of halving lines is n/2.

Finding the maximum number of halving lines is much more difficult. Previous works estimated the upper bound by O(n^4/3) and the lower bound by O(ne^{√log n}). I think that Professor Fox was attracted to this project because the bounds are very far from each other, and some recent progress was made by elementary methods.

Improving a long-standing bound is not a good starting point for a high school project. So after looking at the project we decided to change it in order to produce a simpler task. We decided to study the underlying graph of the configuration of points.

Suppose there is a configuration of n points on a plane, and we are interested in its halving lines. We associate a graph to this set of points. A vertex in the configuration corresponds to a vertex in the graph. The graph vertices are connected, if the corresponding vertices in the set have a halving line passing through them. So we decided to answer as many questions about the underlying graph as possible.

For example, how long can the longest path in the underlying graph be? As I mentioned, the points on the convex hull have exactly one halving line through them. Hence, we have at least three points of degree 1, making it impossible for a path to have length n. The picture below shows a configuration of eight points with a path of length seven. We generalized this construction to prove that there exists a configuration with a path of length n−1 for any n.

We also proved that:

• The largest cycle can have length n − 3.
• The largest clique is of the order O(√n).
• The degrees of two distinct vertices sum to at most n, if they are connected by an edge, and at most n − 2 otherwise.

After we proved all these theorems, we came back to the upper bound and improved it by a constant factor. Our paper is available at arXiv:1210.4959.