Tanya Khovanova's Math Blog

OnlineDegree.net selected the 50 Best Blogs for Math Majors, and I am pleased that Tanya Khovanova’s Math Blog is number two. Since they did not explain their criteria, I suspected that it might be according to the number of Google hits. To double check, I Googled “math blog” and once again my blog was number two.

This might be the right moment to acknowledge the others involved with my blog. First, Sue Katz, my writing teacher and editor, corrected the English in most of my posts. Now I do not “do” mistakes in English any more, I make them.

My sons, Alexey and Sergei, are a huge support. Sometimes my poor kids have to listen endlessly to my latest idea, until I am ready to write about it. And then they will even read the final piece, and continue to encourage me.

But the most important motivators are you, my readers. Your comments, your personal emails and your feedback keep me writing.

I am usually disappointed with American math text books. I have had an underwhelming experience with them. Often I open a book and in the next 15 minutes, I find a mistake, a typo, a misguided explanation, sloppiness, a misconception or some other annoyance.

I was pleasantly surprised when I opened the book Introduction to Algebra by Richard Rusczyk. I didn’t find any flaws in it — not in the first 15 minutes, and not even in the first hour. In fact, having used the book many times I have never found any mistakes. Not even a typo. This was disturbing. Is Richard Rusczyk human? It was such an unusual experience with an American math book, that I decided to deliberately look for a typo or a mistake. After half a year of light usage, I finally found something.

Look at problem 7.3.1.

Five chickens can lay 10 eggs in 20 days. How long does it take 18 chickens to lay 100 eggs?

There is nothing wrong with this problem. But the book is accompanied by the Introduction to Algebra Solutions Manual in which I found the following solution, that I’ve shortened for you:

The number of eggs is jointly proportional to the number of chickens and the amount of time. One chicken lays one egg in 10 days. Hence, 18 chickens will lay 100 eggs in 1000/18 days, which is slightly more than 55 and a half days.

What is wrong with this solution? Richard Rusczyk is human after all.

I like this book for its amazing accuracy and clean explanations. There are also a lot of diverse problems in terms of difficulty and ideas. Richard Rusczyk has good taste. Many of the problems are from different competitions and require inventiveness. I like that there are a lot of challenge problems that go beyond the boring parts of algebra. Also, I like that important points of algebra are chosen wisely and are emphasized.

This book might not be for everyone. It doesn’t have pretty pictures. It doesn’t have color at all. This is not a flaw for a math book. The book concentrates on ideas and problems, not entertainment. So if you’re looking for math entertainment, you’ll find it on my blog. For solid study, try Richard Rusczyk’s books.

I love Raymond Smullyan’s books , especially the trick puzzles he includes. The first time I met him in person, he played a trick on me.

This happened at the Gathering for Gardner 8. We were introduced and then later that day, the conference participants were treated to a dinner event that included a magic show. In one evening I saw more close-up magic tricks than I had in my whole life. This left me lightheaded, doubting physics and my whole scientific outlook on life.

Afterwards, Raymond Smullyan joined me in the elevator. “Do you want to see a magic trick?” he asked. “I bet I can kiss you without touching you.” I was caught off guard. At that moment I believed anything was possible. I agreed to the bet.

He asked me to close my eyes, kissed me on the cheek and laughed, “I lost.”

by Peter Winkler

As a writer of books on mathematical puzzles I am often faced with delicate issues of phrasing, none more so than when it comes to questions about conditional probability. Consider the classic “X has two children and at least one is a boy. What is the probability that the other is a boy?”

It is reasonable to interpret this puzzle as asking you “What is the probability that X has two boys, given that at least one of the children is a boy” in which case the answer is unambiguously 1/3—given the usual assumptions about no twins and equal gender frequency.

This puzzle confounds people *legitimately*, however, because most of the ways in which you are likely to find out that X has at least one boy contain an implicit bias which changes the answer. For example, if you happen to meet one of X‘s children and it’s a boy, the answer changes to 1/2.

Suppose the puzzle is phrased this way: X says “I have two children and at least one is a boy.” What is the probability that the other is a boy?

Put this way, the puzzle is highly ambiguous. Computer scientists, cryptologists and others who must deal carefully with message-passing know that what counts is not what a person says (even if she is known never to lie) but *under what circumstances would she have said it.*

Here, there is no context and thus no way to know what prompted X to make this statement. Could he instead have said “At least one is a girl”? Could he have said “Both are boys”? Could he have said nothing? If you, the one faced with solving the puzzle, are desperate to disambiguate it, you’d probably have to assume that what really happened was: X (for some reason unconnected with X‘s identity) was asked whether it was the case that he had at least one son, and, after being warned—by a judge?—that he had to give a yes-or-no answer, said “yes.” An unlikely scenario, to say the least, but necessary if you want to claim that the solution to the puzzle is 1/3.

Consider the puzzle presented (according to Alex Bellos) by Gary Foshee at the recent 9th Gathering for Gardner:

I have two children. One is a boy born on a Tuesday. What is the probability I have two boys?

If the puzzle was indeed put exactly this way, and your life depended on defending any particular answer, God help you. You cannot answer without knowing, for example, what the speaker would have said if he had one boy and one girl, and the boy was born on Wednesday. Or if he had two boys, one born on Tuesday and one on Wednesday. Or two girls, both born on Tuesday. Et cetera.

Now, there is nothing mathematically wrong (given the usual assumptions, including X being random) about saying that “The probability that X has two sons, given that at least one of X‘s two children is a boy born on Tuesday, is 13/27.” But if that is to be turned into an unambiguous puzzle attached to a presumed situation, some serious hypothesizing is necessary. For instance: you get on the phone and start calling random people. Each is asked if he or she has two children. If so, is it the case that at least one is a boy born on a Tuesday? And if the answer is again yes, are the children both boys? Theoretically, of the times you reach the third question, the fraction of pollees who say “yes” should tend to 13/27.

Kind of takes the fun out of the puzzle, though, doesn’t it? Kudos to Gary for stirring up controversy with a quickie.

I recently discussed the following problem:

You run into an old friend. He has two children, but you do not know their genders. He says, “I have a son born on Tuesday.” What is the probability that his second child is also a son?

I had heard this problem at the Gathering for Gardner 9 in a private conversation. My adversary had been convinced that the answer to the problem is 13/27. I came back to Boston from the gathering and wrote my aforementioned essay in which I disagreed with his conclusion.

I will tell you my little secret: when I started writing I substituted Wednesday for Tuesday. Then I checked my sons’ birthdays and they were born on Saturday and Tuesday. So I changed my essay back to Tuesday.

After I published it people sent me several links to other articles discussing the same problem, such as those of Keith Devlin and Alex Bellos, both of whom think the answer is 13/27. So I invented a fictional opponent — Jack, and here is my imaginary conversation with him.

Jack: The probability that a father with two sons has a son born on Tuesday is 13/49. The probability that a father with a son and a daughter has a son born on Tuesday is 1/7. A dad with a son and a daughter is encountered twice as often as a dad with just two sons. Hence, we compare 13/49 with 14/49, and the probability of the father having a second son is 13/27.

Me: What if the problem is about Wednesday?

Jack: It doesn’t matter. The particular day in question was random. The answer should be the same: 13/27.

Me: Suppose the father says, “I have a son born on *day.” He mumbles the day, so you do not hear it exactly.

Jack: Well, as the answer is the same for any day, it shouldn’t matter. The probability that his second child will also be a son is still 13/27.

Me: Suppose he says, “I have a son born …”. So he might have continued and mentioned the day, he might not have. What is the probability?

Jack: We already decided that it doesn’t depend on the day, so it shouldn’t matter. The probability is still 13/27.

Me: Suppose he says, “I have a son and I do not remember when he was born.” Isn’t that the same as just saying, “I have a son.” And by your arguments the probability that his second child is also a son is 13/27.

Jack: Hmm.

Me: Do you remember your calculation? If we denote the number of days in a week as d, then the probability of him having a second son is (2d−1)/(4d−1). My point is that this probability depends on the number of days of the week. So, if tomorrow we change a week length to another number his probability of having a son changes. Right?

At this point my imaginary conversation stops and I do not know whether I have convinced Jack or not.

Now let me give you another probability problem, where the answer is 13/27:

You pick a random father of two children and ask him, “Yes or no, do you have a son born on Tuesday?” Let’s make a leap and assume that all fathers know the day of the births of their children and that they answer truthfully. If the answer is yes, what is the probability of the father having two sons?

Jack’s argument works perfectly in this case.

My homework for the readers is: Explain the difference between these two problems. Why is the second problem well-defined, while the first one is not?

On March 5, 2010 I visited Princeton and had dinner with John Conway at Tiger Noodles. He gave me the second Doomsday lesson right there on a napkin. I described the first Doomsday lesson earlier, in which John taught me to calculate the days of the week for 2009. Now was the time to expand that lesson to any year.

As you can see on the photo of the napkin, John uses his fingers to make calculations. The thumb represents the DoomsDay Difference, the number of days your birthday is ahead of DoomsDay for a given year. To calculate this number you have to go back to my previous post.

The index finger represents the century adjustment. For example, the Doomsday for the year 1900 is Wednesday. Conway remembers Wednesday as We-are-in-this-day. He invented his algorithm in the twentieth century, not to mention that most people who use his algorithm were born in that century. Conway remembers the Doomsday for the year 2000 as Twosday.

The next three fingers help you to calculate the adjustment for a particular year. Every non-leap year has 52 weeks and one day. So the Doomsday moves one day of the week forward in one year. A leap year has one extra day, so the Doomsday moves forward two days. Thus, every four years the Doomsday moves five days forward, and, consequently, every twelve years it moves forward to the next day of the week. This fact helps us to simplify our year adjustment by replacing every dozen of years with one day in the week.

The middle finger counts the number of dozens in the last two digits of your year. It is important to use “dozen” instead of “12” as later we will sum up all the numerals, and the word “dozen” will remind us that we do not need to include it in the sum.

The ring finger represents the remainder of the last two digits of the year modulo 12, and the pinkie finger represents the number of leap years in that remainder.

John made two sample calculations on the napkin. The first one was for his own birthday — December 26, 1937. John was born exactly on Doomsday. I suspect that that is the real reason he called his algorithm the Doomsday Algorithm. The century adjustment is Wednesday. There are 3 dozens in 37, with the remainder 1 and 0 leap years in the remainder. When we add four more days to Wednesday, we get Sunday. So John Conway was born on Sunday.

The second napkin example was the day we had dinner: March 5, 2010. March 5 is 5 days ahead of the Doomsday. The century adjustment is Twosday, plus 0 dozens, 10 years in the remainder and 2 leap years in the remainder. 5 + 0 + 10 + 2 equals 3 modulo 7. Hence, we add three days to Tuesday, demonstrating that we dined out together on Friday. But then, we already knew that.

Do you know that some Russian letters are shaped exactly as some letters in the English alphabet? The shapes are the same, but the sounds of the letters are not. My Russian last name can be completely spelled using English letters: XOBAHOBA.

The adequate translation of my last name into English is Hovanova. You might ask where the first “K” came from. For many years French was considered the language of diplomacy and the USSR used French as an official language for traveling documents.

But “H” in French is silent and “Hovanova” would have been pronounced as “Ovanova.” To prevent that, Russians used “kh” for the “h” sound.

Now to my first name. I was born Tatyana, for which Tanya is a nickname. Back in Russia, Tanya is used for children and students and Tatyana for adults and teachers. As I was a student throughout my 30 years of life in Russia, I was always Tanya. When I moved to the US, I decided to keep using Tanya, which I much preferred to Tatyana.

A psychiatrist might think that I wanted to be a student forever or refused to grow up. Or I could be accused of being lazy, as Tanya is shorter. In reality, I was just trying to be considerate. Tanya is easier to write and to spell for Americans. Anyway, I already had enough problems spelling out my last name in this country.

Now that more information is getting translated from Russian into English, I keep stumbling on references to me as to Hovanova or Tatyana. For example, the IMO official website used Russian sources to come up with the names of the Russian participants. They then translated the names directly into English, instead of going through French. As a result, on their website I am Tatyana Hovanova. This is not unique to me: many Russian names on the IMO website differ from those peoples’ passport names.

By the way, if you Google my last name you will encounter other Khovanovas. Khovanova is not a particularly unusual name. Only one of the Khovanovas that came up in my search results is a close relative. Elizabeth Khovanova is my father’s second wife and a dear friend. She is also an accomplished geneticist.

Khovanova is used only for females in Russia. The male equivalent is Khovanov. Surely you have heard of my half-brother Mikhail Khovanov and his homologies.

I gave you the Wise Men Without Hats puzzle in one of my previous posts:

A sultan decides to check how wise his two wise men are. The sultan chooses a cell on a chessboard and shows it to the first wise man. In addition, each cell on the chessboard either contains a pebble or is empty. The first wise man has to decide whether to remove one pebble or to add one pebble to an empty cell. Next, the second wise man must look at the board and guess which cell was chosen by the sultan. The two wise men are permitted to agree on their strategy beforehand. What strategy can they find to ensure that the second wise man will always guess the chosen cell?

My readers solved it. The solution is the following. Let us assign a number between 0 and 63 to every cell of the board. The second wise man takes numbers corresponding to cells with pebbles, converts them to binary and XORs the result. The answer is the cell number that he is seeking. The first wise man can always add or remove a pebble to make the XORing operation of the remaining pebbles produce any given number from 0 to 63.

This solution only works for boards that have a power of two as the number of cells.

Let’s look at the solution more closely. Let us create a graph corresponding to this problem. The vertices of the graph will correspond to the positions of pebbles. That means vertices are in one-to-one correspondence with the subsets of the set of 64 elements. Let us connect two vertices if we can get from one position to another by removing or adding a pebble. That means vertices are connected if two corresponding sets differ by exactly one element. We can see that the resulting graph is regular and each vertex is connected to exactly 64 other vertices.

Let us assign one out of 64 colors to each cell of the chessboard. The second wise man can guess the cell by looking at the chessboard. From this we can conclude that there is a bijection from the vertices of the graph to chessboard cells. In other words, we can color the graph in 64 colors. The existence of the strategy for wise men means that we can color the graph in such a way that each vertex is connected to the vertices of all colors.

As each vertex in our graph has exactly 64 neighbors, the graph has the following property: It can be colored in 64 colors in such a way that every vertex is connected to exactly one vertex of every color.

As soon as I realized that there is such a graph-theoretical object, I started to run around MIT asking everyone if such objects were studied or have a name.

It appears that indeed such an object has a name. A graph that can be colored into k colors in such a way that every vertex has exactly one neighbor of every color is called a rainbow graph.

Andrew Woldar discusses properties of such graphs in his paper. In particular, rainbow graphs are matching graphs. Indeed, every vertex is connected to exactly one vertex of the same color. Hence there is a natural pairing on vertices. From here, we can conclude that the smallest size of a rainbow graph is 2k.

Several MIT students liked the wise men problem and the associated graph object so much that they decided to study them. Hwanchul Yoo, SuHo Oh, and Taedong Yun enumerated all rainbow graphs of size 2k. The number of non-isomorphic rainbow graphs of size 2k equals mitthe number of switching classes of graphs with k vertices. The corresponding sequence A002854 starts as: 1, 1, 2, 3, 7, 16, 54. The paper is soon to appear. It is titled “Rainbow Graphs and Switching Classes.”

Just received from Victor Gutenmacher:

Fibonacci salad: For today’s salad, mix yesterday’s leftover salad with that of the day before.

New additions to my trick problems collection:

* * *

It takes 12 minutes to saw a log into 3 parts. How much time will it take to saw it into 4 parts?

* * *

The Davidsons have five sons. Each son has one sister. How many children are there in the family?

* * *

A caterpillar wants to see the world and decides to climb a 12-meter pole. It starts every morning and climbs 4 meters in half a day. Then it falls asleep for the second half of the day during which it slips 3 meters down. How much time will it take the caterpillar to reach the top?