Tanya Khovanova's Math Blog

Here is a strange puzzle that was inspired by the palindrome problem. Suppose you have a sequence of words in some alphabet with the initial term a and all the other terms b: a, b, b, b, b, etc. Suppose this sequence generates palindromes every time you concatenate the first several terms, not counting the first term itself. So, ab, abb, abbb, and so on — are all palindromes. We call words b “papaya” words, when a exists, such that a and b generate the sequence with this palindrome property. Can you describe papayas?

Theorem. The word b is a papaya word if and only if b is a substring of Reverse(b)Reverse(b).

Proof. After we have added b so many times that the initial part a is much smaller than half of the concatenated string, the middle part of the concatenated string would consist of several words copies of the word b. The middle of the reverse string consists of several concatenations of Reverse(b). So the word b must be a substring of Reverse(b)Reverse(b). On the other hand, suppose b is a substring of Reverse(b)Reverse(b). Then Reverse(b)Reverse(b) is of the form xby, and we can choose a = y.

Theorem. Papaya words are either palindromes or concatenations of two palindromes.

Proof. Suppose our word consists of two palindromes cd. Then the reverse of it is dc and its double is dcdc. The word cd is a substring of dcdc, thus according to the first theorem, cd is a papaya word. Let’s do the other direction. Suppose the word b is a substring of Reverse(b)Reverse(b). Then Reverse(b)Reverse(b) is of the form xby. Then b = yx, and Reverse(b) = xy, which equals Reverse(x)Reverse(y). From here, Reverse(x) = x and Reverse(y) = y. If x or y has zero length, then our word is a palindrome. QED.

Hey, do you already know why we call these words papayas?

Just for fun we would like to study the structure of papaya words. Any one-character or two-character word is a papaya word, so the patterns are: a, aa, ab. For three-character words there are four patterns: aaa, aab, aba, abb. For four-character words there are 10 patterns: aaaa, aaab, aaba, abaa, aabb, abab, abba, abbb, abac, abcb. In this manner we get the sequence of the number of n-character papaya patterns: 1, 2, 4, 10, 21, 50 etc, which is sequence A165137 in the OEIS. This sequence depends on the number of letters in your alphabet. But the first n terms of these sequences are the same for all alphabets that have at least n letters.

Let us assume that we are working with an infinite alphabet. The complementary sequence would be the number of patterns for non-papaya words. The total number of patterns is described by sequence A000110 — Bell numbers: the number of word structures of length n using an infinite alphabet. So the beginning of this complementary sequence A165610 is: 0, 0, 1, 5, 31, 153, etc. The list of corresponding patterns is abc, aabc, abbc, abcc, abca, abcd, etc.

Historically, we first invented the corresponding sequence for numbers, not for words. We call a number a papaya number if it is a palindrome or a concatenation of two palindromes. If we use numbers instead of words in the problem, we need to carefully look at what happens if we encounter initial zeroes. Let’s take the papaya number 2200100, and see if we can find a number a, such that adding 22010 repeatedly to this sequence starting with a will always generate a palindrome. The number a must be 00100. But this is not a number. We have two choices: to say that we are working with strings of digits, or to allow several numbers to start the sequence before we add b repetitively and before getting to palindromes. In the latter case our sequence can start 0, 0, 100, 22010, 22010, and so on.

As we mentioned before, the number of patterns of papaya numbers will start the same as the number of patterns of papaya words. Later the sequence of patterns of numbers A165136 will be smaller than the corresponding sequence for words. As the sequence of Bell numbers is much more famous than the sequence A164864 of patterns of numbers, we expect the papaya patterns sequence corresponding to the infinite alphabet to be more interesting and important than the sequence of papaya patterns for numbers.

Though papaya numbers might be less important than papaya words with an infinite alphabet, they have an advantage in that we can generate more sequences with them. For example we can calculate the number of positive papaya number with n digits, as in the sequence A165135: 9, 90, 252, 1872, 4464, 29250, etc. And we can also calculate the sequence A165611 of n-digit non-papaya numbers: 0, 0, 648, 7128, 85536 etc.

This geometric problem was given to me by Arkady Berenstein:

There are n points on the plane, but not all of them are on one line. Prove that a line exists that passes through exactly two points of this set.

Arkady gave me a beautiful solution to this problem. First, draw a line through each pair of points. Suppose you calculate all the distances from each point to all the lines that the point doesn’t belong to. Pick the smallest distance. The corresponding line will be the one with two points. To finish the solution you need to fill in the details. That process is usually left to the reader.

I suspect that there might also be a solution using linear algebra. Can you find one?

I would like to reformulate this problem without using geometry. Suppose there is a set of n elements. Let’s call a family of subsets line-like if any two distinct subsets of this family can have as an intersection not more than one element. Then the geometry problem above has a set-theoretical analogue:

You have a set of n elements and a line-like family of subsets of this set such that any two elements of the set belong to a subset from this family, and that the family doesn’t contain the whole set. Is it true that there always exists a subset in this family consisting of two elements?

Usually I give such problems as homework for the reader, but this time I decided to change my habit, so I’m including the picture which contains the solution of this problem by my son Alexey Radul.

Conclusion: geometry is important.

I bought the book “Heard on The Street: Quantitative Questions from Wall Street Job Interviews” by Timothy Falcon Crack several years ago when I was looking for a job and felt that working in finance was a possibility. Despite having bought it simply to prepare for employment interviews, I actually enjoyed the math problems in the book.

The book has problems in logic, probability, statistics and finance, as well as a very useful chapter of general interview questions. If you’re interested in buying this book, I should mention that some questions require calculus and knowledge of financial terms.

I love the author’s taste in problems, and here are some sample questions from the book.

Question 2.7: How many degrees (if any) are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?

Question 5.1.14: Welcome to your interview. Sit in this chair. Excuse me while I tie your arms and legs to the chair. Thank you. Now we are going to play “Russian roulette.” I have a revolver with six empty chambers. Watch me as I load the weapon with two contiguous rounds (i.e., two bullets side-by-side in the cylindrical barrel). Watch me as I spin the barrel. I am putting the gun against your head. Close your eyes while I pull the trigger. This is your lucky day: you are still alive! Our game differs from regular Russian roulette because I am not going to add any bullets to the barrel before we continue, and I am not going to give you the gun.
My question for you: I am going to shoot at you once more before we talk about your résumé. Do you want me to spin the barrel once more, or should I just shoot?

Question 6.1.16: Tell me something you tried but ended up quitting on.

I can tell you what I would have answered to the last question: I tried smoking, but ended up quitting.

What follows is the story of a pair of integer sequences, which started life as a Google interview puzzle back in the previous century when VHS video tapes were in use:

Suppose you are buying VHS tapes and want to label them using the stickers that came in the package. You want to number the tapes consecutively starting from 1 and the stickers that come with each package are exactly one of each digit [“0″…”9”]. For your first tape you use only the digit “1”, and save all the other digit stickers for later tapes. The next time you will need a digit “1” will be for tape number 10. By this time you will have several unused “1” stickers. What is the next tape number such that after labeling the tape with that number you will not have any “1” stickers remaining?

We can formalize this puzzle in the following way:

Consider a function f which, for a given whole number x, returns the number of times that the digit 1 is needed to write all of the numbers between one and x. For example, f(13) = 6. Notice that f(1) = 1. What is the next largest x such that f(x) = x?

Thus f(x) is the number of “1” stickers needed to label all the tapes up to tape x. When f(x) = x then we have used all of the “1” stickers in labeling the first x tapes.

Let’s consider any non-zero digit. In the single and double-digit numbers, there are ten of each digit in the ones column, and ten of each digit in the tens column, so 20 altogether. Early on, the tape number is ahead of the digit count. By the time we get to 20-digit numbers, though, there should be, on average, two of any single non-zero digit per number. Thus, the number of times that any digit is used should eventually catch up with the tape numbers.

Encouraged by assurance of reaching our goal somewhere, we might continue our estimate. In the up-to three-digit numbers there are 300 of each non-zero digit; in the numbers below 10,000 there are 4000; then 50,000, and so on up to 10¹⁰, where f(x) and x must (almost) meet. In particular, there are 10,000,000,000 counts for any non-zero digit in the numbers below 10,000,000,000. Hence, were the puzzle asking about any of the digits 2–9, then ten billion could have been an easy answer or, at least a limit on how far we need to search.

Sadly, there is a 1 in the decimal representation of ten billion (and a few zeroes), so we require 10¹⁰+1 of the digit “1” to write the numbers [1…10¹⁰]. Thus, f(10¹⁰) ≠ 10¹⁰, so 10¹⁰ cannot be the answer to the original puzzle. Thus stymied, Gregory wrote a program to find the solution to the original Google’s puzzle. And the answer turned out to be 199,981.

Gregory was overstymied, so he actually wrote a program to solve the puzzle for any non-zero digit. He calculated the beginning of the sequence a(n), where a(n) is the smallest number x > 1 such that the decimal representation of n appears as a substring of the decimal representations of the numbers [1…x] exactly x times.

We already know that a(1) is 199,981. The sequence continues as follows: 199,981,   28,263,827,   371,599,983,   499,999,984,   10,000,000,000,   9,500,000,000,   9,465,000,000,   9,465,000,000,   10,000,000,000, ….

Did you expect this sequence to be increasing? You could have, because smaller numbers tend to contain smaller digits than larger numbers. Then why is the sequence not increasing? As Gregory failed to find a value for the digit 5 below ten billion, he noticed that it’s fairly easy to imagine a scenario where you have one less than the number you need, and then the next value has more than you need for equality, and then you equalize again later. In response, Alexey Radul, a friend of one author and a son of the other, suggested a related sequence:

Let a(n) be the smallest number x > 1 such that the decimal representation of n appears as a substring of the decimal representations of the numbers [1…x] more than x times.

The key difference being “more than” rather than “exactly”. Starting at 1 then, here are the first nine terms of each sequence:

Some of these pairs are interesting in their own right. Notice that 199,991 is ten more than the previously found 199,981. For all the numbers in between, the initial equality holds. Likewise for n=3, each of the numbers between 371,599,983 and 371,599,993 has exactly one three. Hence, the increase in a number by one is the same as the increase in the count of threes. A similar situation holds for n=4.

Gregory has submitted these two new sequences to the Online Encyclopedia of Integer Sequences, as they turned out not to be there yet, and they can be found using the identifiers A163500 for the “=” sequence and A164321 for the “>” sequence. It’s not surprising that the values matching this relaxed second condition are more well behaved than those with equality. Do you think the second sequence is always increasing? Wait a minute, let’s check that sequence for zero.

In counting zeroes, it is important to remember that we start with one, not zero. In this case the smallest number x such that x is less than or equal to the number of 0s in the decimal representations of [1 … x] is 100,559,404,366. But what is the corresponding number for the “=” sequence? It appears that no such number exists. The challenge of accurately proving it, as they say, is left as an exercise to the reader.

There is no reason that we should be constrained to single digits. The formal statement of the problem provides an obvious generalization, where we consider substrings of each of the numbers [1 … x] rather than digits in those numbers. We should note that we count every occurrence of a substring separately. Thus 11 will be counted twice as a substring of 1113.

We can prove that the “more than” sequence is increasing after the first term. Indeed, for two integers i and j, if i is less than j, then for every occurrence of j, by replacing j with i we get a smaller number with an occurrence of i.

Inspired, Tanya wrote another fancier and faster program to find values of this sequence for two-digit numbers. Here is the smallest number x for which the number of “10”s as substrings of the numbers [1…x] is more than or equal to x. And by a lucky strike the equality holds. The number is: 109,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,810. Now the reader can do an exercise and find the number for the “more than” sequence.

The value of a_≥(11) might seem like a miracle: 119,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,811. Note how strikingly similar it is to the tenth element of the sequence! Can you explain that similarity between a_≥(10) and a_≥(11)?

Sadly, a_≥(12) is not so pretty: 1,296,624,070,230,872,986,615,199,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,812.

We cannot leave off without at least mentioning that the sequence function should next take one more parameter: the base of representation.

We have found only the first few members of these new sequences, and there are many related sequences to be catalogued. We would love to hear tales from your explorations. Enjoy the sequence hunt!

Peter Winkler gave a talk at MIT last fall and, as is customary, the audience was invited to join him for dinner afterwards at a local restaurant. I was eager to dine with Peter because he is a puzzle collector and I was hoping to hear a new puzzle. I got what I was hoping for — tripled. We got a pizza puzzle, a cake puzzle and a tart puzzle to complement our dinner. Today I will discuss the pizza puzzle.

Peter is now a columnist at ACM communications. His column is called “Puzzled” and it is featured as part of the section titled “Last Byte.” Writing these paragraphs has made me so hungry that I need to go grab something to bite.

Okay, I am back and here is the pizza puzzle.

Alice and Bob ordered a pizza. The pizza is cut into several radial pieces. Both Alice and Bob are greedy and well-mannered at the same time. They each want to get as much pizza as possible for themselves, but they don’t want to be obvious about it. They take pieces in turn, starting with Alice. Because they are well-mannered and not obvious, when it is their turn, they only take a piece that is adjacent to the pieces already taken. Throughout the process of consuming this pizza, the untaken pieces are contiguous.

The question is: Is it possible to cut the pizza in such a way that although Alice starts, Bob can guarantee himself more than half?

If you want to think about this puzzle on your own, now would be a good time to pause. Why? Because in the next paragraph, I will give you some hints about how to approach this question.

If the number of pieces is even, then Alice can’t lose. She can number the pieces around the circle consecutively, decide whether all the odd pieces or all the even pieces make up a bigger chunk, and then follow the parity.

But what happens if there are an odd number of pieces? Alice has an advantage, for she will get more pieces. But is that enough to guarantee that she will get at least half? Suppose she starts by taking a minuscule piece. Then Bob can number all of the leftover pieces in order and decide if he prefers the even-numbered group or the odd-numbered group. He is in control now, so he can guarantee himself the bigger part of the leftover pieces.

However, that might not be good enough for Bob to win. For example, if there is a very big piece, one that is bigger than half of the pizza, then in the first move Alice wins.

On the other hand, would Alice necessarily win by starting with the biggest piece?

Suppose the biggest piece is significantly less than half. Would Bob have a chance? To his advantage, he does have a lot of control. He can choose the parity of the pieces he wants at the beginning, and he can also switch this parity later, depending on what Alice does. Does he control the situation enough that it would be possible to cut the pizza in his favor?

I have to add that if you can find a solution with N pieces, then you can easily build a solution with N+2 pieces. Suppose you start with a pizza cut into N pieces, such that Bob will win. If you add two adjacent pieces of zero value to this pizza, you will get a pizza cut into N+2 pieces, such that Bob can still win. Indeed, Bob will follow the strategy he used with the N-pieces pizza, except that each time Alice takes one of the new pieces, Bob takes the other.

Can you find a way to cut a pizza so that Bob can guarantee himself more than half?

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?

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.

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.