Tanya Khovanova's Math Blog

Here is a palindrome problem by Nazar Agakhanov from the All-Russian Mathematical Olympiad, 1996:

Can the number obtained by writing the numbers from 1 to n, one after another, be a palindrome?

Of course, we should assume that n > 1.

When I give this problem to my friends, they immediately answer, “No, of course not.” The reasoning is simple. The last 9 digits of this palindrome should be 987654321 — all different digits. The earliest you can get these digits at the end of your string 1 to n, is when your number n is actually 987654321. By that time your string of digits is really huge. If we take a random number with 2k digits, then the probability of it being a palindrome is 10^(-k). There is no reason to think that writing consecutive integers increases the probability of finding a palindrome. So the probability of hitting a palindrome is so low, that you can safely answer, “No, of course not.”

After confidently saying “no”, my friends usually stop thinking about the problem altogether. Only my friend David Bernstein suggested a simple solution for this problem. You can try to find the proof, but I do not insist that you do. I am about to give you many other fun problems to solve, and you can choose which ones you want to think about.

Naturally, we can replace the sequence of natural numbers in the Agakhanov’s problem with any sequence. So, one problem becomes 160,000 different problems when you plug all current sequences from the Online Encyclopedia of Integer Sequences into it.

For some periodic sequences every concatenation you create is a palindrome. For example, for the sequence of all zeroes, every set of the first n terms is a palindrome. More interestingly, you can think of an increasing sequence such that any first n terms comprise a palindrome, as we see in the sequence of repunits: 1, 11, 111, 1111, etc. Can you think of other sequences like this?

For some sequences, not every concatenation you create is a palindrome, but you can obtain an infinite number of palindromes. One example, suggested by Sergei Bernstein, is the sequence a(n) of the last digit of the greatest power of 2 that divides n. Can you think of other sequences like that?

For some sequences only the initial term itself is a palindrome. Beyond that you can’t obtain a palindrome by concatenating the first n terms. For a few of those sequences, this fact is easy to prove. Take, for example, the sequence of powers of ten, or the sequence of squares, or the sequence of prime numbers. Can you think of other similar sequences?

There are many sequences that do not produce a palindrome beyond the first term, even if you try many times. I suspect that they do not, in fact, ever produce a palindrome, but I have no clue how to prove that. I have in mind the sequence of the digits of π. Can you suggest other sequences like that?

Instead of solving the initial problem, I gave you a variety of other problems. My last challenge for you is to find other sequences that can replace the sequence of natural numbers in the Agakhanov’s problem so that the problem becomes solvable and the solution is interesting.

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.