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.

Many years ago I conducted an experiment. I asked several sets of friends who had written joint math papers what they thought their individual contributions were. I asked them separately, of course. As the result of this experiment I formulated the conjecture:

The total of what joint authors estimate their contributions to be is always more than 100%.

Here is an actual example of answers I received from the two authors of a joint paper.

Author 1: My contribution is 80%. I suggested a breakthrough idea that made this paper possible. He just typed everything.

Author 2: My contribution is 80%. I did all the work. She just suggested a good idea.

You can see how the answers are synchronized. It is clear that both are telling the truth. People just tend to over-value their own input.

In other cases each author thinks that she or he generated the main idea. It doesn’t mean that one of them is lying. Very often they are absolutely sincere. Take this example of Alice and Bob, who are working on a paper together. Alice suggests that they might have better progress on their theorem if they consider graphs with symmetries first. Bob is engrossed in his thoughts and doesn’t register Alice’s suggestion. Next day, he comes up with an idea to add a group action on graphs. He sincerely believes that this was his own idea. It would be hard to know whether this had been provoked by Alice’s suggestion, or had come to Bob independently. Alice assumes that they are working on her idea.

When you acknowledge other people’s contribution, keep in mind that their perception might be different from yours. If you do not want to hurt other people’s feelings, you might consider inflating your gratitude.

The conjecture doesn’t apply to single-author papers. First of all, mathematicians never claim their contribution is 110% as non-mathematicians do. In many cases, especially when there are acknowledgements in the paper, it would be illogical to claim 100% contribution. Most mathematicians are logical, so if they are gracious enough to acknowledge the help of others, they are unlikely to claim 100%.

I would be curious to continue the experiment and either prove or disprove my conjecture. I’d appreciate your help. If you want to be part of this experiment, you can provide the following numbers in your comments: your average contribution to your own papers; and also your weighted average contribution to your joint papers.

I always thought that the famous equation

10² + 11² + 12² = 13² + 14²

is sort of a miracle, a random fluke. I enjoyed this cute equation, but never really thought about it seriously. Recently, when my son Sergei came home from MOP, he told me that this equation is not a fluke; and I started thinking.

Suppose we want to find five consecutive integers such that the sum of the squares of the first three is equal to the sum of the squares of the last two. Let us denote the middle number by n, which gives us the equation:

(n–2)² + (n–1)² + n² = (n+1)² + (n+2)².

After simplification we get a quadratic equation: n² – 12n = 0, which has two roots, 0 and 12. Plugging n = 0 into the equation above gives us (–2)² + (–1)² + 0² = 1² + 2², which doesn’t look like a miracle at all, but rather like a trivial identity. If we replace n with 12, we get the original miracle equation.

If you looked at how the simplifications were done, you might realize that this would work not only with five integers, but with any odd number of consecutive integers. Suppose we want to find 2k+1 consecutive integers, such that the sum of the squares of the first k+1 is equal to the sum of the squares of the last k. Let us denote the middle number by n. Then finding those integers is equivalent to solving the equation: n² = 2k(k+1)n. This provides us with two solutions: the trivial solution 0, and the non-trivial solution n = 2k(k+1).

So our miracle equation becomes a part of the series. The preceding equation is the well-known Pythagorean triple: 3² + 4² = 5². The next equation is 21² + 22² + 23² +24² = 25² + 26² + 27². The middle numbers in the series are triangular numbers multiplied by four.

Actually, do you know that 10² + 11² + 12² = 13² + 14² = 365, the number of days in a year? Perhaps there are miracles or random flukes after all.

Robert Calderbank and Ingrid Daubechies jointly taught a course called “The Theory of Games” at Princeton University in the spring. When I heard about it I envied the students of Princeton — what a team to learn from!

Here is a glimpse of this course — a problem on Evolutionarily Stable Strategy from their midterm exam with a poem written by Ingrid:

On an island far far away, with wonderful beaches
Lived a star-bellied people of Seuss-imagin’d Sneetches.

Others liked it there too — they loved the beachy smell,
From their boats they would yell “Can we live here as well?”
But it wasn’t to be — steadfast was the “No” to the Snootches:
For their name could and would rhyme only with booches …

Until with some Lorxes they came!
These now also enter’d the game;
A momentous change this wrought
As they found, after deep thought.

Can YOU tell me now
How oh yes, how?
In what groupings or factions
Or gaggles and fractions
They all settled down?

Sneetches and Snootches only:

Sneetches and Snootches and Lorxes:

Find all the ESSes, in both cases.

To get to the national swimming championship, you need to win the state running championships.

What? Is that a joke? Perhaps you’re having the same reaction. Because this is exactly what is happening with math competitions. The official USA math competition has three rounds: AMC, AIME and USAMO.

AMC is a multiple-choice competition with 25 problems in 75 minutes. To be good at it, you need speed, accuracy and the ability to guess well.

AIME is 3 hours long and has 15 problems. The problems are a different level of difficulty and guessing will not help you. Though AIME is also multiple-choice, unlike AMC where you choose out of 5, in AIME you choose out of 1,000. But you still need speed and accuracy. A small arithmetic mistake will cost you the whole problem.

USAMO is a competition that runs for 9 hours and has 6 problems. The problems are much harder and you have to write proofs. Proofs? What proofs? Where are the proofs coming from? It is like you got to the national swimming championship because you are a great runner, but you do not know how to swim.

As the result of this system of selection, the USA team at the International Math Olympiad has diverse skills: these kids are good at all three types of the math competitions. It is like taking an Olympic triathlon team to the Olympic swimming event.

However, the US loses by selecting in this way. There are many kids who are great mathematicians: they may be good at difficult problems but not that good at speed-racing problems. An arithmetic mistake costs you only one point at IMO, but a whole problem at AIME. There are kids who are deep mathematicians prone to small arithmetic mistakes. They could get a gold medal at IMO, but they can’t pass AMC or AIME.

Not only that. As many AMC problems are boring and do not require ideas, AMC might discourage kids from all math competitions at an early stage.

I will write later with my ideas about how to change AMC. Right now I would like to offer a solution to a smaller problem. I am sure that the US math team organizers know many cases in which a non-senior kid does great at USAMO and is potentially a team member for the next year’s US IMO team, but, oops, next year he can’t pass AMC.

I suggest the following: USAMO participants are allowed to go to next year’s AIME no matter what their AMC scores are. USAMO winners are allowed to go to the next year’s USAMO no matter what their AIME results are. This way kids who have proved that they are great swimmers do not need to compete in running again.

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.

I ran an experiment. I copied multiple choices from the 2007 AMC 8 into a file and asked my son Sergei to try to guess the answers, looking only at the choices. I allowed him to keep several choices. The score I assigned depended on the number of leftover choices. If the leftover choices didn’t contain the right answer, the score for the problem was zero. Otherwise, it was scaled according to the number of choices he left. For example, if he had four choices left and the right answer was among them he got 1/4 of a point. Here are the choices:

1. 9, 10, 11, 12, 13.
2. 2/5, 1/2, 5/4, 5/3, 5/2.
3. 2, 5, 7, 10, 12.
4. 12, 15, 18, 30, 36.
5. 24, 25, 26, 27, 28.
6. 7, 17, 34, 41, 80.
7. 25, 26, 29, 33, 36.
8. 3, 4.5, 6, 9, 18.
9. 1, 2, 3, 4, cannot be determined.
10. 13, 20, 24, 28, 30.
11. Choose picture: I, II, III, IV, cannot be determined.
12. 1:1, 6:5, 3:2, 2:1, 3:1.
13. 503, 1006, 1504, 1507, 1510.
14. 5, 8, 13, 14, 18.
15. a+c < b, ab < c, a+b < c, ac < b, b/c = a.
16. Choose picture: 1, 2, 3, 4, 5.
17. 25, 35, 40, 45, 50.
18. 2, 5, 6, 8, 10.
19. 2, 64, 79, 96, 131.
20. 48, 50, 53, 54, 60.
21. 2/7, 3/8, 1/2, 4/7, 5/8.
22. 2, 4.5, 5, 6.2, 7.
23. 4, 6, 8, 10, 12.
24. 1/4, 1/3, 1/2, 2/3, 3/4.
25. 17/36, 35/72, 1/2, 37/72, 19/36.

It is clear that if you keep all choices, your score will be 5, which is the expected score for AMC if you are randomly guessing the answers. Sergei’s total score was 7.77, which is noticeably better than the expected 5.

There were two questions where Sergei felt that he knew the answer exactly. First was question number two with choices: 2/5, 1/2, 5/4, 5/3, 5/2. All but one of the choices has a 5 in it, so 1/2 must be wrong. Numbers 2/5 and 5/2 are inverses of each other, so if organizers expect you to make a mistake by inverting the right answer, then one of these choices must be the right answer. But 5/4 and 5/3 are better suited as a miscalculation of 5/2, than of 2/5. His choice was 5/2, and it was correct. The second question for which he was sure of the answer was question 19, with his answer 79. I still do not have a clue why.

Sergei’s result wasn’t too much better than just guessing. That means that AMC 8 organizers do a reasonably good job of hiding the real answer. You can try it at home and see if you can improve on Sergei’s result. I will publish the right answers as a comment to this essay in a week or so.

My knowledge about vampires comes mostly from the two TV series Buffy The Vampire Slayer and Angel. If you saw these series you would know that vampires can’t stand the sun. Therefore, they can’t get any tan at all and should be very pale. Angel doesn’t look pale but I never saw him going to a tanning spa. Nor did I ever see him taking vitamin D, as he should if he’s avoiding the sun.

But this is not why I’m confused about vampires. My biggest concerns are about vampires that are numbers.

Vampire numbers were invented by Clifford A. Pickover, who said:

If we are to believe best-selling novelist Anne Rice, vampires resemble humans in many respects, but live secret lives hidden among the rest of us mortals. Consider a numerical metaphor for vampires. I call numbers like 2187 vampire numbers because they’re formed when two progenitor numbers 27 and 81 are multiplied together (27 * 81 = 2187). Note that the vampire, 2187, contains the same digits as both parents, except that these digits are subtly hidden, scrambled in some fashion.

Some people call the parents of a vampire number fangs. Why would anyone call their parents fangs? I guess some parents are good at blood sucking and because they have all the power, they make the lives of their children a misery. So which name shall we use: parents or fangs?

Why should parents have the same number of digits? Maybe it’s a gesture of gender equality. But there is no mathematical reason to be politically correct, that is, for parents to have the same number of digits. For example, 126 is 61 times 2 and thus is the product of two numbers made from its digits. Pickover calls 126 a pseudovampire. So a pseudovampire with asymmetrical fangs, is a disfigured vampire, one whose fangs have a different number of digits. Have you ever seen fangs with digits?

In the first book where vampires appeared Keys to Infinity the vampire numbers are called true vampire numbers as opposed to pseudovampire numbers.

We can add a zero at the end of a pseudovampire to get another pseudovampire, a trivial if obvious observation. To keep the parents equal, we can add two zeroes at the end of a vampire to get another vampire. Adding zeroes is not a very intellectual operation, but a vampire that can’t be created by adding zeroes to another vampire is more basic and, thus, more interesting. In the book Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning a vampire where one of the multiplicands doesn’t have trailing zeroes is called a true vampire, as opposed to just a vampire. Thus, the trueness of vampires changes from book to book, adding some more confusion. It looks like the second definition of a true vampire is more widely adopted, so I will stick to it.

By analogy, we should call pseudovampires that do not end in zeroes, true pseudovampires. It’s interesting to note that by adding zeroes we can get a true vampire from any pseudovampire that is not a vampire. You see how easy it is to build equality? Just add zeroes.

A true vampire might not be true as a pseudovampire. For example, a vampire number 1260 = 20 * 61 is generated by adding a zero to a pseudovampire 126 = 2 * 61. In this case, the pseudovampire is truer than the vampire. Why does something more basic get a prefix “pseudo”?

Here’s another question. Why do vampires have to have two fangs? Can a vampire have three fangs? For example, 11439 = 9 * 31 * 41. This generalization of vampires should be called mutant vampires. Or multi-gender vampires.

To create more confusion, a mutant vampire can, at the same time, be a simple vampire: 1395 = 31 * 9 * 5 = 15 * 93.

Of course, nothing prevents a mutant vampire from being politically correct, that is, to have multiple and equal parents with the same number of digits, as in 197925 = 29 * 75 * 91.

People continue creating a mess with vampires. For example, a definition of a prime vampire number is floating around the Internet. When you look at this name, your first reaction is that a prime vampire is a prime number. But a vampire is never prime as it is always a product of numbers. By definition a prime vampire is a vampire with prime multiplicands, for example 124483 = 281 * 443. So “prime vampire number” is a very bad name. We should call these vampires prime-fanged vampires — this would be much more straightforward.

To eliminate some of this confusion, we mathematicians should go back and rename vampires consistently. But in the meantime, check out the illustration of vampire numbers shown above that I found at flickr.com with this description:

Like the count von Count in Sesame Street, there is a tradition that vampires suffer terribly from arithromania: the compulsion to count things. To keep vampires from wreaking murderous havoc at night, poppy seeds were strewn about their resting places. On waking, the vampire would be compelled to count the seeds. It would take him all night, and keep him from mischief.

My knowledge about vampires comes mostly from the two TV series Buffy The Vampire Slayer and Angel . If you saw these series you would know that vampires can’t stand the sun. Therefore, they can’t get any tan at all and should be very pale. Angel doesn’t look pale but I never saw him going to a tanning spa. Nor did I ever see him taking vitamin D, as he should if he’s avoiding the sun.

But this is not why I’m confused about vampires. My biggest concerns are about vampires that are numbers.

Vampire numbers were invented by Clifford A. Pickover, who said:

If we are to believe best-selling novelist Anne Rice , vampires resemble humans in many respects, but live secret lives hidden among the rest of us mortals. Consider a numerical metaphor for vampires. I call numbers like 2187 vampire numbers because they’re formed when two progenitor numbers 27 and 81 are multiplied together (27 * 81 = 2187). Note that the vampire, 2187, contains the same digits as both parents, except that these digits are subtly hidden, scrambled in some fashion.

Some people call the parents of a vampire number fangs. Why would anyone call their parents fangs? I guess some parents are good at blood sucking and because they have all the power, they make the lives of their children a misery. So which name shall we use: parents or fangs?

Why should parents have the same number of digits? Maybe it’s a gesture of gender equality. But there is no mathematical reason to be politically correct, that is, for parents to have the same number of digits. For example, 126 is 61 times 2 and thus is the product of two numbers made from its digits. Pickover calls 126 a pseudovampire. So a pseudovampire with asymmetrical fangs, is a disfigured vampire, one whose fangs have a different number of digits. Have you ever seen fangs with digits?

In the first book where vampires appeared Keys to Infinity the vampire numbers are called true vampire numbers as opposed to pseudovampire numbers.

We can add a zero at the end of a pseudovampire to get another pseudovampire, a trivial if obvious observation. To keep the parents equal, we can add two zeroes at the end of a vampire to get another vampire. Adding zeroes is not a very intellectual operation, but a vampire that can’t be created by adding zeroes to another vampire is more basic and, thus, more interesting. In the book Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning a vampire where one of the multiplicands doesn’t have trailing zeroes is called a true vampire, as opposed to just a vampire. Thus, the trueness of vampires changes from book to book, adding some more confusion. It looks like the second definition of a true vampire is more widely adopted, so I will stick to it.

By analogy, we should call pseudovampires that do not end in zeroes, true pseudovampires. It’s interesting to note that by adding zeroes we can get a true vampire from any pseudovampire that is not a vampire. You see how easy it is to build equality? Just add zeroes.

A true vampire might not be true as a pseudovampire. For example, a vampire number 1260 = 20 * 61 is generated by adding a zero to a pseudovampire 126 = 2 * 61. In this case, the pseudovampire is truer than the vampire. Why does something more basic get a prefix “pseudo”?

Here’s another question. Why do vampires have to have two fangs? Can a vampire have three fangs? For example, 11439 = 9 * 31 * 41. This generalization of vampires should be called mutant vampires. Or multi-gender vampires.

To create more confusion, a mutant vampire can, at the same time, be a simple vampire: 1395 = 31 * 9 * 5 = 15 * 93.

Of course, nothing prevents a mutant vampire from being politically correct, that is, to have multiple and equal parents with the same number of digits, as in 197925 = 29 * 75 * 91.

People continue creating a mess with vampires. For example, a definition of a prime vampire number is floating around the Internet. When you look at this name, your first reaction is that a prime vampire is a prime number. But a vampire is never prime as it is always a product of numbers. By definition a prime vampire is a vampire with prime multiplicands, for example 124483 = 281 * 443. So “prime vampire number” is a very bad name. We should call these vampires prime-fanged vampires — this would be much more straightforward.

To eliminate some of this confusion, we mathematicians should go back and rename vampires consistently. But in the meantime, check out the illustration of vampire numbers shown above that I found at flickr.com with this description:

Like the count von Count in Sesame Street, there is a tradition that vampires suffer terribly from arithromania: the compulsion to count things. To keep vampires from wreaking murderous havoc at night, poppy seeds were strewn about their resting places. On waking, the vampire would be compelled to count the seeds. It would take him all night, and keep him from mischief.

This puzzle is a generalization of a problem from the 1977 USSR math Olympiad:

At the beginning of the game you are given a polynomial, which has 1 as its leading coefficient and 1 as its constant term. Two people play. On your turn you assign a real value to one of the unknown coefficients. The person that goes last wins if the polynomial has no real roots at the end. Who wins?

It is clear that if the last person’s goal is for the polynomial to have a root, then the game is trivial: in this case, he can always make 1 a root with the last move. Also, an odd degree polynomial always has a real root. Therefore, to make the game interesting we should assume that the degree of the polynomial is even.

Though I can’t imaging myself ever being interested in playing this game, figuring out the strategy is a lot of fun.

Once I witnessed John H. Conway factoring large numbers in his head. Impressed, I stared at him. Encouraged by my interest, he told me that if I ever want to be able to factor large numbers, I should know all the primes below one thousand.

The secret to knowing all such primes is to remember the composites, he continued. Obviously, we don’t need to remember trivial composites — the ones divisible by 2, 3, 5, or 11. Also, everyone knows all the squares below one thousand, so we can count squares as trivial composites. We only need to remember the non-trivial composites. There are not that many of them below one thousand — only 70. I mean, 70 is nothing compared to the number of primes: 168.

So, I need to remember the following seventy numbers:

91, 119, 133, 161, 203, 217, 221, 247, 259, 287, 299, 301, 323, 329, 343, 371, 377, 391, 403, 413, 427, 437, 469, 481, 493, 497, 511, 527, 533, 551, 553, 559, 581, 589, 611, 623, 629, 637, 667, 679, 689, 697, 703, 707, 713, 721, 731, 749, 763, 767, 779, 791, 793, 799, 817, 833, 851, 871, 889, 893, 899, 901, 917, 923, 931, 943, 949, 959, 973, 989.

If you are very ambitious and plan to learn the primes up to 50,000, then the trick of learning non-trivial composites instead of primes is of no use to you. Indeed, for larger numbers the density of primes goes down, while the density of non-trivial composites stays about the same or increases very slightly due to a smaller number of squares.

The turning point is around 11,625: the number of primes below 11,625 equals the number of non-trivial composites below it. So, compare your ambition to 11,625 and tailor your path of learning accordingly.

If you are lazy, you can learn primes only up to 100. In this case your path is clear; you should stick with remembering non-trivial composites, for you need to remember only one number: 91.