Tanya Khovanova's Math Blog

I started my blog about two year ago. I have written about 200 entries. According to my traffic reports, these have been the top ten most popular entries:

1. The Odd One Out
2. Divisibility by 7 is a Walk on a Graph, by David Wilson
3. The Dirtiest Math Problem Ever (Rated R)
4. My IQ
5. A Miracle Equation
6. Back-to-School Funny Pictures
7. Flexible Zipcar Algorithm
8. A Very Special Ten-Digit Number
9. What Does It Take to Get Accepted by Harvard or Princeton?
10. AMC, AIME, USAMO Contradiction

My most popular category was Math Humor.

Israel Gelfand’s memorial is being held at Rutgers on December 6, 2009. I was invited as Gelfand’s student.

My relationship with Gelfand was complicated: sometimes it was very painful and sometimes it was very rewarding. I was planning to attend the memorial to help me forget the pain and to acknowledge the good parts.

I believe that my relationship with Gelfand was utterly unique. You see, I was married three times, and all three times to students of Gelfand.

Now that I know that I can’t make it to the memorial, I can’t stop wondering how many single male students of Gelfand will be there.

I’ve translated two problems from the 2009 Moscow Math Olympiad. In both of them our characters are genetically engineered octopuses. The ones with an even number of arms always tell the truth; the ones with an odd number of arms always lie. In the first problem (for sixth graders) four octopuses had a chat:

• “I have 8 arms,” the green octopus bragged to the blue one. “You have only 6!”
• “It is I who has 8 arms,” countered the blue octopus. “You have only 7!”
• “The blue one really has 8 arms,” the red octopus said, confirming the blue one’s claim. He went on to boast, “I have 9 arms!”
• “None of you have 8 arms,” interjected the striped octopus. “Only I have 8 arms!”

Who has exactly 8 arms?

Not only do octopuses lie or tell the truth according to the parity of the number of their arms, it turns out that the underwater world is so discriminatory that only octopuses with six, seven or eight arms are allowed to serve Neptune. In the next problem (for seventh graders), four octopuses who worked as guards at Neptune’s palace were conversing:

• The blue one said, “All together we have 28 arms.”
• The green one said, “All together we have 27 arms.”
• The yellow one said, “All together we have 26 arms.”
• The red one said, “All together we have 25 arms.”

How many arms does each of them have?

My students enjoyed the octopuses, so I decided to invent some octopus problems of my own. In the first problem, the guards from the night shift at Neptune’s palace were bored, and they started to argue:

• The magenta one said, “All together we have 31 arms.”
• The cyan one said, “No, we do not.”
• The brown one said, “The beige one has six arms.”
• The beige one said, “You, brown, are lying.”

Who is lying and who is telling the truth?

In the next problem the last shift of guards at the palace has nothing better to do than count their arms:

• The pink one said, “Gray and I have 15 arms together.”
• The gray one said, “Lavender and I have 14 arms together.”
• The lavender one said, “Turquoise and I have 14 arms together.”
• The turquoise one said, “Pink and I have 15 arms together.”

What number of arms does each one have?

An ancient Russian joke:

Patient: Doctor, is there a medicine I can use to prevent my girlfriends from become pregnant?
Doctor: Kefir.
Patient: Should I drink it before or after sex?
Doctor: Instead of.

I have a more pleasurable suggestion than drinking kefir: date postmenopausal women. There are many other reasons why men enjoy dating older women, but since my blog is about mathematics, I would like to dig into some relevant numbers.

We know that boys are born more often than girls, and men die earlier than women. Somewhere around age 30 the proportion in population switches from more boys to more girls. And it gets more skewed with age. So there’s a deficit of older men. In addition, a big part of the population is married, making the disproportions in singles group more pronounced. So I decided to look at the numbers to see how misshaped the dating scene is.

This 2008 data comes from the U.S. government census website’s table “Marital Status of the Population by Sex and Age: 2008. (Numbers in thousands. Civilian non-institutionalized population.)” To calculate the number of singles, I summed up the widowed, divorced and never married columns.

These data alone cannot explain the dating situation. For example, I have no way of knowing what proportion of each gender isn’t interested in dating the opposite sex, or even in dating altogether. But the trend is quite clear: the proportion of men in younger categories is much higher. That implies that there is less competition for older women. So those young men who are open to dating much older women might have more options and those options might be more interesting.

I just turned 50 and plan to return to dating again. Looking at the data I see that there are 11 million single men older than me and 34 million who are younger than me. If I were to pick a single man randomly, I am three times more likely to end up with a younger man.

Supposedly we live in a free society, where people can do what they want as long as they do not harm anyone else. Still our society often disapproves of women dating much younger men. Consider this definition from Wikipedia:

“Cougar — a woman over 40 who sexually pursues a much younger men.”

This derogatory term portrays such women as predatory. Not only is there nothing wrong with women dating younger men, but it makes no sense for older women to ignore the imbalance of the dating scene and be closed to relationships with much younger men. After all, the demographics are also affected by the fact that women live longer, probably because of their healthy life style, non-risky behavior and positive attitude to life.

Can someone explain to me again why sane, healthy, non-risky women with positive attitudes to life are called “cougars”?

The first episode of Numb3rs: Season Six reminded me of the hangman’s paradox. Here is a one-day version of the hangman’s paradox:

Suppose you are in a prison and the guard says to you, “You will be hanged tomorrow at noon and it will be a surprise.” You presume that you can’t be surprised since they already told you, so there is a contradiction in what they’ve said. Therefore, you conclude that they can’t hang you and you relax. Next day at noon the guard comes for you, to take you to be hanged, and you are utterly surprised. Oops.

What I do not like about this paradox is that it assumes that you do not know about the paradox. I, on the other hand, imagine that you, my reader, are logical and intelligent. So the moment the guard tells you that you will be hanged tomorrow at noon and it will be a surprise, you realize that the situation depends on what you decide to believe in now. If you decide that you won’t be hanged tomorrow, then you will have a relatively relaxing day today and you will be caught by surprise tomorrow and die. If you decide that you will die tomorrow, then you will have a nerve-wracking day today, but the guard may release you, to save his honor, since you won’t be surprised.

The original hangman’s paradox in which the guard tells you that you will be hanged on a weekday the following week and that you will be caught by surprise, also assumes that you are not aware of the paradox. If you are aware of the paradox, you know that usually guards in this paradox come for you on Wednesday, so you can prepare yourself. Actually, to guarantee your survival, if not your feeling of moral superiority, you can daily persuade yourself to belief that you will be hanged at noon the next day. This way, you will never be caught by surprise. If you are a person who can control your own beliefs, you may be able to save your life.

The book An Introduction to Diophantine Equations by Titu Andreescu and Dorin Andrica is targeted at people preparing for USAMO and IMO. It contains a lot of problems on Diophantine equations from math Olympiads used in various math Olympiads all over the world.

The first chapter discusses several methods for solving Diophantine equations: decomposition, using inequalities, using parameters, modular arithmetic, induction, infinite descent, and other miscellaneous ideas. Each sub-chapter starts with a short description of the method, accompanied by several solutions to sample problems. At the end of each sub-chapter there are a plethora of exercise problems.

The second and the third chapters are more theoretical. The former discusses some classical equations and the latter looks at Pell’s equation. These two chapters also contain problems, but the bulk of the chapters is devoted to basic theory that is essential to an understanding of Diophantine equations.

For those who are training for the Olympiads, this is an important book to own, not only because there are few other books on the subject, but because it provides so many useful problems.

I’ve long complained that most training books for math competitions leave out any discussion of how we choose a method by just looking at a problem. Andreescu and Andrica didn’t fill that gap with this book.

Perhaps in their next book they will point out clues that indicate that a particular problem might be solved by the parametric method. And explain which types of problems are best solved with induction. Let them challenge students to find those clues in a problem that help us to judge which method might be most promising, instead of randomly trying one method after another. Let me give you a sample problem from the book, which originated at the Balkan Mathematical Olympiad:

Prove that the equation x⁵ – y² = 4 has no solutions in integers.

The solution is to take the equation modulo 11, and see that it is impossible.

Is there a reason to start with the modular arithmetic method and not with other methods? If we use modular arithmetic, do we recognize why it’s best to start with 11? I’m convinced that this problem has sufficient clues to suggest starting with checking this equation modulo 11.

I wonder if you, my readers, agree with me. If so, can you explain which hints in the problem lead to taking the equation modulo 11? I believe it should be a part of competition training to learn to identify clues that suggest that one direction might be preferable to the others.

I love Harvard-MIT Math Tournaments. I like the mini-events, especially when I learn a new game. I also like the guts round, where I enjoy the adrenaline rush of watching the progress in real time. I also like the fact that I know many of the kids from different teams: my current students, my former students, the members of my club, my Sergei’s friends.

The problems for the competitions are designed by undergraduate students at MIT and Harvard. Kudos to them. Still, I was somewhat disappointed with the November 2009 problems. Most problems are variations of standard problems with different parameters. It is not easy to design a problem, but I was hoping for something fresh.

My favorite problem from the HMNT 2009 tournament was in the theme round:

There are five guys named Alan, Bob, Casey, Dan, and Eric. Each one either always tells the truth or always lies. You overhear the following discussion between them:

• Alan: “All of us are truth-tellers.”
• Bob: “No, only Alan and I are truth-tellers.”
• Casey: “You are both liars.”
• Dan: “If Casey is a truth-teller, then Eric is too.”
• Eric: “An odd number of us are liars.”

Who are the liars?

My second favorite problem was in the guts round:

Six men and their wives are sitting at a round table with 12 seats. These men and women are very jealous — no man will allow his wife to sit next to any man except for himself, and no woman will allow her husband to sit next to any woman except for herself. In how many distinct ways can these 12 people be seated such that these conditions are satisfied? (Rotations of a valid seating are considered distinct.)

This was the funniest problem:

You are trapped in ancient Japan, and a giant enemy crab is approaching! You must defeat it by cutting off its two claws and six legs and attacking its weak point for massive damage. You cannot cut off any of its claws until you cut off at least three of its legs, and you cannot attack its weak point until you have cut off all of its claws and legs. In how many ways can you defeat the giant enemy crab? (Note that the legs are distinguishable, as are the claws.)

It is difficult to arrange so many problems for four rounds without mistakes. The error in the following problem is not a typo and it bothers me that no one caught it:

Pick a random digit in the decimal expansion of 1/99999. What is the probability that it is 0?

Hey, there is no uniform distribution on an infinite set of integers: picking a random digit is not defined.

Last month I gave my students a problem from Raymond Smullyan’s book The Riddle of Scheherazade:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. How many of them can each say that it is the same color as another one of Hassan’s horses?

Half of my students failed to notice the trick and gave the wrong answer. Recently I gave them the continuation of the problem from the same book:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. Assuming now that Hassan’s horses can talk, how many of them can each say that it is the same color as another one of Hassan’s horses?

This time the majority of my students didn’t notice the trick. This motivated me to continue playing jokes with them. Unfortunately though, Raymond Smullyan had only two problems about Hassan’s horses, so I have to invent the next one myself. Here is what I plan to give my students next time:

A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. Assuming now that Hassan’s horses can talk and always tell the truth, how many of them will say that it is the same color as another one of Hassan’s horses?

Feel free to continue the series.

My recent blog puzzle where my readers had to choose the odd one out became extremely popular and was republished in many blogs around the world. Some commentators decided that my posting was a joke and an example where the odd one out didn’t exist. I have to disappoint them: as a protest against find-the-odd-one-out questions and to illustrate that sometimes there is no good choice for the odd one out I would have chosen a different picture:

Can you find the odd one out?

Inspired by Michael Huber, who in his new book Mythematics combines math problems with Greek myths, I invented my first logic puzzle. Unlike Huber, I never had any ambition to help Hercules, but I always wanted to assist Frodo.

The day was passing towards sunset when the Company finally caught a long-awaited gleam of water, from which sparkled flickers of sunlight. As they quietly drew nearer, they laid their eyes on the next obstacle — a river that they had to transverse. The Company was footsore and tired and the hobbits were starving. But they couldn’t rest yet. They needed to collect materials with which to construct their raft before it became too dark. By nightfall they managed to build a tiny raft, and eagerly started their supper.

They couldn’t wait until dawn to build more rafts, for they needed to cross the river now. So while they rested, Aragorn smoked his pipe and began to contrive a plan.

Aragorn was in charge and there were eight of them. The four hobbits — Frodo, Sam, Merry and Pippin — were not very useful in battle. However, the four strong fighters — Aragorn, Gimli, Legolas and Boromir, who were sworn to protect the ring-bearer Frodo — were the best in the land.

The small raft they had built would not hold a lot of weight. Aragorn and Boromir were the heaviest. Gimli was short, but together with his armor he weighed as much as either Aragorn or Boromir. Each one of these three heaviest warriors was close to the raft’s maximum capacity, so they had to each be alone on the raft while crossing the river. Among the strong fighters, only Legolas was able to cross the river with a hobbit. The raft could also accommodate two hobbits.

Weight was not Aragorn’s only consideration: the current was dangerously fast. All the strong men could row, but among the hobbits, only Sam was strong enough to row against such a swift current.

Aragorn also worried about the orcs, who were roaming on both sides of the river. He didn’t want to leave any hobbit(s) alone on a riverside, without the safeguard of a strong fighter. Because he was the ring-bearer, Frodo needed extra protection. Aragorn wanted Frodo to be accompanied by at least two strong men. But lately Boromir had become restless when he was around the ring and Aragorn couldn’t count on him to look after Frodo. That is, while on the riverside, Frodo’s protection had to come from two out of the three remaining strong men: Aragorn, Legolas and Gimli.

Can you help Aragorn design a plan to cross the river?