Tanya Khovanova's Math Blog


This blog has a modern version at http://blog.tanyakhovanova.com/, where you can leave comments. This page contains the copies of blog entries.


Content

If you enjoy this page you can support it by shopping at amazon through this link. Thank you.


A Problem from the Moscow Olympiad

Here is a problem from the 2012 Moscow Olympiad:

There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.

My question is: Why 4? I can answer that myself. If in a group of four people any two people share exactly two common acquaintances, then all four people know each other. So in this Olympiad problem, the author wanted students to invent a more intricate example.

Let's take this up a notch and work on a more difficult problem.

There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.

Happy Nobel Prize Winners

I stumbled upon an article, Winners Live Longer, that says:

"When 524 nominees for the Nobel Prize were examined and compared to the actual winners from 1901 to 1950, the winners lived longer by 1.4 years. Why? It seems just having won and knowing you are on top gives you a boost of 1.8% to your life expectancy."

This goes on top of the pile of Bad Conclusions From Statistics. With any kind of awards where people can be nominated several times, winners on average would live longer. The reason is that nominees who die early lose their chance to be nominated again and to win.

I wonder what would happen if we were to compare Fields medal nominees and winners. There is a cut off age of 40 for receiving a Fields medal. If we compare the life span of Fields medal winners and nominees who survived past 40, we might get a better picture of how winning affects life expectancy.

Living a long life increases your chances of getting a Nobel Prize, but doesn't help you get a Fields medal.


Four Papers in Three Weeks

I wish I could write four papers in three weeks. The title just means that I submitted four papers to the arXiv in the last three weeks—somehow, after the stress of doing my taxes ended, four of my papers converged to their final state very fast. Here are the papers with their abstracts:


Integers and Sequences Solution

This is the promised solution to the puzzle Integers and Sequences that I posted earlier. The puzzle is attached below.

Today I do not want to discuss the underlying math; I just want to discuss the puzzle structure. I'll assume that you solved all the individual clues and got the following lists of numbers.

Since the title mentions sequences, it is a good idea to plug the numbers into the Online Encyclopedia of Integer Sequences. Here is what you will get:

Your first "aha moment" happens when you notice that the sequences are in alphabetical order and each has exactly one number missing. The alphabetical order is a good sign that you are on the right track; it can also narrow down the possible names of the sequences that you haven't yet identified. Alphabetical order means that you have to figure out the correct order for producing the answer.

Did you notice that some groups above are as long as nine integers and some are as short as four? In puzzles, there is nothing random, so the lengths of the groups should mean something. Your second "aha moment" will come when you realize that, together with the missing number, the number of the integers in each group is the same as the number of letters in the name of the sequence. This means you can get a letter by indexing the index of the missing number into the name of the sequence.

So each group of numbers provides a letter. Now we need to identify the remaining sequences and figure out in which order the groups will produce the word that is the answer.

Let's go back and try to identify the remaining sequences. We already know the number of letters in the name of each sequence, as well as the range within the alphabet. The third sequence might represent a challenge as its numbers are small and there might be many sequences that fit the pattern, but let's try. The results are below with the capitalized letter being the one that is needed for the answer.

What is going on? There are two sequences that fit the pattern of the third group and the sequence for the sixth group has many names, two of which fit the profile but produce different letters. Now we get to your third "aha moment": you have already seen some of the sequence names before, because they are in the puzzle. This will allow you to disambiguate the names.

Now that we have all the letters, we need the order. Sequences are mentioned inside the puzzle. You were forced to notice that because you needed the names for disambiguation. Maybe there is something else there. On closer examination, all but one of the sequence names are mentioned. Moreover, with one exception the clues for one sequence mention exactly one other sequence. Once you connect the dots, you'll have your last "aha moment:" the way the sequences are mentioned can provide the order. The first letter G will be from the pentagonal sequence, which was not mentioned. The clues for the pentagonal sequence mention the primeval sequence, which will give the second letter R, and so on.

The answer is GRANTER.

Many old-timers criticized the 2013 MIT Mystery Hunt. They are convinced that a puzzle shouldn't have more than one "aha moment." I like my "aha moments."

*****

*****

*****

*****

*****

*****

*****


My Yellow Road to Healthy Weight

Should I eat this piece of cake or not? I will certainly enjoy it very much. What harm will it do? Will this piece increase my weight? Maybe not. The next piece might, but this particular one looks harmless. Even if my weight increases by half a pound, it could be muscle weight. Yes, it probably would be due to muscle weight: I just went out of my house to throw away my garbage and this has to count as exercise.

Do you see the problem? Eating the cake provides an immediate reward, but the punishment is vague and in the far distant future. That is why I got excited when my son Alexey sent me the link to Beeminder, a company that creates an artificial non-vague and not far-in-the-future punishment for eating that piece of cake.

Here is how it works. You give them your target number — in my case my desired weight, but it could be any measurable goal — and the date by which you want to hit it. They draw a yellow path on a weight chart. You must weigh yourself every day. Whenever your weight is above your path, you have to pay real money to the company. Five dollars!

This is a great idea. Suddenly that piece of cake looks threatening. The only problem with using their system is that I have no clue how to lose weight. The company doesn't provide tools to lose weight: it just provides a commitment device. So it is difficult to stick with the weight-loss commitment without having a proven weight-loss plan.

The truth is that my son sent me the link, I laughed, and forgot about it. Besides, if I ever want to pay money for failing in my commitments, I would rather choose the beneficiary myself. Then I realized that I can use the yellow-road idea to try to lose weight while figuring out what works for me. I call my new plan the Adaptive Diet.

Starting from my actual weight on Day One, I drew a line that represents my target weight, assuming a daily decrease of 0.1 pounds. A deviation of one pound from my target weight on my daily weigh-in is what I call my Yellow Zone. When I am in the Yellow, I continue doing what I was doing before: trying to build new, healthier habits.

If I am more than one pound below my target weight, then I have entered what I call the Green Zone. When I am in the Green, I can allow myself to indulge my cravings. However, when I am one pound above my target weight, I call that the dreaded Red Zone. This Zone has different shades of red. If I am between 1 and 2 pounds above my target weight, I have to eat only apples after 8:00pm. If I am 2 to 3 pounds above my target weight, only-apples time starts at 6:00pm. And so on. Every extra pound above my target weight moves the cut-off time by two hours. That means that if I am 7 pounds above my target weight, I would have to eat apples all day long.

The system has to work: I do not like apples.


Skyscrapers

Tanya Khovanova and Joel Brewster Lewis

In skyscraper puzzles you have to put an integer from 1 to n in each cell of a square grid. Integers represent heights of buildings. Every row and column needs to be filled with buildings of different heights and the numbers outside the grid indicate how many buildings you can see from this direction. For example, in the sequence 213645 you can see 3 buildings from the left (2,3,6) and 2 from the right (5,6).

In mathematical terminology we are asked to build a Latin square such that each row is a permutation of length n with a given number of left-to-right and right-to-left-maxima. The following 7 by 7 puzzle is from the Eighth World Puzzle Championship.

Skyscraper Puzzle

Latin squares are notoriously complicated and difficult to understand, so instead of asking about the entire puzzle we discuss the mathematics of a single row. What can you say about a row if you ignore all other info? First of all, let us tell you that the numbers outside have to be between 1 and n. The sum of the left and the right numbers needs to be between 3 and n+1. We leave the proof as an exercise.

Let's continue with the simplest case. Suppose the two numbers are n and 1. In this case, the row is completely defined. There is only one possibility: the buildings should be arranged in the increasing order from the side where we see all of them.

Now we come to the question we are interested in. Given the two outside numbers, how many permutations of the buildings are possible? Suppose the grid size is n and the outside numbers are a and b. Let's denote the total number of permutations by fn(a, b). We will assume that a is on the left and b is on the right.

In a previous example, we showed that fn(n, 1) = 1. And of course we have fn(a, b) = fn(b, a).

Let's discuss a couple of other examples.

First we want to discuss the case when the sum of the border numbers is the smallest — 3. In this case, fn(1, 2) is (n−2)!. Indeed, we need to put the tallest building on the left and the second tallest on the right. After that we can permute the leftover buildings anyway we want.

Secondly we want to discuss the case when the sum of the border numbers is the largest — n+1. In this case fn(a,n+1-a) is (n-1) choose (a-1). Indeed, the position of the tallest building is uniquely defined — it has to take the a-th spot from the left. After that we can pick a set of a-1 buildings that go to the left from the tallest building and the position is uniquely defined by this set.

Before going further let us see what happens if only one of the maxima is given. Let us denote by gn(a) the number of permutations of n buildings so that you can see a buildings from the left. If we put the shortest building on the left then the leftover buildings need to be arrange so that you can see a-1 of them. If the shortest building is not on the left, then it can be in any of the n-1 places and we still need to rearrange the leftover buildings so that we can see a of them. We just proved that the function gn(a) satisfies the recurrence:

Skyscraper Formula 1

Actually gn(a) is a well-known function. The numbers gn(a) are called unsigned Stirling numbers of the first kind (see http://oeis.org/A132393); not only do they count permutations with a given number of left-to-right (or right-to-left) maxima, but they also count permutations with a given number of cycles, and they appear as the coefficients in the product (x + 1)(x + 2)(x + 3)...(x + n), among other places. (Another pair of exercises.)

We are now equipped to calculate fn(1, b). The tallest building must be on the left, and the rest could be arranged so that, in addition to the tallest building, b-1 more buildings are seen from the right. That is fn(1, b) = gn-1(b-1).

Here is the table of non-zero values of fn(1, b).

b=2b=3b=4b=5b=6b=7
n=21
n=311
n=4231
n=561161
n=6245035101
n=712027422585151

Now we have everything we need to consider the general case. In any permutation of length n, the left-to-right maxima consist of n and all left-to-right maxima that lie to its left; similarly, the right-to-left maxima consist of n and all the right-to-left maxima to its right. We can take any permutation counted by fn(a, b) and split it into two parts: if the value n is in position k + 1 for some 0 ≤ k ≤ n-1, the first k values form a permutation with a - 1 left-to-right maxima and the last n - k - 1 values form a permutation with b - 1 right-to-left maxima, and there are no other restrictions. Thus:

Skyscraper Formula 2

Let's have a table for f7(a,b), of which we already calculated the first row:

b=1b=2b=3b=4b=5b=6b=7
a=1012027422585151
a=21205486753407560
a=32746755101501500
a=422534015020000
a=58575150000
a=615600000
a=71000000

We see that the first two rows of the puzzle above correspond to the worst case. If we ignore all other constrains there are 675 ways to fill in each of the first two rows. By the way, the sequence of the number of ways to fill in the most difficult row for n from 1 to 10 is: 1, 1, 2, 6, 22, 105, 675, 4872, 40614, 403704. The maximizing pairs (a,b) are (1, 1), (1, 2), (2, 2), (2, 2), (2, 2), (2, 3), (2, 3), (2, 3), (3, 3).

The actual skyscraper puzzles are designed so that they have a unique solution. It is the interplay between rows and columns that allows to reduce the number of overall solutions to one.


Vampires versus Mathematicians

I just compared two searches on Google Trends:

Vampires versus Mathematicians

Integers and Sequences

The most personal puzzle that I wrote for the 2013 MIT Mystery Hunt was Integers and Sequences based on my Number Gossip database. I named it after the first lecture that I prepared after I decided to return to mathematics. It is still my most popular lecture.

Many of the clues in this puzzle are standard math problems that are very good for math competition training. Other clues are related to sequences and integer properties.

You might wonder why I often ask for the second largest integer with some property. Isn't the largest one more interesting than the second largest? I do think that the largest number is more interesting, but exactly for this reason the largest number is available on my Number Gossip website and therefore is googleable. For example, my Number Gossip properties for 3000 contain the fact that 3000 is the largest palindrome in Roman numerals. This is why in the puzzle I used a slightly different clue, i.e. "the second largest three-letter palindrome in Roman numerals."

It took me many hours to find non-googleable variations of interesting properties for this puzzle. Unfortunately, its non-googleability evaporated as soon as my solution was posted, right after the hunt. In any case some clues in this puzzle are useful for math competition training, and I plan to use them myself in my classes. The puzzle is attached below. I will post the solution in a couple of weeks.

*****

*****

*****

*****

*****

*****

*****


Weighing Coins during the Mystery Hunt

The ultimate goal of each MIT Mystery Hunt is to find a hidden coin. So it was highly appropriate that our 2013 team created a coin-weighing puzzle (written by Ben Buchwald, Darby Kimball, and Glenn Willen) as a final obstacle to finding the winning coin:

There are nine coins, one real and eight fake. Four of the fake coins weigh the same and are lighter than the real coin. The other four fake coins weigh the same and are heavier than the real coin. Find the real coin in seven weighings on the balance scale.

Actually, it is possible to find the real coin in six weighings. Can you do that?


My Weight

My weight used to be my most guarded secret. In general, I am a very open person: I'll tell anyone anything about me, unless it involves other people. However, there were two exceptions, both of them numbers, interestingly enough: my age and my weight. The closest I came to revealing my weight was with my sister, because we often discuss our similar health issues. Unfortunately, she knows my age, so the only missing number is my weight. I am so tired of my struggle to lose weight, that I've stopped caring about keeping the number secret. I am ready to tell it to the whole world.

Let me start from the beginning. I grew up in a country and at a time when men liked plump women. I was never thin, and didn't have to worry about my weight like my thin girlfriends did. I'll never forget my high school boyfriend telling me, "Ninety percent of men like fat women, and the other ten percent like very fat women." When in college I weighed 70 kilograms (154 pounds) and I felt fine. I had my first child when I was 23. I gained 20 kilos while I was breastfeeding, reaching 90 kilos (200 pounds). My husband Andrey kept telling me that he liked Rubenesque women. I wasn't even slightly concerned about my weight. When we divorced in 1988, I felt that my world was crushed and I didn't want to go on living. As a result, I lost about 20 pounds.

By 1990 I recovered from my depression, married my next husband, and moved to the US to live with him. The US made me aware of my weight immediately. It didn't help that Andrey remarried a woman who was the opposite of Rubenesque. From this point on, I wanted to lose weight. After my second child was born, I gained 20 kilograms while breastfeeding, just as I had done with the first child. The result was that I weighed about 220 pounds, much more than I wanted.

I started to look around at what capitalist society had to offer. The pharmacy had many products. I tried Slim Fast, which started to kill my appetite immediately. However, I began to get depressed. The depression felt foreign. As a new mother, I had been very happy before using Slim Fast, and there had been no changes in my life other than consuming Slim Fast. I stopped using it and the depression disappeared. To make sure, I did an experiment. I started using Slim Fast again and the depression reappeared within three days. I stopped it and my depression disappeared. I was so desperate to lose weight that I repeated the experiment. But the result was the same. I stopped using it, and never used any slimming supplement since then. But within that whole process, I lost some weight.

I stayed slightly over 200 pounds for several years. The third time (after the divorce and the Slim Fast) that I lost a lot of weight was when I had my heart broken about 15 years ago. Since then I've been slowly gaining weight.

As you can see from my story, I was never able to lose weight when I wanted to. I lost it three times, but I can't and don't want to reproduce those circumstances. I actually do not know how to lose weight. For the past ten years I've been making changes in my eating habits that I hope, cumulatively, would help me lose weight. I do not buy soda or pizza. I significantly cut my consumption of sweets and starches. I eat more fruits and vegetables. I eat half of what I used to eat in a restaurant. I am still gaining weight.

he only thing I haven't tried is to be hungry. I am afraid of being hungry. Also I am scared that if I decide on a plan which might result in my being hungry, I will not be able to stick to it. I don't want to discover that I don't have enough will power. I am scared to be a failure. I hope that by writing and publishing this I'll gain the courage to replace my half-measures with a more drastic plan.

Oh! I forgot to tell you: I weigh 245 pounds.


February Jokes

* * *

Grigori Perelman's theorem: There is no offer you can't refuse.

* * *

A conversation between two Russians:
— Run to the store and fetch a couple bottles of vodka.
— How much is a couple?
— Seven.

* * *

— Is it true that the Windows operating system was copied from a UFO computer that crashed in Roswell?
— All we know for sure is that the UFO that didn't crash had a different operating system.

* * *

I saw our system administrator's shopping list. The first line was tomatoes.zip for ketchup.


Solving In the Details

I posted the puzzle In the Details two weeks ago. This is the most talked-about puzzle of the 2013 MIT Mystery Hunt. The author Derek Kisman invented this new type of puzzle and it is now called a Fractal Word Search. I anticipate that people will start inventing more puzzles of this type.

Let's discuss the solution. The words in the given list are very non-random: they are related to fractals. How do fractals work in this puzzle? The grid shows many repeating two-by-two blocks. There are exactly 26 different blocks. This suggests that we can replace them by letters and get a grid that is smaller, for it contains one-fourth of the number of letters. How do we choose which letters represent which blocks? We expect to see LEVEL ONE in the first row as well as many other words from the list. This consideration should guide us into the matching between letters and the two-by-two blocks.

The level one grid contains 18 more words from the list. But where are the remaining words? So we have level one, and the initial grid is level two. The substitution rule allows us to replace letters by blocks and move from level one to level two. When we do this again, replacing letters in level two by blocks, we get the level three grid. From there we can continue on to further levels. There are three words from the list on level three and one word on level four. But this is quickly getting out of hand as the size of the grid grows.

Let's step back and think about the next step in the puzzle. Usually in word search puzzles, after you cross out the letters in all the words you find, the remaining letters spell out a message. What would be the analogous procedure in the new setting of the fractal word search? In which of our grids should we cross out letters? I vote for grid number one. First, it is number one, and, second, we can assume that the author is not cruel and put the message into the simplest grid. We can cross-out the letters from words that we find in level one grid. But we also find words in other levels. Which letters in the level one grid should we cross out for the words that we find in other levels? There is a natural way to do this: each letter in a grid came from a letter in the previous level. So we can trace any letter on any level to its parent letter in the level one grid.

We didn't find all the words on the list, but the missing words are buried deep in the fractal and each can have at most three parent letters. I leave to the reader to explain why this is so. Because there are so few extra letters, it is possible to figure out the secret message. This is what my son Sergei and his team Death from Above did. They uncovered the message before finding all the words. The message says: "SUM EACH WORD'S LEVEL. X MARKS SPOT." Oh no! We do need to know each word's level. Or do we? At this point, the extra letters provide locations of the missing words. In addition, if a word on a deep level has three parents, then it has to be a diagonal word passing through a corner of one of the child's squares. So our knowledge of extra letters can help us locate the missing words faster.

Also, the message says that the answer to this puzzle will be on some level in the part of the grid that is a child of X. Luckily, but not surprisingly, there is only one letter X on level one. The child of X might be huge. But we could start looking in the center. Plus, we know from the number of blanks at the end of the puzzle, that the answer is a word of length 8. So Sergei and his team started looking for missing words and the answer in parallel. Then Sergei realized that the answer might be in the shape of X, so they started looking at different levels and found the answer before finding the last word on the list. The answer was hiding in the X shape in the center of the child of X on level 167: HUMPHREY.

H..Y
.UE.
.RM.
H..P

Cambridge Waldo

Cambridge Waldo puzzle from the 2013 MIT Mystery Hunt was supposed to be easy. Its goal was to get people out of the building for some fresh air. I made this puzzle jointly with Ben Buchwald, Adam (Pesto) Hesterberg, Yuri Lin, Eric Mannes and Casey McNamara. The puzzle consists of 50 pictures of different locations in Cambridge; one of the above individuals was hiding in each picture. Let me use this opportunity to thank my friends for starring in my puzzle and being inventive while doing it.

The puzzle starts with a group picture of my stars. The caption to the picture gives their names. The fact that they are standing in alphabetical order is a clue.

Out of the 50 pictures, each person appears in exactly ten pictures. If you mark the locations of one person on a map, they look like a letter. For example, below are Ben's locations that form a letter "S". When you put the letters in the alphabetical order by people names you get the answer to the puzzle: SCAMP.

Ben's Locations

As you can see, you do not need all ten locations to recognize the letter. You might be able to recognize the letter with five locations, or at least significantly reduce possibilities for the letter. Besides, you do not need all the letters to recognize the answer. We thought that this was an easy puzzle.

And, to make it even easier, the order in which we posted the pictures was not completely random. The pictures of one person were in the order one might walk from one location to another. This played two important roles. If you recognize the person but do not recognize the location on the picture, you can make an approximate estimation of the location because it must be on the path between the previous and next locations. If you recognize the location but not the person, you can guess the person by checking whose path it fits better.

It was difficult to hide people, especially when there were no other people around. So we sometimes used props. We only used one prop per person. Here you can see Pesto with his sarongs in plain view. In the other picture (below) he is hiding under a white sarong. Yuri had a bicycle helmet. In one of the pictures, she hid so well that you couldn't see her — but you could see her helmet. Ben had a bear hat. In one of the pictures you can only see a shadow of a person, but this person was clearly wearing a hat with bear ears. Eric didn't have a prop, but my car was eager to make a cameo appearance at the Mystery Hunt, so I hid him in my car in one of the pictures.

Pesto with sarongs
Pesto under a white sarong

As you might guess I made the pictures of different people at different times. So Ben Buchwald was the one who realized that solvers might differentiate people by looking at the data of the picture files. He carefully removed the original time stamps.

Despite our best intentions, our test-solvers decided not to leave their comfy chairs, but rather to use Google-StreetView. We strategically made some of the pictures not Google-StreetViewable, but our test-solvers still didn't leave the comfort of their chairs. They just became more inventive. I do not know all the things they did to solve the puzzle, but I heard about the following methods:

I have yet to understand why this puzzle was difficult for the Mystery Hunt teams.


Open Secrets Revealed

Here is the solution to the Open Secrets puzzle I published recently. Through my discussion of this solution, you'll also get some insight into how MIT Mystery Hunt puzzles are constructed in general.

I've included the puzzle (below) so that you can follow the solution. The puzzle looks like a bunch of different cipher texts. Even before we started constructing this puzzle, I could easily recognize the second, the seventh, and the last ciphers. The second is the cipher used by Edgar Allan Poe in his story, The Gold-Bug. The seventh cipher is a famous pigpen (Masonic) cipher, and the last is the dancing men cipher from a Sherlock Holmes story. Luckily you do not need to know all the ciphers to solve the puzzle. You can proceed with the ciphers you do know. With some googling and substitution you will translate these three pieces of text into: COLFERR, OAOSIS OF LIFEWATER, and RBOYAL ARCH.

These look like misspelled phrases, each of which has an extra letter. However, there are no typos in good puzzles. Or, more precisely, "typos" are important and often lead to the answer. So now I will retype the deciphered texts with the extra letter in bold: COLFERR, OAOSIS OF LIFEWATER and RBOYAL ARCH. In the first word it is not clear which R should be bold, but we will come back to that later.

At this point you should google the results. You may notice that the "royal arch" leads you to the Masons, who invented the pigpen cipher. From this, you can infer the structure of the ciphers and the connections among them. Indeed, a translation of one cipher refers to another. So you should proceed in trying to figure out what the texts you have already deciphered refer to. Eoin Colfer is the author of the Artemis Fowl series that contains a Gnomish cipher, and Oasis of Lifewater will lead you to Commander Keen video games with their own cipher. When you finish translating all of the ciphers, you get the following list:

The bold letters do not give you any meaningful words. So there is more to this puzzle and you need to keep looking. You will notice that the translations are in alphabetical order. This is a sign of a good puzzle where nothing is random. The alphabetical order means that you need to figure out the meaningful order.

To start, the phrases reference each other, so there is a cyclic order of reference. More importantly, the authors of the puzzle added an extra letter to each phrase. They could have put this letter anywhere in the phrase. As there is nothing random, and the placements are not the same, the index of the bold letter should provide information. If you look closely, you'll see that the bold letters are almost all in different places. If we choose the second R in COLFERR as an extra R, then the bold letter in each text is in a different place. Try to order the phrases so that the bold letters are on the diagonal. You'll see that this order coincides with the reference order, which gives you an extra confirmation that you are on the right track. So, let's order:

Now the extra letters read BOKLORYFH. This is not yet meaningful, but what is this puzzle about? It is about famous substitution ciphers. The first and most famous substitution cipher is the Caesar cipher. So it is a good idea to use the Caesar cipher on the phrase BOKLORYFH. There is another hint in the puzzle that suggests using the Caesar cipher. Namely, there are many ways to clue the dancing men code. It could be Conan Doyle, Sherlock Holmes, and so on. For some reason the authors chose to use the word ELEMENTARY as a hint. Although this is a valid hint, you can't help but wonder why the authors of the puzzle are not consistent with the hints. Again, there is nothing random, and the fact that the clues are under-constrained means there might be a message here. Indeed, the first letters read ROMAN CODE, hinting again at the Caesar shift. So you have to do the shift to arrive at the answer to this puzzle, which is ERNO RUBIK.


Turnary Reasoning

The most difficult puzzle I wrote for the MIT Mystery Hunt 2013 was Turnary Reasoning. I can't take credit for the difficulty: I designed the checkers positions; they were expectedly the easiest. Timothy Chow created the chess positions, and Alan Deckelbaum created the MTG positions. As the name of the puzzle suggests, you need to find whose turn it is in each position or, as the flavor text suggests, decide that the position is impossible.

I tried to solve the chess positions myself and was charmed by their beauty. The most difficult one was the first chess puzzle presented below. Find whose turn it is or prove that the position is impossible.

Chess Position from Turnary Reasoning

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.


In the Details

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

BOUNDARY HENON LEVY DRAGON SCALING
BROWNIAN HILBERT LYAPUNOV SPACE
CAUCHY HURRICANE MANDELBROT STRANGE
CURLICUE ITERATE NEURON TAKAGI
DE RHAM JULIA NURNIE TECTONICS
DIMENSION LEIBNIZ POWER LAW T-SQUARE
ESCAPE LEVEL ONE RAUZY WIENER
HAUSDORFF LEVEL TWO RIVER YO DAWG

_ _ _ _ _ _ _ _

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:


Something 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:


Portals

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.


Random Walk

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.


Open Secrets

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.


Apologies

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.


Children's Riddle

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


Affirmations

"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:

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?


Halving Lines

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(n4/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.

Path

We also proved that:

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.


I am on the Air

Samuel Hansen has an unusual profession: he is a mathematics podcaster. He interviewed me for his Relatively Prime podcast titled 0,1,2,3,…, where we discussed my Number Gossip project. The podcast also includes interviews with Neil Sloane, Michael Shamos, and Alex Bellos.

My previous interview with Samuel is at acmescience.com. There I discuss both math education and gender in math issues.

When I listened to myself, I found it strange that I seemed to have a British accent on top of my Russian accent. Did you notice that too?


Helpmate

I discovered the following chess puzzle on a Russian blog for puzzle lovers. It is a helpmate-type puzzle. Black cooperates with White in checkmating himself. In this particular puzzle Black starts and helps White to win in one move.

Oops. Something is not quite right. There are not enough pieces on the board. To recover the missing pieces in order to solve the puzzle, you need to retrace your steps. If Black and White go back one move each, they will be able to cooperatively checkmate Black in one move. Find the position one move back and the cooperative checkmate.

Helpmate

Me and Chess

I am Russian; I know how to play chess. My father taught me when I was three or four. We played a lot and he would always win. I got frustrated with that and one day, when I was five, I didn't announce my check. On the next move, I grabbed his king and claimed my victory.

He was so angry that he turned red and almost hit me. This frightened me so much that I lost my drive for chess that very moment.

I still understand its beauty and solve a chess problem about once a decade. Look for a cute chess puzzle in my next post.


Challenge Problems

For my every class I try to prepare a challenge problem to stretch the minds of my students. Here is a problem I took from Adam A. Castello's website:

There is a ceiling a hundred feet above you that extends for- ever, and hanging from it side-by-side are two golden ropes, each a hundred feet long. You have a knife, and would like to steal as much of the golden ropes as you can. You are able to climb ropes, but not survive falls. How much golden rope can you get away with, and how? Assume you have as many hands as you like.

The next problem I heard from my son Sergei:

You are sitting at the equator and you have three planes. You would like to fly around the equator. Each plane is full of gas and each has enough gas to take you half way around. Planes can transfer gas between themselves mid-air. You have friends, so that you can fly more than one plane at once. How do you fly around the equator?

Nerdy and Flirtatious Jokes

* * *

Right clicking a file with a mouse will allow you to change it, check it for viruses, or revert to the previous version. I wonder where I can buy a mouse that can do the same thing with my husband.

* * *

— Let's have sex.
— Sure, but today I want to be the numerator.

* * *

Attention! We want to check that you are not a robot. Please, undress and turn on a web-camera.

* * *

In a drug store:
— I would like input and output cleaners.
— ???
— Toothpaste and toilet paper.

* * *

I used to recount the multiplication tables to delay my ejaculation. Now, each time I see the multiplication tables I get a hard on.

* * *

— Tonight my parents are away. Let's finally try a forbidden thing.
— Dividing by zero?

* * *

My friend put his mistress in his phone's contact list as 'low battery'.


2012!

In what base does 2012! have more trailing zeros: base 15 or 16?

Explain why the result shouldn't be too surprising.


Why I Eat

I would like to report on my weight loss progress. Last time I added two new habits, walking my toy dog every day, and drinking more water from the enticing cute bottles I bought.

I named my stuffed dog Liza and I walk with her every day. I didn't expect immediate weight loss due to this new regime, because my first goal was to get out of the house every day, even if only for two seconds. The next step will be to increase walking time to ten minutes.

Drinking a lot of water doesn't work well. I spend too much time looking for bathrooms and panicking that I will not make it. I like the idea of drinking a lot of water, but I am not sure I can hold to it, if you understand what I mean.

Since taking on this challenge, I've gained two habits, but I haven't lost a pound.

Now I'm upping my game. Below is my analysis of why I eat. When I eat, I believe that I am hungry. But looking at this more objectively I think this is not always the case: sometimes there are other reasons. I am listing these other reasons so I can fight them face-to-face. Here we go:

Hmm. That was painful to write. My psychoanalyst taught me that pain means I am on the right track.


Three out of Three

Davidson Institute for Talent Development announced their 2012 Winners. Out of 22 students, three were recognized for their math research. All three of them are ours: that is, they participated in our PRIMES and RSI programs:

I already wrote about Xiaoyu's project. Today I want to write about Sitan's project and what I do as the math coordinator for RSI.

RSI students meet with their mentors every day and I meet with students once a week. On the surface I just listen as they describe their projects. In reality, I do many different things. I cheer the students up when they are overwhelmed by the difficulty of their projects. I help them decide whether they need to switch projects. I correct their mistakes. Most projects involve computer help, so I teach them Mathematica. I teach them the intricacies of Latex and Beamer. I explain general mathematical ideas and how their projects are connected to other fields of mathematics. I never do their calculations for them, but sometimes I suggest general ideas. In short, I do whatever needs to be done to help them.

I had a lot of fun working with Sitan. His project was about the rank number of grid graphs. A vertex k-ranking is a labeling of the vertices of a graph with integers from 1 to k so that any path connecting two vertices with the same label passes through a vertex with a greater label. The rank number of a graph is the minimum possible k for which a k-ranking exists for that graph. When Sitan got the project, the ranking numbers were known for grid graphs of sizes 1 by n, 2 by n, and 3 by n. So Sitan started working on the ranking number of the 4 by n graph.

His project was moving unusually fast and my job was to push him to see the big picture. I taught him that the next step, once he finishes 4 by n graphs is not to do 5 by n graphs, as one might think. After the first step, the second step should be bigger. He should use his insight and understanding of 4 by n graphs to try to see what he can do for any grid graphs.

This is exactly what he did. After he finished the calculation of the rank number of the 4 by n graphs, he found a way to improve the known bounds for the ranking number of any grid graph. His paper is available at the arXiv.

I just looked at my notes for my work with Sitan. The last sentence: "Publishable results, a potential winner."


PRIMES-USA

PRIMES-USA: A new MIT program for talented math students from across the country.

I've been working as a math coordinator for RSI, the most competitive summer program for high school juniors. RSI arranges for these select students to do scientific research. I only work with kids who do math, and usually we have a dozen of them. Every student has an individual mentor, usually a graduate student, with whom they meet daily. I supervise all the projects and meet with each high school student about once a week. My job was described as "going for the biggest impact": when the project is in trouble, I jump in to sort it out; when the project is doing well, I push it to further limits.

RSI is a great program: kids enjoy it and we produce interesting research. My biggest concern is that the program is too short. The kids do math for five weeks and they usually approach a good result, but at the end of RSI we generally see just a hint of what they could truly achieve. Kids who continue to work on their own after the program ends are more successful. Unfortunately most of the students stop working at the end of the program just as they are approaching a big theorem.

I discussed this dissatisfying trend with Pavel Etingof and Slava Gerovitch and we decided to do something about it. Pavel and Slava conceived and found funding for a new program called PRIMES that is similar to RSI, but runs for a year. From February through May, PRIMES students meet with their mentors weekly. In fact, we require on the application that the students commit to coming to MIT once a week, thereby limiting us to local students. Theoretically, someone from Detroit with a private jet who can fly to MIT weekly would be welcomed.

Before the first year, we wondered whether the smaller pool of local students would be weaker than national and international RSI students. To our delight, that wasn't the case. In the first year we got fantastic students. One explanation is that PRIMES is much more flexible. We do not mind when our students go to IMO in the summer or to math camps or when they go away on vacation with their parents. As a result, we get students who would never apply to RSI because of their summer schedules. Our PRIMES students have won so many prizes that I do not remember them all. We post our successes on the website.

Our success in PRIMES suggests that there are likely many talented kids in other states who never even apply to RSI because of a scheduling conflict. This led us to try to adapt PRIMES to national needs. So we created a new program called PRIMES-USA that will accept students from across the country. We will work with them through Skype. These students must commit to travel to MIT for a PRIMES conference in May. Because this is our pilot program, we will only accept five students.


Number Gossip is Back

Thank you to everyone who helped me to find a host for my Number Gossip website. Some readers and friends even offered me free hosting on their servers. I decided to pay for hosting because I have many specific requirements and that might be a burden on my friends.

On the basis of my readers' recommendations, I chose Dreamhost as my new webhosting provider. I apologize for the interruption in the flow of the gossip. I know that many people use Number Gossip for birthday gift ideas. I can tell you that on my previous birthday, you could have congratulated me on becoming prime and evil.


A Visit to Smullyan

Raymond Smullyan 2012

I visited Raymond Smullyan on my way home from Penn State. We went for lunch at Selena's Diner. What do two mathematicians do during lunch? Exchange magic tricks and jokes, of course. Here is a story Raymond told me:

Raymond: What is the date?
Stranger: I do not know.
Raymond: But you have a newspaper in your pocket!
Stranger: It's no use. It's yesterday's.


A Measure of Central Symmetry

Consider central symmetry: squares and circles are centrally symmetric, while trapezoids and triangles are not. But if you have two trapezoids, which of them is more centrally symmetric? Can we assign a number to describe how symmetric a shape is?

Here is what I suggest. Given a shape A, find a centrally symmetric shape B of the largest area that fits inside. Then the measure of central symmetry is the ratio of volumes: B/A. For centrally symmetric figures the ratio is 1, and otherwise it is a positive number less than 1.

Five Discs

The measure of symmetry is positive. But how close to 0 can it be? The picture on the left is a shape that consists of five small disks located at the vertices of a regular pentagon. If the disks are small enough than the largest symmetric subshape consists of two disks. Thus the measure of symmetry for this shape is 2/5. If we replace a pentagon with a regular polygon with a large odd number of sides, we can get very close to 0.

Triangle's Symmetricity

What about convex figures? Kovner's theorem states that every convex shape of area 1 contains a centrally symmetric shape of area at least 2/3. It is equal to 2/3 only if the original shape is a triangle. That means every convex shape is at least 2/3 centrally symmetric. It also means that the triangle is the least centrally symmetric convex figure. By the way, a convex shape can have only one center of symmetry.

After I started writing this I discovered that there are many ways in which people define measures of symmetry. The one I have defined here is called Kovner-Besicovitch measure. The good news is that the triangle is the least symmetric planar convex shape with respect to all of these different measures.


Great Ideas that Haven't Worked. Yet.

I'm trying to lose weight. Many books explain that dieting doesn't work, that people need to make permanent changes in their lives. This is what I have been doing for several years: changing my habits towards a healthier lifestyle.

This isn't easy. I am a bad cook; I hate shopping; and I never have time. Those are strong limitations on developing new habits. But I've been a good girl and have made some real changes. Unfortunately, my aging metabolism is changing faster than I can adopt new habits. Despite my new and improved lifestyle, I am still gaining weight.

But I believe in my system. I believe that one day I will be over the tipping point and will start losing weight, and it will be permanent. Meanwhile I would like to share with you the great ideas that will work someday.