Tanya Khovanova's Math Blog

You are visiting your girlfriend and she orders pizza. Your evil girlfriend has perfect eyesight and notices fly droppings in three places on the pizza. She is seeking revenge on you for refusing to babysit her poodle and proceeds to cut the pizza. Assuming that the droppings occurred independently and in random places, what is the probability that she will be able to cut a half-circle pizza slice with all three droppings in one half?

Now that I’ve ruined your appetite, here’s a simpler puzzle you can solve as an appetizer to the one I just gave you above. In this puzzle, you have a bread stick that is, of course, in the shape of a line segment. Your girlfriend notices that the bread stick also has three fly droppings on it and she offers to cut an exact half length out of the middle for you. What is the probability that she can cut it so that you end up with all the droppings?

Can you bear to continue this tasty discussion? If so, I’ll give you an even simpler problem. Try to solve both of the above puzzles — but with only two droppings instead of three.

If I’ve spoiled your appetite so completely that you’ll skip dinner, why not use the extra time to solve the most challenging of these problems with a meatball that has four fly droppings on it. These droppings, too, are in random places and you must calculate the probability that you are able to cut a semi-sphere with all four droppings on one side.

This final puzzle — in a less distasteful setting — was sent to me by Nick Petry.

I have an old book which I value a great deal. The book is called 200 Problems in Linguistics and Mathematics and only 1,550 copies were printed in 1972. Luckily, a new extended edition just appeared on the web. Both editions are in Russian, so I decided to translate some of the problems into English. Here is a sample:

Problem 1. Here are phrases in Swahili with their English translations:

• atakupenda — He will love you.
• nitawapiga — I will beat them.
• atatupenda — He will love us.
• anakupiga — He beats you.
• nitampenda — I will love him.
• unawasumbua — You annoy them.

Translate the following into Swahili:

• You will love them.
• I annoy him.

Problem 2. You are given words in Swahili: mtu, mbuzi, jito, mgeni, jitu and kibuzi. Their translations in a different order are: giant, little goat, guest, goat, person and large river. Make the correspondence.

Problem 3. In Russian the middle name is the patronymic. Thus, the middle initial is the first letter of the father’s first name. And, as in many languages, the first initial is the first letter of the first name. Here are names of males in a family:

• A.N. Petrov
• B.M. Petrov
• G.K. Petrov
• K.M. Petrov
• K.T. Petrov
• M.M. Petrov
• M.N. Petrov
• N.M. Petrov
• N.K. Petrov
• N.T. Petrov
• T.M. Petrov

Draw the family tree of the Petrovs, given that every father has two sons, the patriarch of the family has four grandsons, and his sons have two grandsons each. Prove that the solution is unique.

Problem 4. In Latvian a noun can be one of two genders; furthermore, adjectives agree with nouns in gender, number and case. You are given phrases in either the nominative or the genitive case with their translations:

• silts ezers — warm lake
• melns lauva — black lion
• liela krāsns — big oven
• lielas jūras — big sea’s
• sarkana ezera — red lake’s
• melna kafija — black coffee
• sarkans putns — red bird
• liela kalna — big mountain’s
• sarkanas lapas — red leaf’s
• sarkana pils — red castle
• liels ezers — big lake
• melna putna — black bird’s
• liela lauvas — big lion’s
• silta jūra — warm sea
• melnas kafijas — black coffee’s
• liels kalns — big mountain

Indicate which words are nouns and which are adjectives. Divide Latvian nouns into two groups, so that each group contains words of the same gender.

Problem 5. The Portuguese language takes its roots from Latin. In this problem modern Portuguese words are written on the left and their roots (in Latin and other languages on the right). All the words on the left belong to one of three classes: ancient borrowing, early borrowing and late borrowing.

• chegar — plicare
• praino — plaine
• plátano — platanum
• chão — planum
• plebe — plebem
• cheio — plenum
• prancha — planche

For every Portuguese word, indicate which class it belongs to. (Note that in Portuguese “ch” is pronounced as “sh”.)

I bought the book “Math Doesn’t Suck: How to Survive Middle School Math Without Losing Your Mind or Breaking a Nail“ by Danica McKellar because I couldn’t resist the title. Sometimes this book reads like a fashion magazine for girls: celebrities, shopping, diet, love, shoes, boyfriends. At the same time it covers elementary math: fractions, percents and word problems.

You can apply math to anything in life. Certainly you can apply it to fashion and shoes. I liked the parallel between shoes and fractions that Danica used. She compared improper fractions to tennis shoes and mixed numbers to high heels. It is much easier to work with improper fractions, but mixed numbers are far more presentable.

Danica is trying to break the stereotype that girls are not good at math by feeding all the other stereotypes about girls. If you are a typical American girl who hates math and missed some math basics, this book is for you. If you want to discover whether the stars are on your side when you are learning math, the book even includes a math horoscope.

I am celebrating the first hundred essays I have written for my blog. My English teacher and editor Sue Katz edited most of them. Sue Katz not only corrects my English mistakes, but also helps me to choose better and more descriptive words and rearranges my text so that it doesn’t sound like a direct translation from Russian.

If you’re looking for an editor, she’s superb.

Sue is an extremely interesting person. She was one of the first women to gain a black belt in Tae Kwon Do and taught martial arts and dance on three continents. Now she concentrates on her blog and writing. In her blog Sue Katz: Consenting Adult she writes a lot about sex and also about current affairs. She reviews books and movies and expresses her interesting and unique perspective on things. Some of my favorite posts:

• Philosophical and romantic — Six-Word Memoirs: Sought revolution, got pantsuits, want more
• Down-to-earth and funny — The Drip Dominatrix rules her bladder
• Bitter and sweet — Film Review: The Diving Bell and the Butterfly

I am not only grateful to Sue for the excellent professional job, but also for encouraging me. She laughs at my jokes and is a devoted fan of my blog. Thank you, Sue!

I love “Knights and Knaves” logic puzzles. These are puzzles where knights always tell the truth and knaves always lie. A beautiful variation of such a puzzle with Gnyttes and Mnaivvs was given at the 2009 MIT mystery hunt. In this puzzle people’s ability to tell the truth changes during the night depending on the sex partner. You will enjoy figuring out who is a Gnytte or a Mnaivv for each day, who is infected and who slept with whom on each night. Just remember that the ultimate answer to the puzzle is a word or a phrase. So there is one more step after you solve the entire logic part. You do not really need to do this last step, but you might as well. Here we go:

The Sexaholics of Truthteller Planet

Each inhabitant of Veritas 7, better known as the Truthteller Planet, manifests one of two mutations: Gnytte or Mnaivv. Gnyttes always tell the truth, and Mnaivvs always lie. Once born a Gnytte or Mnaivv, the inhabitant can never change…until now.

Veritas 7 is in the midst of an outbreak of a nasty virus dubbed Nallyums Complex II. If an infected inhabitant has sex with another inhabitant of that planet, each one can be converted from Gnytte to Mnaivv, or Mnaivv to Gnytte, as shown below:

• If the sex is heteroverific (1 Gnytte and 1 Mnaivv), both become Mnaivvs.
• If the sex is homoverific (2 Gnyttes or 2 Mnaivvs), both become Gnyttes.

This occurs if either party or both parties have the disease. The disease itself is not transmitted via sex, which is some relief.

Several members of a Veritas 7 village have just contracted Nallyums Complex II. Below are statements from the 15 village residents, taken over the 5-day period since the outbreak. Interviews were taken each morning, and sex occured only at night. Each night, residents paired off to form seven separate copulating couples, with one individual left out. No individual was left out for more than one night.

Can you identify the infected individuals and track their pattern of sexual activity?

A note on wording: If someone refers to sex with someone who was a Gnytte or Mnaivv, they are referring to the individual’s truth-telling status just before sex. If a clue says that two individuals had sex, it means they had sex with each other. “Mutation” refers to the individual’s current status as Gnytte or Mnaivv.

Interviews Day 1

• Artoo: Etrusco is not infected.
• Bendox: Cravulon and Flav are not the same mutation today.
• Cravulon: Either Artoo or Flav is a Gnytte today.
• Dent: Jax-7 and I are both Mnaivvs today.
• Etrusco: Greasemaster is a Mnaivv today.
• Flav: There are at least five Mnaivvs today.
• Greasemaster: Murgatroid is a Gnytte today.
• Holyoid: Etrusco is either an infected Mnaivv or an uninfected Gnytte today.
• Irono: Etrusco is a Mnaivv today.
• Jax-7: Among Artoo, Greasemaster, and Nebulose, exactly one is a Gnytte today.
• Killbot: Bendox is a Gnytte today.
• Lexx: Holyoid and Irono are not the same mutation today.
• Murgatroid: There are at least eight Gnyttes today.
• Nebulose: Murgatroid is a Mnaivv today.
• Oliver: Lexx is a Gnytte today.

Surveillance Night 1

Security cameras revealed that Jax-7 did not have sex with anyone last night, and that Nebulose and Murgatroid had sex.

Interviews Day 2

• Artoo: Last night, I did not have sex with an infected individual.
• Bendox: Last night, Oliver had sex with someone who was a Mnaivv.
• Cravulon: There are at least six Gnyttes today.
• Dent: If there are only five Gnyttes today, then Cravulon and Oliver had sex last night.
• Etrusco: Last night, Bendox had sex with someone who was a Mnaivv.
• Flav: Neither Killbot nor her partner last night is infected.
• Greasemaster: Last night, either Cravulon and Bendox had sex, or Oliver and Etrusco had sex, but not both.
• Holyoid: Last night, I had sex with someone who was a Gnytte.
• Irono: Last night, I did not have sex with Flav.
• Jax-7: Last night, Artoo had sex with Dent.
• Killbot: Last night, I had sex with someone who was a Mnaivv.
• Lexx: Cravulon is infected.
• Murgatroid: Nebulose is not infected.
• Nebulose: Last night, either Cravulon or Flav had sex with Etrusco.
• Oliver: Last night, Irono had sex with someone who was a Mnaivv.

Surveillance Night 2

Security cameras revealed that Holyoid did not have sex with anyone last night, and that Irono and Oliver had sex.

Interviews Day 3

• Artoo: Last night, I had sex with the individual who had sex with Murgatroid on Night 1.
• Bendox: Last night, I had sex with an uninfected individual.
• Cravulon: Last night, Jax-7 had sex with the individual who had sex with Lexx on Night 1.
• Dent: Last night, I had sex with someone who was a Mnaivv.
• Flav: Last night, I had sex with an uninfected individual.
• Holyoid: Neither Oliver nor Irono is infected.
• Irono: Last night, the individual who had sex with Oliver on Night 1 had sex with someone who was a Mnaivv.
• Jax-7: There are more than seven Gnyttes today.
• Killbot: Bendox and Murgatroid are the same mutation today.
• Lexx: Last night, the individual who had sex with Flav on Night 1 had sex with an infected individual.
• Nebulose: The individual who had sex with Etrusco on Night 1 is a Mnaivv today.
• Oliver: Last night, Lexx had sex with the individual who had sex with Bendox on Night 1.

Surveillance Night 3

Security cameras revealed that Dent and Jax-7 had sex.

Interviews Day 4

• Artoo: There are at most seven Gnyttes today.
• Cravulon: Last night, I had sex with someone who has never been a Gnytte.
• Dent: The two sex partners of an individual who was a Mnaivv on the first three days had sex last night.
• Etrusco: Last night, Oliver did not have sex.
• Flav: Last night, I had sex with an infected individual.
• Greasemaster: There are exactly eight infected individuals.
• Killbot: None of the individuals who have been left out of the sexual activity is infected.
• Murgatroid: Last night, I had sex with someone who was a Gnytte on Day 1.
• Nebulose: Last night, I had sex with someone who has had sex with Artoo.
• Oliver: Last night, an individual who had sex with Holyoid during one of the first two nights had sex with an individual who had sex with Jax-7 during one of the first two nights.

Surveillance Night 4

Security cameras have been vandalized.

Interviews Day 5

• Artoo: Last night, I had sex with a Mnaivv, but not the individual who, on Night 3, had sex with the individual who, on Night 2, had sex with the individual who, on Night 1, had sex with Dent.
• Bendox: Last night, Dent had sex with the individual who, on Night 1, had sex with the individual who, on Night 3, had sex with the individual who, on Night 2, had sex with Artoo.
• Cravulon: Last night, Holyoid had sex with the individual who, on Night 3, had sex with the individual who, on Night 2, had sex with the individual who, on Night 1, had sex with Murgatroid.
• Dent: Jax-7 is a Gnytte today.
• Flav: Last night, Cravulon did not have sex with the individual who, on Night 1, had sex with the individual who, on Night 2, had sex with the individual who, on Night 3, had sex with Cravulon.
• Jax-7: Last night, Greasemaster did not have sex.
• Nebulose: Last night, Killbot either had sex with an uninfected individual or did not have sex.

I do not remember where I dug this logic puzzle out from:

Folks living in Trueton always tell the truth. Those who live in Lieberg, always lie. People living in Alterborough alternate strictly between truth and lie. One night 911 got a call: “Fire, help!” The operator couldn’t identify the phone number, so he asked, “Where are you calling from?” The reply was Lieberg.
Assuming no one had overnight guests from another town, where should the firemen go?

After you have solved this problem, you will see that the sentence “Fire, help!” is true. I wonder, if this statement were a lie, how would we interpret it? It could be that it is just a joke and there is no fire and therefore no need for the police. Or it could be that help is needed — perhaps for a robbery, but not for a fire.

However, when you solve this puzzle, you’ll find out that the “Fire, help!” statement is true, so you do not need to wonder what it would mean if the statement were a lie. But I wondered, and as a result I invented several new puzzles.

Here is the first one:

Let’s say that people will call the police only if something is happening and there are only two things that could be happening: fire or robbery. Suppose that when people calling the police need to lie, they replace fire with robbery, and vice versa. Suppose also that when asked about location, people will not say, &quotI am not from Lieberg,” as they could have, but will always reply with one word, which is a name of one of three towns. So, there are two possibilities for the first statement — Fire, Help! or Robbery, Help! — and three possible answers to the question about location. — Trueton, Lieberg and Alterborough. My puzzle in this case is: What answer to the location question will give the biggest headache to the police?

We can branch the original puzzle out in a different way. Here is my second puzzle:

We can assume that only fire, not robbery, could happen in this remote place and when people call the police they either say “Fire, help!” or “We do not have a fire, thank you for your time.” Let us again assume that people will call the police only if something is happening. In this case, what combinations of first and second sentences of the callers will never happen?

My third puzzle is a more complicated version of the second puzzle:

Let’s assume that fires happen with the same probability in every town and that the cost of sending a team of firefighters is identical for every town. Furthermore, the ferocity of all the fires is minuscule and the cost of sending a team is the same, whether or not it turns out that there is a fire. If the police think that the call could have come from several places, they send several teams and the cost multiplies accordingly. The police are obsessed with making charts and the most important number they analyze is the cost they incur, depending on the content of the first sentence of each call.
Given that there are frequent fires, what could the ratio of the cost to police for the calls “Fire, help!” be compared to those that begin with “We do not have a fire, thank you for your time”?

I wanted to see how different presidents affected the Dow Jones index. The index was invented at the end of the nineteenth century, so for my convenience, I will start my analysis from the beginning of the twentieth century. I skipped the presidents who were in office for only four years — four years might not be enough to rebuild a bad economy or to destroy a good one. Besides, in order to give the presidents a fair chance, I compared them for the same time period: eight years.

So I removed from my consideration all those who only served for four years: William Howard Taft, Herbert Hoover, Jimmy Carter and George H.W. Bush. I also combined two presidents together, when one succeeded the other mid-term for a total of eight years. Namely, I combined Warren Harding with Calvin Coolidge, John Kennedy with Lyndon Johnson, and Richard Nixon with Gerald Ford. For Franklin Roosevelt, I only considered the first eight years of his presidency.

Please note that it was not always precisely eight years — the inauguration date was sometimes moved. So Theodore Roosevelt and Harry Truman had slightly less than eight years. I tried to use the Dow Jones index from the exact day of each inauguration, but not all the dates were available in the file I used. So sometimes I had to pick the previous day.

Some might argue that I need to scale the Dow Jones Index. For example, the inflation rate was very different for different presidents. It is generally accepted that the value of one point in the Dow Jones Index decreases with time, but inflation is only one of many elements contributing to that change. Nonetheless, I took a look at that and the resulting picture didn’t change much anyway when I adjusted for inflation.

The Dow Jones is just one number. An increase in the Dow Jones does not completely describe the state of the economy, but it is certainly an interesting measure in its own right.

Let’s look at how the presidents and the presidential teams performed, sorting them from best to worst:

When I started this calculation I expected Clinton to be doing well and Bush badly, I just didn’t know exactly how good/bad they were. But the most interesting result of this exercise is the fact that the highest increase in DJI happened right before the Great Depression.

What can I say? I should have done this analysis eight years ago. Maybe the proximity of Clinton’s performance to the pre-depression boom could have urged me to move my 401(k) from stocks. Sigh.

The computational linguistics Olympiad started in Moscow in 1962. I first participated when I was in seventh grade. The Olympiad had two sets of problems: the first set was more difficult and meant for seniors, and the second set was for everyone else. Although the sets overlapped, they were significantly different. I should mention that the Soviet Union had 10 grades at that time and prizes were awarded by grade.

I achieved my best result when I was in ninth grade, just below the senior level. During the competition, I solved all the problems for non-seniors and still had a lot of time left. Luckily for me, both sets of problems were in the same booklet, so I proceeded to solve the problems for seniors.

I won two first place prizes: for my ninth grade and for the tenth grade, too.

The following year I was in tenth grade and I felt strange. I couldn’t compete on two levels as I was overqualified for non-seniors. So it was impossible to repeat my result. I could only go downhill — winning only one first place in the best case. So, I didn’t go to the competition at all.

Someone told me that I was arrogant not to go. But what they didn’t know was that I hadn’t been able to stop worrying: what if I didn’t win first place? All my friends cheered me on during my competitions, and I was afraid to let them down. To this day I can remember my fear of performing worse than the year before.

The organizers of the computational linguistics Olympiad had another reason to think I was arrogant. After my successes, they tried to persuade me to go into linguistics. I actually considered that until someone told me that all the computational linguistics majors are later employed by the KGB. The minute I heard that, I lost all interest in linguistics for many years to come. I told the organizers that all my success was due to my impeccable logic, not to my linguistics ability, so there was no point for me to go into linguistics. My arrogance was reaffirmed.

Recently my son Sergei started to compete in the computational linguistics Olympiad, which reminded me of how interesting linguistics can be. I wonder if Sergei will get a call from the CIA.

Computational Linguistics Olympiads started in Moscow in 1962. Finally in 2007 the US caught up and now we have the NACLO — North American Computational Linguistics Olympiad.

The problems from past Soviet Olympiads are hard to find, so here I present a translation from Russian of a sample problem from the Moscow Linguistics Olympiad website:

You are given sentences in Niuean language with their translations into English:

1. To lele e manu. — The bird will fly.
2. Kua fano e tama. — The boy is walking.
3. Kua koukou a koe. — You are swimming.
4. Kua fano a ia. — He is walking.
5. Ne kitia he tama a Sione. — The boy saw John.
6. Kua kitia e koe a Pule. — You are seeing Pule.
7. To kitia e Sione a ia. — John will see him.
8. Ne liti e ia e kulï. — He left the dog.
9. Kua kai he kulï e manu. — The dog is eating the bird.

Translate the following sentences into Niuean:

1. John swam.
2. You will eat the dog.
3. Pule is leaving you.
4. The bird will see the boy.
5. The dog is flying.

I was interested for some time in the divisibility of odd Fibonacci numbers. Fibonacci numbers are closely related to Lucas numbers. Lucas numbers L_n follow the same recurrence as Fibonacci numbers: L_n = L_n-1 + L_n-2, but with a different start: L₀ = 2, L₁ = 1. Obviously, every third Fibonacci and every third Lucas number is even.

Primes that divide odd Lucas numbers divide odd Fibonacci numbers. Let us prove this. Suppose a prime p divides an odd Lucas number L_k, then we can use the famous identity F_2k = F_kL_k. We see that p divides F_2k. The fact that L_k is odd means that k is not divisible by 3 and so is 2k. Thus F_2k is an odd Fibonacci that is divisible by p.

We see that primes that divide odd Lucas numbers are a subset of primes dividing odd Fibonacci numbers. It is easy to see that it is a proper subset. The smallest prime that divides an odd Fibonacci and doesn’t divide any Lucas number is 5.

The next natural question to ask: is there a prime number that divides an odd Fibonacci, doesn’t divide an odd Lucas number, but divides an even Lucas number? Below I show that such a prime doesn’t exist. In other words, that the set of prime factors of odd Lucas numbers is the intersection of the set of prime factors of odd Fibonacci numbers with the set of prime factors of all Lucas numbers.

Let us consider a Fibonacci-like sequence a_n in a sense that a_n = a_n-1 + a_n-2 for n > 1. Let me denote by b_n, the sequence that is a_n modulo a prime number p. The sequence b_n has to be periodic. It could happen that b_n is never 0. For example, Lucas numbers are never divisible by 5. Suppose the sequence b_n contains a zero. Let us denote r(p) the difference between the indices of two neighboring zeroes in b_n. We can prove that r(p) is well-defined, meaning that is doesn’t depend on where you choose your neighboring zeroes. Moreover r(p) doesn’t depend on the sequence you start with (see 9 Divides no Odd Fibonacci for the proof). The number r(p) is called the rank of apparition of the prime p.

As the Fibonacci sequence starts with a zero, then the terms divisible by a prime p are exactly the terms with indices that are multiples of the corresponding rank of apparition. The Lucas sequence doesn’t start with a zero, but we know that L_-n = (-1)ⁿL_n. That means, if a Lucas number is ever divisible by a prime p, then the smallest positive index for such a number has to be r(p)/2. Also, the indices of the Lucas numbers divisible by p will be odd multiples of r(p)/2.

We know that the indices of even Fibonacci or Lucas numbers are multiples of 3. Hence, a prime number p that divides an odd Fibonacci number must have a rank of apparition that is not divisible by 3, That means that if p ever divides a Lucas number, then it divides a Lucas number with an index of r(p)/2, which is not divisible by 3, meaning that p divides an odd Lucas number. QED.