Tanya Khovanova's Math Blog

The PhD program in Russia was limited to exactly three years. My son Alexey was born right after I started it, and I was distracted from my research for quite some time. At that time, my mom, who lived with us, reached her retirement age of 55. Her retirement would have been supported by the government and her pension would have been almost equal to her salary. So I begged my mom to retire and help me with my son Alexey. I couldn’t understand why she wouldn’t stop working, so I kept pressing.

At the same time, I was frantically trying to find a place for Alexey in a day care center. I finally was successful, but it backfired. Alexey started getting sick all the time. Daycare was overcrowded, with 30 kids to every adult. Workers didn’t have time to attend to every kid. Day care workers were so tired that they were relieved when a few kids stayed home sick.

After Alexey was hospitalized for two weeks with severe dysentery, my mother gave up and retired. It was one year before the end of my graduate school. In that year I wrote four papers and my thesis, and I got my PhD.

Now that I am fifty, I understand that my mother really did love her job. Being older and wiser, I recognize what a sacrifice my mother made in retiring in order to look after a grandchild.

Mom, sorry for being so pushy back then and thank you so much for all that you did for us.

This puzzle was brought to me by Leonid Grinberg.

A frog needs to jump across the street. The time is discrete, and at each successive moment the frog considers whether to jump or not. Unfortunately, the frog has crappy eyesight. He knows there are dangerous cars out there, but he can’t see them. If a car appears at the same moment that he decides to jump, he will die.

The adversary sends cars, hoping to kill the frog. The adversary knows the frog’s algorithm, but can use only a finite number of cars. The frog wants to maximize his chances of survival with his algorithm. The frog is allowed to use a random number generator that the adversary can’t predict. Can you suggest an algorithm for the frog to cross the street and survive with a probability of at least 1 − ε?

My guest blogger is Levy Ulanovsky, a maven of physics puzzles. Here is one of his favorite puzzles:

There are n points in 3-dimensional space. Every point is connected to every other point by a wire of resistance R. What is the resistance between any two of these points?

In 2007 Alexander Shapovalov suggested a very interesting coin problem. Here is the kindergarten version:

You present 100 identical coins to a judge, who knows that among them are either one or two fake coins. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

You yourself know that there are exactly two fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly two fake coins without revealing any information about any particular coin?

To solve this problem, divide the coins into two piles of 50 so that each pile contains exactly one fake coin. Put the piles in the different cups of the scale. The scale will balance, which means that you can’t have the total of exactly one fake coin. Moreover, this proves that each group contains exactly one fake coin. But for any particular coin, the judge won’t have a clue whether it is real or fake.

The puzzle is solved, and though you do not reveal any information about a particular coin, you still give out some information. I would like to introduce the notion of a revealing coefficient. The revealing coefficient is a portion of information you reveal, in addition to proving that there are exactly two fake coins. Before you weighed them all, any two coins out of 100 could have been the two fakes, so the number of equally probable possibilities was 100 choose 2, which is 5050 4950. After you’ve weighed them, it became clear that there was one fake in each pile, so the number of possibilities was reduced to 2500. The revealing coefficient shows the portion by which your possibilities have been reduced. In our case, it is (5050 − 2500)/5050 (4950-2500)/4950, slightly more less than one half.

Now that I’ve explained the kindergarten version, it’s time for you to try the elementary version. This problem is the same as above, except that this time you have 99 coins, instead of 100.

Hopefully you’ve finished that warm-up problem and we can move on to the original Shapovalov’s problem, which was designed for high schoolers.

A judge is presented with 100 coins that look the same, knowing that there are two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

You yourself know that there are exactly three fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly three fake coins, without revealing any information about any particular coin?

If you are lazy and do not want to solve this problem, but not too lazy to learn Russian, you can find several solutions to this problem in Russian in an essay by Konstantin Knop.

Your challenge is to solve the original Shapovalov puzzle, and for each solution to calculate the revealing coefficient. The best solution will be the one with the smallest revealing coefficient.

My guest blogger is David Wilson, a fellow fan of sequences. It is a nice exercise to understand how this graph works. When you do, you will discover that you can use this graph to calculate the remainders of numbers modulo 7. Back to David Wilson:

I have attached a picture of a graph.

Write down a number n. Start at the small white node at the bottom of the graph. For each digit d in n, follow d black arrows in a succession, and as you move from one digit to the next, follow 1 white arrow.

For example, if n = 325, follow 3 black arrows, then 1 white arrow, then 2 black arrows, then 1 white arrow, and finally 5 black arrows.

If you end up back at the white node, n is divisible by 7.

Nothing earth-shattering, but I was pleased that the graph was planar.

My son Alexey Radul defended his PhD thesis on Propagation Networks on August 4. Here is the abstract.

I propose a shift in the foundations of computation. Modern programming systems are not expressive enough. The traditional image of a single computer that has global effects on a large memory is too restrictive. The propagation paradigm replaces this with computing by networks of local, independent, stateless machines interconnected with stateful storage cells. It offers great flexibility and expressive power, and has therefore been much studied, but has not yet been tamed for general-purpose computation. The novel insight that should finally permit computing with general-purpose propagation is that a cell should not be seen as storing a value, but as accumulating information about a value.

Various forms of the general idea of propagation have been used with great success for various special purposes; perhaps the most immediate example is constraint propagation in constraint satisfaction systems. This success is evidence both that traditional linear computation is not expressive enough, and that propagation is more expressive. These special-purpose systems, however, are all complex and all different, and neither compose well, nor interoperate well, nor generalize well. A foundational layer is missing.

I present the design of a general-purpose propagation system. I illustrate on several examples how the resulting prototype supports arbitrary computation; recovers the expressivity benefits that have been derived from special-purpose propagation systems in a single general-purpose framework, allowing them to compose and interoperate; and offers further expressive power beyond what we have known in the past.

Warning: this essay contains solutions to math problems.

Here is a famous hat puzzle:

A king decides to give 100 of his wise men a test. If together they pass, they can go free. Otherwise, the king will execute all of them. The test goes as follows: the wise men stand in a line one after another, all facing in the same direction. The king puts either a black or a white hat on each wise man. The wise men can only see the colors of the hats in front of them. In any order they want, each one guesses the color of the hat on his own head. Other than that, the wise men cannot speak. To pass, no more than one of them may guess incorrectly. Given that they have time to agree on a strategy beforehand, how can they assure that they will survive?

Instead of discussing the puzzle above, I’d like to look at a different version. It is an infinite variation of the puzzle that my son Sergei brought back from the Canada/USA Mathcamp last year.

The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake?

Oh, I forgot to mention: you are allowed to use the axiom of choice.

Here is the solution. You can build an equivalence relation on the possible placements of hats. To be equivalent, two ways of placing the hats should have the same tail. In other words, there is a person such that both hat arrangements to his right are the same. By the axiom of choice you can pick a representative in any equivalence class. The first wise man looks at all the other hats and calculates in how many places the tail differs from the representative of the class they picked. This is a finite number, and by stating one color or the other, he signals the parity of that number. After that, all the wise men say their colors from left to right. Everyone sees the tail and everyone hears the color choices of the people behind. So every wise man can reconstruct the color of his hat with this information. Only the first person may potentially be mistaken.

Many things about this solution bother me. Where is this country that can fit an infinite number of people? What kind of humans can see into infinity? How much time will this procedure take?

Aside from the practical matters, there are mathematical matters that bother me, too. By the axiom of choice you can pick an element in every class. The problem is that all of the wise men have to pick the same element. The axiom of choice claims the existence of a choice function, which picks an element in each set. So the function exists, but can we distribute this function to many wise men? Remember, they need to agree on this function the night before.

We already implicitly assumed that our wise men have a lot of magical abilities. So we can add to those the ability to go through all the possible tails and memorize the representatives for all the tails in one evening.

But still, I am very curious to know what follows from the axiom of choice. Tell me what you think: does the axiom of choice imply that we can distribute the choice function, or do we need a new axiom? In your opinion, will these wise men live?

I do not know why I like the television show America’s Got Talent. Sometimes I picture myself on a stage doing what I love to do the most: entertaining people with mathematics. But it wouldn’t really work on the stage of America’s Got Talent. The audience makes its judgment in the first five seconds of a performance. There is no way I can teach a new math idea in five seconds.

Back to the show. I especially like the auditions. I noticed a strange correlation between what people say before their performance and what happens on the stage. In short, if a person brags that he/she has the greatest talent and that the judges will be blown away, the performance is likely to be pathetic.

My first thought was that the producers were editing it this way in order to boost the drama of the show. Now I wonder if it could be something else. Perhaps people who do not have much talent need to build up their confidence to appear on the show. And, vice versa, people who have talent can afford to be modest.

I didn’t see the same correlation when I watched Britain’s Got Talent. Could this tendency be a part of our American culture? After all, the message that confidence is all we need to succeed permeates the whole culture.

A pre-stage interview with one of the contestants on the show was especially telling. She said, “I could be the next greatest act in America, because I have the courage, the self-esteem, the confidence, the faith and hope and belief in myself.” Talent wasn’t mentioned at all.

Yesterday I had a nightmare. I was on the stage of America’s Got Talent and Piers Morgan, my favorite judge, was questioning me:

Piers: Do you have a talent people will pay for?
Me: Yes, I do.
Piers: What is it?
Me: I sing so badly people will pay me to stop.

Do you know that numbers have destinies? Well, to have a destiny, a number needs to have a life, or in mathematical terms, destinies are defined with respect to an operation or a function.

I know the term “destiny” from John Conway, the creator of the Game of Life. It would be harmonious to assume that he suggested this term.

Case 1. SOD. Suppose our function is the sum of digits of a number, denoted as SOD. Then the trajectory of a number k is the sequence a(n), such that a(0) = k and a(n+1) = SOD(a(n)).

Two numbers have the same destiny with respect to SOD if the tails of their trajectories coincide. Suppose a(n) and b(n) are two trajectories. Then the numbers a(0) and b(0) on which these trajectories are build have the same destiny if there exist N and M, such that for any j, a(N+j) = b(M+j). In particular, all numbers in the same trajectory a(n) have the same destiny.

In the above example of SOD, any trajectory of a positive integer ends with a one-digit non-zero number repeating many times. It follows that all the natural numbers have 9 different destinies with respect to SOD, which only depend on the remainder of the number modulo 9.

Given an operation, we can build another sequence that is called “the first occurrence of a new destiny”. This is the sequence of numbers c(n) such that c(n) is the smallest number with its destiny. For the SOD operation, the sequence of the first occurrences of new destinies is finite and is equal to: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Case 2. The next prime. Let us consider a different example. Let the function f(n) be the next prime after n. Then wherever we start, the tail of the trajectory with respect to the function f(n) is a sequence of consecutive prime numbers. Therefore, with respect to this function all integers have the same destiny.

Case 3. Reverse. Suppose f(n) is a reverse of n. If a number is a palindrome, then its trajectory is a one-cycle consisting of that number. If a number is not a palindrome, then its trajectory is a two-cycle consisting of a number and its reverse. The first appearance of a new destiny is sequence A131058 — a list of numbers n whose reverse is not less than n. In this case, instead of studying destinies, it might be more interesting to study types of destinies. For this operation we have two types: one-cycles for palindromic integers and two-cycles for non-palindromic integers.

Case 4. The sum of proper divisors. For the next example, let f(n) denote the sum of proper divisors. Let’s look at the trajectory of 15: it is 15, 9, 4, 3, 1, 0. The sum of proper divisors of zero is not-defined or is equal to infinity, whichever you prefer. So, let us say the trajectory of 15 is finite, and ends with 1, 0. This situation makes the definition of destinies more complicated, but it is appropriate to say that finite sequences have the same destinies if they end with the same number. For our example of sums of proper divisors all finite sequences end with 0. Thus all the numbers whose trajectories are finite have the same destinies. The sequence of new destinies starts 1, 6, 28, 220, …; and we do not know what the next number is because for 276 we do not know the behavior of its trajectory. Even when we know what kind of life the number is living the destinies are not always clear.

Case 5. TITO. The next interesting example is the TITO operation. TITO is an abbreviation of “Turning Inside, Turning Outside”. By definition, to calculate TITO(n) you need to reverse the prime factors of n, multiply them back together (with multiplicities) and reverse the result. For example, to calculate TITO(68), we first find prime factors of 68, which are 2, 2 and 17. We reverse them and multiply: 2*2*71 = 284. Then we reverse the result: TITO(68) = 482.

It is easy to see that prime numbers are among the fixed points of the TITO operation. That means all prime numbers have different destinies of the same type: they end with a one-cycle. There are numbers other than prime that have one-cycle destinies. For example, a palindrome that is a product of palindromic primes is a fixed point of the TITO operation. There are other cases too: for example 26 is a fixed point, but is neither prime nor palindromic. There are numbers that have one-cycle destinies, but are not the fixed points of TITO operation themselves. For example, the trajectory of 49 starts with the following sequence: 49, 94, 841, 4648, 8212, 80041, 415003, 282145, 54796, 849667, 3652951, 35429422, 2941879, 27075955, 5275759, 5275759, 5275759. ….

There are numbers that generate two-cycles. For example, 12 and 156. For numbers n that have only palindromic factors, TITO(n) is equal to the reverse of n. If n is not a palindrome and the reverse of n has only palindromic factors, then the trajectory of n is a two-cycle. Not all two-cycles are like that. Take for example 291 which is a product of primes 3 and 97. Thus, TITO(291) is the reverse of 3*79, which is equal to 732. On the other hand, 732 = 2*2*3*61. Hence, TITO(732) = reverse(2*2*3*16) = 291.

There are longer cycles too. Take for example 15, which generates a cycle of length 7: 15, 51, 312, 447, 3282, 744, 213, 15, …. Also, for some numbers we do not know if there is a cycle. The smallest number for which I myself do not know whether the trajectory tends to infinity or collapses into a cycle is 78.

For the TITO operation we might be more interested in types of destinies. Personally, I am interested not only in the types of destinies, but also in sets of numbers that have the same destinies for the same reasons. For example, I am interested in dividing numbers of one-cycle TITO destinies into three groups: primes, palindromes with palindromic primes and other cases.

Case 6. RATS. I kept the RATS operation for dessert as, in my opinion, it is the most interesting operation with respect to destinies. RATS is the abbreviation of Reverse Add Then Sort. For example, to calculate RATS(732) we need to reverse 732 getting 237, then add 732 and 237 together getting 969, then sort the digits. Thus, RATS(732) = 699.

Let’s look at the RATS sequence starting with one: 1, 2, 4, 8, 16, 77, 145, 668, 1345, 6677, 13444, 55778, 133345, 666677, 1333444, 5567777, 12333445, 66666677, 133333444, 556667777, 1233334444, 5566667777, 12333334444, 55666667777, 123333334444, 556666667777, …. We can prove that this sequence is infinite, because numbers fall into a repetitive pattern with an increasing number of digits. This is the first such example in this discussion. John Conway calls the destiny of 1 “the creeper”. Conway conjectured that RATS destinies are either the creeper or a cycle.

New destinies do not appear too often in this sequence. That is why the sequence of new destinies might be of interest: 1, 3, 9, 29, 69, 2079, 3999, 6999, 10677, 20169, …. This sequence is A161590 in the Online Encyclopedia of Integer Sequences and it needs more terms. The length of the corresponding periods starting from the second term are: 8, 2, 18, 2, 2, 2, 14, which is the sequence A161593.

Destinies are kinda fun.

Decades ago there was a study in Russia that claimed that a woman worked four more hours a day than a man on average. Men and women were equal in Russia and all had the same 40-hours-a-week jobs. Women were not, by and large, housewives, for they worked full-time.

So where did the additional four hours come from? They were devoted to house chores. In Russia, women did everything at home — at a time when life in Russia was much more difficult. For example, my family didn’t have a washer, or a dryer or a dish-washing machine. Plus, everything was in deficit, so to buy milk or a sweater, women had to stand in lines, sometimes for hours.

My mother was very bitter because her husband, my father, never helped her. So I always hoped that when I got married, my husband would take on some of the house chores.

When I married Andrey, he was somewhat helpful — better than the average Russian husband. Then, when I was at grad school, we had a baby named Alexey. Andrey convinced me that I had to take over all the child care because only women could get academic maternity leave. It seemed logical and I agreed.

In a year, when the leave was over, I felt that Andrey should take over some of these duties. He refused. He insisted that since I already had published a paper when I was an undergrad, and since he still didn’t have his research results for his PhD, that he had to stay focused on his work. I wasn’t strong enough to resist.

We signed up for government child care — private care didn’t exist — but we were on the waiting list for a couple of years. Almost no one in Russia — certainly not graduate students — could afford a private babysitter. I couldn’t really work on my PhD research because between caring for the house and the baby, I never had big chunks of time. The best I could do was to start preparing for my qualifying exams.

Allow me to digress from my main story for a moment to mention my gray notebook. This notebook was our baby diary. Initially I recorded important baby data — like the first time Alexey smiled. But later, as soon as Alexey turned one year old, he became very eloquent; and this notebook became my son’s quote book.

One day Andrey and I went out and my mom babysat Alexey, who was two years old. When we returned, my mother recited the following quote from Alexey:

When will Daddy be back from the university and Mommy from the store?

I don’t really remember the long hours in stores or the cooking and cleaning. I remember the quote.