Tanya Khovanova's Math Blog

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?

I wrote a story a while ago about how a clerk at my previous job mistyped my resignation date, substituting January 2007 for my real date, January 2008. As a result, my medical insurance provider decided that I wasn’t covered in 2007, and requested that my doctor return the money he had already received.

After several phone calls my medical insurance was reinstated, but I kept receiving bills from my doctor. When I called my insurance, they assured me that everything was fine and that they had paid my doctor. However, my doctor continued to send me bills.

After half a year of phone calls back and forth, someone finally explained to me what was going on. My insurance company had initially requested the money back. The money was never returned to them, because my doctor’s office would not pay them a penny until I had paid the doctor first. In my doctor’s database, my visits were marked as unpaid.

When the problem was cleared up, the insurance company stopped requesting that the doctor pay them back. But the computer at my doctor’s office didn’t understand that stop-the-request command. It didn’t know what stopping the request meant.

The computers were talking different languages and I was caught in the middle.

My son, Alexey Radul, made his PhD thesis available to the public.

I was amazed at how much he had invested in the thesis. I assumed that the main goal for a dissertation in computer science is to write a ground-breaking code and that the accompanying text is just a formality. However, this is not the case with my son’s thesis. I am not fully qualified to appreciate the “ground-breakness” of his code, but his thesis text is just wonderful.

Alexey decided that he wanted to make his thesis accessible to a wide audience. He had to make a lot of choices and decisions while he was designing and coding his prototype, and in his thesis he devoted a lot of effort to explaining this process. He also tried to entertain: I certainly had fun trying to solve an evil sudoku puzzle on page 87, that turned out not to have a unique solution.

In addition to everything else, Alexey is an amazing writer.

I am a proud mother and as such I am biased. So I’ll let his thesis speak for itself. Below is the table of contents accompanied by some quotes:

1. Time for a Revolution
   

   “Revolution is at hand. The revolution everyone talks about is, of course, the parallel hardware revolution; less noticed but maybe more important, a paradigm shift is also brewing in the structure of programming languages. Perhaps spurred by changes in hardware architecture, we are reaching away from the old, strictly time-bound expression-evaluation paradigm that has carried us so far, and looking for new means of expressiveness not constrained by over-rigid notions of computational time.”

   1. Expression Evaluation has been Wonderful
   2. But we Want More
   3. We Want More Freedom from Time
   4. Propagation Promises Liberty
      

      “Fortunately, there is a common theme in all these efforts to escape temporal tyranny. The commonality is to organize computation as a network of interconnected machines of some kind, each of which is free to run when it pleases, propagating information around the network as proves possible. The consequence of this freedom is that the structure of the aggregate does not impose an order of time. Instead the implementation, be it a constraint solver, or a logic programming system, or a functional reactive system, or what have you is free to attend to each conceptual machine as it pleases, and allow the order of operations to be determined by the needs of the solution of the problem at hand, rather then the structure of the problem’s description.”

2. Design Principles
   1. Propagators are Asynchronous, Autonomous, and Stateless
   2. We Simulate the Network until Quiescence
   3. Cells Accumulate Information
3. Core Implementation
   1. Numbers are Easy to Propagate
   2. Propagation can Go in Any Direction
   3. We can Propagate Intervals Too
   4. Generic Operations let us Propagate Anything!
4. Dependencies
   

   “Every human harbors mutually inconsistent beliefs: an intelligent person may be committed to the scientific method, and yet have a strong attachment to some superstitious or ritual practices. A person may have a strong belief in the sanctity of all human life, yet also believe that capital punishment is sometimes justified. If we were really logicians this kind of inconsistency would be fatal, because were we to simultaneously believe both propositions P and NOT P then we would have to believe all propositions! Somehow we manage to keep inconsistent beliefs from inhibiting all useful thought. Our personal belief systems appear to be locally consistent, in that there are no contradictions apparent. If we observe inconsistencies we do not crash—we chuckle!”

   1. Dependencies Track Provenance
   2. Dependencies Support Alternate Worldviews
   3. Dependencies Explain Contradictions
   4. Dependencies Improve Search
5. Expressive Power
   1. Dependency Directed Backtracking Just Works
   2. Probabilistic Programming Tantalizes
   3. Constraint Satisfaction Comes Naturally
      

      “This is power. By generalizing propagation to deal with arbitrary partial information structures, we are able to use it with structures that encode the state of the search as well as the usual domain information. We are consequently able to invert the flow of control between search and propagation: instead of the search being on top and calling the propagation when it needs it, the propagation is on top, and bits of search happen as contradictions are discovered. Even better, the structures that track the search are independent modules that just compose with the structures that track the domain information.”

   4. Logic Programming Remains Mysterious
   5. Functional Reactive Programming Embeds Nicely
   6. Rule-based Systems Have a Special Topology
   7. Type Inference Looks Like Propagation Too
6. Towards a Programming Language
   1. Conditionals Just Work
   2. There are Many Possible Means of Abstraction
   3. What Partial Information to Keep about Compound Data?
   4. Scheduling can be Smarter
   5. Propagation Needs Better Garbage Collection
   6. Side Effects Always Cause Trouble
   7. Input is not Trivial Either
   8. What do we Need for Self-Reliance?
7. Philosophical Insights
   

   “A shift such as from evaluation to propagation is transformative. You have followed me, gentle reader, through 137 pages of discussions, examples, implementations, technicalities, consequences and open problems attendant upon that transformation; sit back now and reflect with me, amid figurative pipe smoke, upon the deepest problems of computation, and the new way they can be seen after one’s eyes have been transformed.”

   1. On Concurrency
      

      “The “concurrency problem” is a bogeyman of the field of computer science that has reached the point of being used to frighten children. The problem is usually stated equivalently to “How do we make computer languages that effectively describe concurrent systems?”, where “effectively” is taken to mean “without tripping over our own coattails”. This problem statement contains a hidden assumption. Indeed, the concurrency itself is not difficult in the least—the problem comes from trying to maintain the illusion that the events of a concurrent system occur in a particular chronological order.”

   2. Time and Space
      

      “Time is nature’s way of keeping everything from happening at once; space is nature’s way of keeping everything from happening in the same place ( with apologies to Woody Allen, Albert Einstein, and John Archibald Wheeler, to whom variations of this quote are variously attributed).”

   3. On Side Effects
8. Appendix A: Details
   

   “I’m meticulous. I like to dot every i and cross every t. The main text had glossed over a number of details in the interest of space and clarity, so those dots and cross-bars are collected here.”

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 − ε?