Beijing

K. and I are in China. Today is my second full day in Beijing.

Actually, I should say that today is my second full day in one neighbourhood of Beijing. I’m in the Chaoyang district on the northeast section of the Third Ring Road.  I have not yet seen much beyond this area.

What I have seen has been unexpected. This area is heavily, heavily westernized. There are a great number of foreigners here—indeed, the U.S. embassy is literally across the street from me—and the various shops and restaurants here cater to foreign tastes. It seems that every restaurant, shop, or brand that a westerner could want can be found here.

For example, before breakfast this morning, I walked down to the local Starbucks for a cappuccino. K. had her usual venti skim milk latte. She ordered in English. The total came out to 60 RMB, which she paid by credit card.

It is strange to have come so very far only to end up in a place that is not immediately distinguishable—on the surface—from home.

A Curious Question that Demonstrates that Sometimes, Approximations are Infinitely Accurate

I keep a list of interesting mathematical questions with me at all times. On my flight Friday from Dulles to Hartsfield, I pulled this list out and considered the following question:

For the number $x = \frac{10^{20000}}{10^{100}-3}$, what is the digit in the units place?*

Just so that we’re clear on the question, in the number 12.34, the digit 2 is in the units place. Also just for clarification, $x$ is a really big number. It is approximately equal to $10^{19900}$, or 1 followed by 19900 zeroes!

For a point of comparison, the largest number that can be represented in a computer using the 64-bit floating point standard is about equal to 1 followed by a mere 308 zeroes. We cannot therefore hope to find the answer simply by handing the question to a machine. Instead, we will have to be clever.

Our trick will be to devise an easy-to-compute approximation of $x$ and use this approximation to answer the question. Normally, of course, this strategy will only give an approximation to the answer. The clever bit is that we will show that our approximation is so good that our answer is exact.

We start be rewriting $x$:

$x = \frac{10^{20000}}{10^{100}-3} = \frac{10^{20000}}{10^{100}(1-3\cdot 10^{-100})} = 10^{19900}\cdot \frac{1}{1-3\cdot 10^{-100}}$

So far this is exact. We can rewrite $x$ still further by taking advantage of some calculus. In particular, we can expand the fraction using a Taylor series:

$\frac{1}{1-\epsilon} = 1 + \epsilon + \epsilon^2 + \epsilon^3 + \ldots = \Sigma_{n=0}^{\infty} (\epsilon)^n$

Setting $\epsilon = 3\cdot 10^{-100} = \frac{3}{10^{100}}$, we get that

$\frac{1}{1+3\cdot 10^{-100}} = \Sigma_{n=1}^\infty \frac{3^n}{10^{100n}}$,

which means that

$x = 10^{19900}( \Sigma_{n=0}^\infty \frac{3^n}{10^{100n}})$.

So far, this is still exact as long as you keep all infinity terms in the sum. Instead, we will form an approximation of $x$ by keeping only a finite number of terms. Actually, we are only going to keep one term. The question, of course, is which one.

To figure out which term is the right one to keep, remember that we don’t really care about $x$ itself; we only want to know about the units digit. Notice also that our Taylor series in parentheses gets multiplied by the really big number $10^{19900}$. For a digit to end up in the units place after having been multiplied by $10^{19900}$, it has to have started out very small. In fact, it ought to be about equal to $10^{-19900}$. Do we have any such term in our Taylor series?

Yes we do. The term when $n = 199$ is equal to $\frac{3^{199}}{10^{19900}}$. When multiplied by the $10^{19900}$ out front, we get just $3^{199}$. This seems to be the most important term. Later, we’ll see that this is the only term that matters.

In order to determine the units digit of $x$, we will compute the units digit of $3^{199}$. This is actually a much simpler problem. Remember that $x$ is approximately equal to 1 followed by 19,900 zeros. For comparison, $3^{199}$ is about equal to 1 followed by a mere 100 zeroes or so. In fact, this is small enough that we could reasonably just hand the question to a computer now. And yet, somehow, that would seem to be such a sad thing to do. We have been clever enough to turn a really big problem into a merely-big problem so far; let us see if we can be still more so.

While $3^{199}$ is far too large a number to compute by hand, remember that we still don’t actually care about the whole number. We only want the units digit. Let’s see if we can find a pattern in the units digits of various powers of 3. Consider the following table:

 $n =$ $3^n =$ Units digit 0 1 1 1 3 3 2 9 9 3 27 7 4 81 1 5 243 3 6 729 9 7 2187 7 8 6561 1

Notice the pattern in the units digit. It is always the same four numbers repeated in sequence: 1, 3, 9, 7, 1, 3, 9, 7, 1 … Notice also that the unit digit is equal to 1 when $n$ is a multiple of 4. We want to know about $3^{199}$. Since 196 is divisible by 4, we know that the units digit of $3^{196}$ is 1. Then the units digit of $3^{197}$ is 3, that of $3^{198}$ is 9, and that of $3^{199}$ is 7.

Finally, then, we have an answer! For our number $x = \frac{10^{20000}}{10^{100}-3}$, the units digit is 7.

… Or is it? Remember that our answer has come from an approximation. In fact, we made what may have been a terrible approximation: instead of using all of the infinite terms in our Taylor series for $x$, we used just the one term when $n = 199$! How could our answer possibly be correct?

To begin with, the terms when $n < 199$ all end with long strings of zeroes. When you add them to our $n = 199$ term, then, the units digit doesn’t change. To see that they all end in long strings of zeroes, consider the $n = 198$ term:

$10^{19900}\cdot \frac{3^{198}}{10^{19800}} = 10^{100}\cdot 3^{198}$

Since $3^{198}$ is an integer, this means that this number ends with a string of 100 zeroes! The $n = 197$ term ends with 200 zeroes, the $n = 196$ term ends with 300 zeroes, et cetera, down to the $n = 0$ term which ends with 19900 zeroes! These terms, then, don’t change the units digit of $x$ at all.

How about the terms when $n > 199$? These terms turn out to all be between 0 and 1. That is to say, they all have the form 0-point-something. None of these terms change the units digit of $x$ either! To see this, consider the $n = 200$ term:

$10^{19900}\cdot\frac{3^{200}}{10^{20000}} = \frac{3^{200}}{10^{100}}$.

Since both $3^{200}$ and $10^{100}$ are big numbers, it might not be clear whether this number is bigger than 1 or less than 1. If this number is less than 1, then it has a zero in the units place and it doesn’t change our answer above. If this number is greater than 1, then it might not have a zero in the units place and we will have to worry about it. To quickly check whether it is less than 1 or not, we can rewrite the exponentials in terms of the natural exponential base $e$:

$3^{200} = 9^{100} = e^{\ln(9^{ 100})} = e^{100 \ln(9)}$

Similarly $10^{100} = e^{100\ln(10)}$. Thus

$\frac{3^{200}}{10^{100}} = \frac{e^{100\ln(9)}}{e^{100\ln(10)}} = e^{100(\ln(9) - \ln(10))}$.

Since $\ln(9) < \ln(10)$, the exponent is negative and therefore this number is less than 1. The same also holds true for all the terms with $n > 200$. This is to say that none of the terms with $n > 199$ affect the ones digit of $x$ either.

So there we have it: to determine the units digit of $x$, we only need to know the units digit of the $n = 199$ term! We can therefore be perfectly confident in our answer:

The units digit of the number $\mathbf{x = \frac{10^{20000}}{10^{100}-3}}$ equals 7.

As suggested in the title of this post, there is an interesting lesson to learn here. Sometimes, just sometimes, in very special circumstances, approximate answers are actually exact answers. For our question, it is easy to see why this worked. While the number $x$ is very, very large, we only wanted to know about a very small portion of it—just a single digit, in fact. We were therefore justified in ignoring most of the information we had about $x$ and focusing on just the one term that matters. By doing so, we turned a question about a number so big that even a computer couldn’t handle it into question that can be solved using pen-and-paper.

* This question is a very-slightly modified version of question A2 of the Forty-Seventh William Lowell Putnam Mathematical Competition given on December 6, 1986.

Bakeware and a cat

Problem 1: my apartment, while generally awesome,  suffered from a distinct lack of cat. Not just any cat—my cat. He’s old, somewhat lazy, and entirely insistent that he get his way, but he is fantastic. Solving this problem was the goal of my trip down to Blacksburg this last weekend.

Having cat back has been wonderful. He fills my apartment with life. He wakes me up in the morning. He usually does so by placing his front paw gently on my cheek. He does this repeatedly, tapping my face gently, as if to say, “are you awake yet?” Of course, his primary interest is breakfast. Still, I usually manage to squeeze a snuggle or two out of him. It’s a nice way to wake up.

Problem 2: I have all the ingredients necessary to make chocolate chip cookies as well as a fantastic box of brownie mix, but I do not have any bakeware. There are so many things that my new apartment is missing. On the bright side, this particular failing is easy to correct. I ordered a set of bakeware from amazon and it arrived today.

Conclusion: I am enjoying some absolutely fantastic brownies and hanging out with my awesome cat. Life is good.

Once more to Blacksburg

As I don’t have a functioning car at the moment, heading to Blacksburg is a moderately complicated affair. I’m renting a car for the weekend. The thing is, though, that the nearest car rental office seems to be in Dulles airport, some twenty miles away.

Fortunately, the public transportation seems to be quite good here. I’m taking the 981 from Reston Town Center straight to the airport. There, I will (hopefully) have a car waiting for me. Everything else ought to be pretty simple.
I have realized that I will be leaving town at just about five o’clock on a Friday. To put it another way, I am leaving at the worst possible time! On the bright side, as I am far outside the Beltway, maybe traffic won’t be so bad… Keep your fingers crossed!

On the Third Language

I spent a fair amount of my childhood in a Spanish-speaking household. Many of my relative speak Spanish. These days, my grandmother speaks Spanish nearly exclusively. It is therefore a bit of an embarrassment to admit that I do not, myself, speak Spanish.

Still, this is a situation which can be rectified. I have already learned quite successfully—as an adult, no less—to speak German. How hard could it be to take all the language-learning skills that I have developed and begin studying Spanish?

Actually, not very hard at all. I am following the same basic scheme for Spanish as I did for German. I learn a little bit every day, I listen to Spanish music and study the lyrics, and I try to have internal conversations with myself in Spanish every now and then throughout the day. Even better, I am much more eager to try out my developing Spanish skills. From my experience with German, I have already learned that people will still understand me and speak with me even if I sometimes conjugate the wrong verb. Overall, then, learning Spanish is going much smoother.

That said, there are a few weird exceptions. I consistently mix up German and Spanish. I only very rarely mix either up with English. As an example, I spent a few moments the other day wondering—in German—whether “con” takes Akkusattiv or Dativ objects. I concluded that it should take Dativ objects and chided myself gently for forgetting so basic a thing. The thing is, “con” is the Spanish preposition corresponding to the English “with”; I had accidentally mixed it up with the German preposition “mit” (which does, indeed, take Dativ objects). So, when speaking German, I will sometimes (rarely) accidentally and unknowingly use Spanish words with the correct meaning, and when speaking Spanish I accidentally mix in German words. I almost never accidentally use English words in either language.

It seems that these kinds of experiences are not very well studied in the field of linguistics. Indeed, it seems that interest in third language acquisition is only a fairly recent thing. This paper contains a short summary of recent research on the topic. A particularly interesting recent conclusion in the field is that a person’s ability to learn a third language depends on his or her proficiency in their second language more so than in their first. I suddenly wish that I had spent more time learning my verb conjugation tables in German.

A Moment from the DC Metro

I was returning home from the city via the orange line after spending an awesome day out with E., a friend of mine from Blacksburg, and V., a friend of E.’s. It seemed that most people on the train were returning full and happy from some sort of Thanksgiving Day celebration. As I was listening to my music and reflecting on the day, something unusual happened.

A man-and-woman couple that had been sitting a few seats over from me suddenly realized—a few moments too late—that the train was at their stop. They rushed toward the door, the man with a container of Thanksgiving leftovers in his hand, just as it began to close. The lady was first, and she nearly made it through the closing door. She gave out a small cry when the doors closed on her wrist, catching her hand fast.

Seemingly without thought, I found myself on my feet and crossing the half of the train car between myself and the door. I watched the man grasp ineffectively with one hand at the door, having not yet realized that he should put the leftovers down. Another guy rose to help; he arrived from the other direction in time to collide with me by the door. I knocked him completely out of the way by reason of simply being larger. I barely noticed, though, as I was focused on the door and the lady’s hand sticking through it.

The man had taken a hold of one door. Think that, together, we could pry them apart, I reached out for the other door. Just then, either the train itself, or its operator, realized that something was wrong and the doors sprung open. A recorded message warned everyone in a pleasant voice to stay clear of the doors. The man stepped through the opening with leftovers still in hand, the lady kindly called out a thank you, I apologized to the man whom I had knocked aside, and I returned to my seat.

No one else appeared to have moved. Perhaps no one else had even noticed.

The train accelerated smoothly away from the station and ordinary life reasserted itself. All was as though nothing had happened.
.