Tanya Khovanova’s Math Blog

You have been warned. You are allowed to read this if you are 17 or over. Otherwise, you can ask your parents to read this to you. Here is a famous old condom puzzle in the version I heard when I was a teenager myself:

A man hires three prostitutes and wants to have sex with all three of them. They all might have different sexually transmitted diseases and they all want to use condoms. Unluckily, they have only two condoms. Plus, they are in the forest and can’t buy new condoms. Can the man have sex with all three of the women without danger to any of the four?

Everyone in this problem is so health-conscious, that it might not be such a dirty problem after all. I leave you with the fun challenge of figuring this problem out.

Another fun variation of this problem is when you have two men and two women and two condoms. Every woman wants to have sex with every man. How can they do that?

If you are a teacher and want to use these great puzzles for younger students, you can follow the example of MathWorld and pretend that it’s a glove problem between doctors and patients.

Recently my younger son and his MIT friends invented another variation of this problem:

Suppose three gay men all want to have sex with each other and every pair among them wants to do two penetrative sexual acts, switching roles. They want to avoid contaminating each other, and in addition, each man also does not want to cross-contaminate himself from either region to the other. How can they do that using exactly three condoms?

Let me remind you that they plan to perform six sexual acts altogether, meaning that six condoms would be enough. On the other hand, each of them needs two condom surfaces, so they can’t do it with less than three condoms. My son showed to me his solution, but I will postpone its publication.

Of course, you can say that this is a glove problem about three surgeons operating on each other.

In addition, you can generalize it to any number of gay men. Here is my solution for four men and four condoms, where letters denote people, numbers denote condoms, and the order of people represents roles: A12D, B32D, C2D, A14C, B34C, D4C, A1B, B3A, C21B, D41B, C23A, D43A.

Can you solve the problem for five or more people?

I used to receive emails requesting link exchanges with other websites. They promised to increase my page rank by creating additional hyperlinks to my pages. I ignored them. If they thought my website was good, why did they need my reciprocity to link to me? Besides, their websites didn’t have anything to do with mathematics; they were the sites of dental services or Honda dealers.

I have resisted the temptation so far. The links that I have on my websites are to sites that I recommend. Sometimes I wonder through other people blogrolls and add good links to my blog.

At other times a blog roll exchange happens: I have Google Analytics installed on my sites. From time to time I examine my traffic. When I see a new traffic flow from a particular website, I check that site out. If I like it, I add it to my blogroll.

I wouldn’t mind people writing to inform me that they have a link to my website and asking me if I’d like to reciprocate. But this doesn’t happen. Instead, strangers write to me offering to put up a link to my website on the condition that I put a link to them. I do not like this imposition.

Recently I received a request for a blog review exchange. I went to that blog and found that all of its postings were reviews of other people’s blogs, presumably those who had agreed on this kind of exchange. I checked out several of those other blogs and I didn’t find any of them very interesting.

I missed this opportunity to receive that blog review, but on the other hand, if I start linking to random crap, I might lose the respect of my readers.

My previous paragraph reminded me of a Russian joke:

I wonder how a person whose website comes up first in a Google search for “random crap” feels.

Russians assume that such a person will be embarrassed. They do not understand Americans who welcome negative publicity, and purposefully would name their website randomcraponline.com.

I enjoyed a recent discussion on the sequences fans mailing list. David Wilson suggested an idea for hiding email addresses on webpages from bots: change your email slightly and explain how to change it back.

For example, if you want to contact me, you should reverse my login name in the following email address:

hkaynat@yahoo.com

Or, remove all the digits from the following email address:

1ta2nya3kh4@yahoo.com

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.