Tanya Khovanova's Math Blog

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.

My son Alexey taught me to play “The Settlers of Catan .” This game is so good that throughout the four years of his undergraduate studies, he played it every evening. I am exaggerating of course, but only so slightly. He also taught me some of the game’s wisdom.

Lesson 1. Trading is beneficial for both traders.

When you agree to exchange your two rocks for one grain, one grain is more valuable to you than two rocks. The opposite is true for your trading partner.

Presumably, the same principle works for the economy. If I buy a sweater at T.J.Maxx for $20, I need the sweater more than $20. And if the store sells this sweater for $20, they are hoping to make some profit, that is, that the sweater cost them less than $20. Supposedly, shopping transactions are profitable for both parties.

Lesson 2. Trading is bad for non-trading players.

This is the consequence of the fact that in “Settlers of Catan” there is only one winner. If something is good for someone, it is bad for everyone else. In real life you do not have to lose if someone wins. With each shopping transaction everyone gains. This is the reason why shopping must be good for the economy.

Lesson 3. Powerful players can persuade other players to trade against their best interests.

Shortly after I moved to the US, I became very aware of my own smell. My smell didn’t change with my move from Russia, nor did my sense of smell change. I was just bombarded with deodorant advertisements, and due to the vulnerability of my self-perception, in one year I bought more deodorants than in all my previous 30 years. I have a friend who has an exceptional sense of smell. He told me that people often use much more deodorant and perfume than they need.

Lesson 4. You pay a lot for storage.

In Settlers, if you have more than seven cards and the dice rolls seven, you need to discard half of your hand. So if you have six cards and someone offers you three grains for one sheep, consider the storage price before jumping into this bargain deal.

Once I bought so much discounted toilet paper that it lasted me for months and months. When it was time to move to a different apartment, I had to pay for the largest truck available to fit all my junk.

Lesson 5. It is important to understand the goal of the person you are trading with.

A profitable deal becomes a big mistake when, as a result of the trade, your trading partner builds a settlement right in the spot where you were planning to build.

Similarly, if your doctor prescribes you a medication, it would behoove you to know whether he will reap any profit from it himself.

Lesson 6. If a player is the only receiver of rock in the game he dictates the price.

This is like a monopoly. I needed my last laptop more than the $1,000 I paid for it. But this price included pre-installed Windows, which I didn’t want and which I immediately deleted. I was forced to pay extra for Windows because of Microsoft’s monopoly.

So, is shopping good for the economy?

What about that skirt I bought and never used and eventually threw away? I wasted $20 on it. But the store didn’t gain that $20; they only gained their profit margin, which could have been $5. That means that together we wasted $15.

I do not throw away every piece of clothing I buy, but it is true that we buy more things than we need.

I think that going shopping to help our country get out of an economic crisis is a ridiculous idea. If you are shopping for other reasons than necessity, you do not help anyone and as a group we lose.

My son Alexey wins almost every game of “Settlers of Catan” he plays. So does my friend Mark Shiffer. The main reason is that they both know how to use trading effectively. To me that indicates that there are probably other people out there who know how to effectively sell deodorants, pills, clothing and other junk to us. I suspect that I lose in every shopping transaction, as I am an unskilled trader. If most folks are like me, could it be that shopping is actually bad for the economy?

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.