Tuesday, July 04, 2006

John Von Neumann and the Mathematician's Trap

This little story about the great mathematician John Von Neumann has always been one of my favorites. I will tell it the way I first heard it. I have since heard a few variations on the story, leading me to think that there may be a component of Urban Legend to it. But I really don't care, because I think it's such a great story that it's worth retelling.

John Von Neumann was considered by many to be one of the most brilliant minds of the twentieth century. He reportedly had an IQ of 180. He was a pioneer of Game Theory, which was very important during the nuclear arms race. (Because GT assumes that all players act in their own best enlightened self-interest, GT turned out to be a much better model for evolutionary biology than for human behavior.) He was also one of the two people (Alan Turing being the other) who is credited with being the father of the modern computer.

The story goes that someone once posed to Von Neumann the following problem:

Two trains are 20 miles apart on the same track heading towards each other at 10 miles per hour, on a collision course. At the same time, a bee takes off from the nose of one train at 20 miles per hour, towards the other train. As soon as the bee reaches the other train, it bangs huwey and heads off at 20 miles per hour back towards the first train. It continues to do this until the trains collide, killing the bee.

The question is, how far does the bee fly (d) before the collision?

This is a pretty staight-forward problem for anyone who has studied Mathematical Analysis or Pre-Calculus. The initial separation is D = 20 miles (from here on out I will use the variable D, then substitute the value of 20 miles at the end. I think this makes it easier to follow the steps.) The bee is traveling twice as fast as each of the trains, therefore covering twice the distance as the approaching train before the first turn-around. So the distance d1 that the bee travels on the first leg, plus the distance the approaching train travels (one half d1) equals D.
Therefore d1 = 2/3 D.

As the bee begins leg #2, not only has the turn-around train covered the distance 1/3 D, but so has the train the bee is now heading towards. That means the remaining free distance D' = 1/3 D. By the same argument as above, the bee covers two thirds of this distance on his second leg.
Therefore d2 = 2/3 D' = (2/3)*(1/3)*D.

For leg #3, by the above argument, the remaining distance D'' = 1/3 D', which the bee covers two thirds of.
Therefore d3 = 2/3 D'' = (2/3)*(1/3)*D' = (2/3)*(1/3)*(1/3)*D.

I hope you all can see the pattern that's developing. Each trip gets one third shorter. Symboically speaking, if we move the 2 and the D out to the begining, we get 2D*(1/3)*(1/3)*... with the number of 1/3's being equal to the leg#. Since this is the same as raising (1/3) to the exponent equal to the leg#, we get
dn = 2D/3^n.

This means that on the nth leg of its journey, the bee flies 2D times one third raised to the power n (or conversely, 2D divided by three raised to the power n). Now that we know how far the bee travels on each leg, it's time to find out the total distance. The distance the bee travels after n legs (d'n) equals
d'n = d1 + d2 + ... + dn, which equals
d'n = 2D/3 + 2D/3^2 + ... + 2D/3^n, which when we factor out the 2D we get
d'n = 2D*(1/3 + 1/3^2 + ... + 1/3^n), which in mathematical notation is written as

(note: I've been having trouble with my free Math graphics software. The formulas look neat when I compose them, but when I go to export them, the software keeps changing the capital Sigma "Σ" to a capital Ess "S" which is begining to frustrate me. When I work out the prblem, I will edit this post to add the cool mathematical graphics. In the meantime, please bear with my poor man's notations.)

d'n = 2D * (x=1 --> n)Σ[1/3^x]

Let me take a moment to try to explain my rigged notation. Σ means "summation." The expression inside the brackets is what is being summed. The expression inside the parenthesis tells you over what values you perform the summation. So for the above expression, that means we will be adding up the values of 1/3^x for the values of x=1 through x=n. In other words, 1/3^1 + 1/3^2 + ... + 1/3^n.

There may be a formula for solving that sum; I may even have been taught that formula. But unfortunately, that's not the kind of knowledge that I tend to retain. Therefore we will solve this using the algorithm I remember and can (kind of) explain. What I will do is sum up the first few terms, look for a pattern, then use induction to prove it. Hopefully my explanation will at least make an inkling of sense to those of you who are completely lost right now. So here we go.

1/3 =1/3
1/3 + 1/9 = 4/9
1/3 + 1/9 + 1/27 = 13/27
1/3 + 1/9 + 1/27 + 1/81 = 40/81
. . .

The pattern I see here is that the numerator (top part of the fraction) is half of the denominator (bottom part of the fraction) minus one. In other words,
Since the denominator is just 3^n, then the numerator is 1/2*(3^n - 1).

So the formula that I need to test with induction is
(x=1 --> n)Σ[1/3^x] =? 1/2*(3^n - 1)/3^n

Before I proceed further, let's do a quick refresher on mathematical induction. The basic idea is that you prove a general expression by first proving that it is consistent, ie. IF it's true for some specific case, then it must necesarrily be true for some general case. Then prove that it's true for that specific case, and you're done.

The normal route is to assume that an expression is true for some value x=n, then attempt to prove that it must necesarrily be true for x=n+1. Which of course means it's also true for n+2 (substitute n+1 for n), n+3 and all x greater than n. Now if you prove it's true for x=n=1, then it must be true for all n. Since we've already proven our formula true for n=1 (and 2 and 3 and4), we only need to prove that if it's true for x=n, then it must also be true for x=n+1.

We have
1. (x=1 --> n)Σ[1/3^x] = 1/2*(3^n - 1)/3^n
which we are assuming to be true for x=n, and trying to see if
2. (x=1 --> n+1)Σ[1/3^x] =? 1/2*(3^{n+1} - 1)/3^{n+1}
is also true.
If we recall that adding 1 to an exponent is the same as multiplying by the base
3. 3^{n+1}=3*3^n, we get
4. (x=1 --> n+1)Σ[1/3^x] =? 1/2*(3*3^n - 1)/3*3^n
Going back to the meaning of Σ as summation, summing up to x=n+1 is the same as summing up to n, then adding the next term where x=n+1. In other words,
5. (x=1 --> n+1)Σ[1/3^x] = (x=1 --> n)Σ[1/3^x] + 1/3^{n+1}
Substituting statements 1. and 3. into 5. we get
6. (x=1 --> n+1)Σ[1/3^x] = 1/2*(3^n - 1)/3^n + 1/3*3^n
= 3*(3^n - 1)/2*3*3^n + 2/2*3*3^n
=(3*3^n - 3 +2)/2*3*3^n = (3*3^n - 1)/2*3*3^n = 1/2*(3*3^n - 1)/3*3^n
which is the expression we were trying to prove in statement 4.

Since we've already proven it for n=1, then expression 1. has now been proven true for all n.
1. (x=1 --> n)Σ[1/3^x] = 1/2*(3^n - 1)/3^n

Back to our friend the bee. We now have an expression for how far the bee flies after n legs
7. d'n = 2D * 1/2*(3^n - 1)/3^n = D*(3^n - 1)/3^n
and we need to solve it for how far the bee flies before dying. In actuality, the bee will stop flying (okay, "in actuality" this would never happen) when the distance between the trains is less than the body length of the bee. However, since the summation quickly converges on the solution, we can assume that the bee is a point, ignore the famous paradox, and do the summation up to n=infinity.
7. d'n = D*(3^n - 1)/3^n = D*(3^n/3^n - 1/3^n) = D*(1 - 1/3^n)
Quick refresher on infinite limits: as we let n get infinitely large, 3^n approaches infinity, and 1/3^n approaches zero. Therefore the limit as n approaches infinity is
d = limit(n-->infinity)[D*(1 - 1/3^n)] = D*(1-0) = D = 20 miles!

We have just solved this problem by the infinite series method. Infinite series are very important in Mathematical Analysis and Pre-Calculus as they form the basis for derivatives and integration and everything which is Calculus and Differential Equations. That's why all students of Math, Physics and Engineering get to do a ton of infinite series problems before they graduate. The reason I call this problem the "Mathematician's Trap," is because virtually all mathematicians who see this problem will try to solve it the way we just did.

However, if you were to give the problem to someone who's only had basic Algebra, they might solve it differently. The trains crash at the midway point which is at 10 miles. Since each train is going 10 mph, this takes one hour. During that same hour, the bee is flying at 20 mph, therefore the bee flies 20 miles! Wow, that was a lot easier!

(note: Some of you may have noticed that for the infinite series solution, I didn't use the respective speeds of the bee and the trains, but only their ratio. This would also work for the algebraic solution, but it would make the math a little more complicated, which rather defeats the purpose of what I was trying to prove. In fact, as a general case, as long as the speeds of the two trains adds up to the speed of the bee, the distance traveled by the bee will always be the initial separation of the trains, ie. d=D. You can see this in the following thought experiment. Since the speeds of the trains added together equals the speed of the bee, at any given moment in time, the distance covered by the two trains together is equal to the distance covered by the bee. That means that at any given moment in time, the available flying space left is equal to what would be the remaining distance if the bee were flying unimpeded from point A to point B. Therefore d=D. Think about it.)

The moral of the story is that being smarter or better educated can often times put you at a disadvantage. When someone is trained at doing something a certain way, that action is virtually automatic. It takes great insight to be able to "step outside of the box" and ask if there's an easier way to do it. (I'm currently working on another post on just this subject which should hopefully be up soon.) Even brilliant mathematicians will fall into the trap, which brings us back to John Von Neumann.

When posed with the above problem (or some variation of it), JVN took all of five to ten seconds to come up with the correct solution. This floored the questioner who said "I'm impressed that you didn't fall for the Mathematician's Trap." After getting a perplexed look from our genius, he asked "How did you solve the problem?"

"By infinite series, of course!"


Anonymous said...

Given the sum of the trains speeds equals the bees speed you can even simplify more by thinking of one train approaching a wall with the sum of the speeds and the bee flying right ahead. After 20 miles both the train and the bee crash into the wall.

Mark Leeper said...

"virtually all mathematicians who see this problem will try to solve it the way we just did."

This is patently false. I suspect you have not asked this question of many mathematicians. Mathematicians are trained to look for elegant solutions. They are probably better at finding them than the general public. They will look at three or four ways to solve a problem rather than trying the brute force technique you suggest.

Anonymous said...

Being smarter or better educated never puts you at a disadvantage. Thinking you are smarter while not being smarter does.

"virtually all mathematicians who see this problem will try to solve it the way we just did."

I agree with the other poster in saying this is "patently false". Being well educated myself, I immediately recognized that the solution involved a series I didn't want to solve so I considered the possibility of an alternate solution. A moment later the answer was obvious and if it took me 5 seconds I'd be surprised.

I would call this the "dumb mathematician's trap". It doesn't take much cleverness to look right though this problem.

Anonymous said...

I had the same problem with getting math to display correctly a while ago as well. I finally stumbled across a nice javascript package thing call jsmath which allows for inline LaTeX math markup, and seems fairly platform independant, and not completely fugly.

Anonymous said...

I don't understand why this problem *and* the story doesn't drive at least the physicists up the wall. There is no way for the bee to change directions without deceleration and acceleration, so the claim that it is always traveling at 20mph is absurd. This would require massive change in momentum, killing the bee the first time it happens.

There's no way Von Neumann (or any decent mathematician) would miss this point.

clin said...

Math problems are meant to make the visualization easier to follow. The problem could be phrased abstractly without resorting to bees. By a similar argument, you could ask why a bee would want to go back and forth, why two trains are travelling so slow, why two trains are on the same track, etc. Most people seeing this problem see it as a math problem, not as some representation of reality.

As an aside, I was surprised to see Mark Leeper. I used to see his name on Internet movie reviews back in the day. Guess he's still doing it!

david said...

Actually, the way I heard it was that Von Neumann replied so fast that the guy asked him if he knew the "easy way," to which he replied something to the effect of "what's easier than summing up the series?"

Anonymous said...

Ah, I've heard this problem before, but you missed the rest of the problem, the most interesting part.

Assuming the trains are traveling east and west, and the bee departs from the western, eastbound train, which direction is the bee facing when the trains collide?

wivnee said...

The last post above me is briliant..

Charles said...

Hmm.. If had known that someone would think that was so brilliant, I would have signed in when I posted it. But I can't take credit for the brilliance of that question, I think it originated from that old wag Martin Gardner.

Let me make the problem easier to solve, by making some assumptions necessary for its solution. Assume the bee is a point, and turns direction instantaneously. Hint: think about Xeno's Paradox.

Martijn said...

I've heard slightly different version of the same story, but with an interesting twist.

Ulam (or some other famous mathematician) posed the train riddle to Von Neumann, who thought for a couple of seconds and came up with the right answer. "Oh you've heard it before" he said with a disappointed look on his face. "What do you mean?" "Well, that you [explains easy solution], instead of summing the series." "Oh yes, that's a good way too."

Von Neumann was such a brilliant mathematician that he could solve the problem the difficult in a couple of seconds. When you're that brilliant you don't need shortcuts!

Anonymous said...

It's a trade-off really. The "mathematician's" way is more generic although it takes longer. Suppose that one train started at 20mph but also accelerated at 1m/h/h. It this case the 'easy' way is actually impossible and will never be able to arrive at an answer however, the mathematician's strategy can be applied also as easily as in the original problem.

Zipi said...

Virtually all mathematicians who see this problem try to solve it the way we just did.

I agree with some previous posters who said this is patently false. Mathematicans are trained to think outside the box, to always look for the most elegant question, and that every tool that they have previously learned in their lives can be used at any moment. Maybe you are confusing mathematicans with those who believe they know math (such as some teachers and plenty of college students), but who have just only memorized algorithms without understanding what they are doing.

Anyway, I challenge you to pose this problem to real mathematicians and tell us what happened. I am one and did not think of adding the series for a second.

Anonymous said...

what i am wondering is where the story is... so it was posed to Neumann... what happened after that?!!

Anonymous said...

I disagree that "There's no way Von Neumann (or any decent mathematician) would miss this point" in reference to the questionable physics behind this problem.

As an engineer and a physicist, I took most of my advanced math classes directly from the math department and not from an engineer of physicist. The mathematicians that taught our advanced math classes were top notch and I still laugh about the absurd physics behind many of the math problems.

My favorite math examples use electric circuits with 10 Farad capacitors, 10 Henry inductors, 1 Ohm resistors and 10 Volt supplies.

My point is that even great math texts have laughable physics. So I'd say that any decient mathematicians might easily overlook the physics behind this problem.

Anonymous said...

In one variation, the first train is being driven by a Norwegian and the other is being driven by a drunk. As a result, the bee can keep flying indefinitely: for norse is norse, and souse is souse, and never the trains shall meet...

Anonymous said...

Was it an African or European bee?

Charles said...

I see that nobody bit on my question about which direction the bee is heading when the trains collide. I remember the answer, but not the exact math of reaching it, which involves eigenvectors, which is beyond my meager ability. But the answer seems obvious once you hear it: the bee's direction at collision time is in a superimposed state, going both east and west at the same time. As the trains converge, the bee reaches a state where it is moving back and forth infinitely fast.

Oh well, this thought experiment is obviously beyond the limits of real physics and real bees and locomotives, so this answer may be unsatisfying but correct mathematically. But I think it was Ulam who said, "insofar as mathematics accurately reflects the real world, it ceases to be interesting.

Johan Richter said...

I think it is fair to say that von Neuman, and almost all other mathematicians, would realize that changing direction requires acceleration. von Neuman did after all write "The Mathematical foundations of quantum mechanics" so he clearly knew some physics. On the other hand I don't think many mathematicians would actually be bothered by the absurd physics.

I totally agree with the point that mathematicians look for elegant solutions and doesn't just settle for the first they can find.

Anonymous said...

which direction the bee is heading when the trains collide?

up! up! up!

The Science Pundit said...

Thank you everyone for all the comments you all left on this post. This is much more attention than I'm accustomed to, and I really appreciate it.

Many of you had an issue with my comment "virtually all mathematicians who see this problem will try to solve it the way we just did." If this is the biggest problem you all had, then I'm truly flattered that you liked the story. However, I should address this.

Having re-read my post and this statement in particular, I admit that I made an unjustified generalization and stated a belief as if it were a fact. This was wrong and I am sorry for it. But I stand by my belief.

It is based on a psychological theory which I discuss in my newest post. (which is in fact the same incomplete post which I refer to in my Von Neumann post--I'll need to update the link) In my post I argue that soaking in (and repeating) what you're taught without evaluation is not only the most efficient way to gain new knowledge, but, on average, the best way to behave.

"Thinking outside the box" is only a virtue when used sparingly (ie - when it "seems" appropriate). It becomes a hinderence to productivity when used indiscriminantly. Far from being "stupid" (I sure as hell don't consider Von Neumann stupid), I believe the instinct to solve by infinite series is a virtue.

Commenter #12 had it exactly right. The only reason that there is a short cut solution to this problem is that all velocities are constant (except of course for the bee's instantaneous, infinite accelerations at the turns :-D). The best way to approach the general case for this type of problem is exactly the way we were taught in precalculus: by infinite series. I may not have posed this problem to "real mathematicians" (whatever that means), but I personally find it hard to believe that anything but a majority will approach it as an infinite series problem.

Thank you again for all your comments. I welcome further comments and discussion on this or any of my other posts.

Thank you,

The Science Pundit said...

Also, comment #17 is da bomb!

Anonymous said...

As a graduate student in Mathematics I also would like to add in my two cents by denouncing the statement that most mathematicians will do this problem by infinite series. The author of the original post in his response to the many objections is implying that mathematicians are taught routine methods from which they sometimes deviate and think outside the box. This is a classic misunderstanding of what Mathematics is, usually caused by years of rote and mind-killing repetitive high school number crunching. No self-respecting math program in any university will teach their students a standard method for how to solve this problem. There is no textbook that says in such a situation one must use infinite series or any other specific method. Mathematics is not a long list of methods and what to apply in what situation. It is the study of creative and logical problem solving. This means creating solutions for problems that have none. The simpler and more clever the solution, the more elegant it is, and the better. A mathematician is trained to spot the good solution, and one who fails to see the easy one to this problem is not worth his or her salt.

Lucio M. Tato said...

You said:
"Commenter #12 had it exactly right. The only reason that there is a short cut solution to this problem is that all velocities are constant"
Let me disagree. The "easier way" is not a "short cut", it's a problem separation: You forget the bee and calculate the time to collision. After that, you can calculate the distance traveled by the bee.
The problem separation it's useful even if the bee or the trains have not constant speeds.
And Commenter #12 had it not right because if on of the trains starts at 20mph and accelerates, the 20mph bee wil be traveling pushed by the windshield at the first turn! ;)

Sophist said...

Loved the thread, felt great to refresh much-loved concepts of time and motion and browsing through others thanks to the pointers given both in the post and in the comments to it.

I want to agree that the natural, instinctive way for the brain to 'think' is in line with the infinite series method, and it is heartening to see that there are theories built around this view, but Zeno's paradoxes were and still are considered 'counter-intuitive'. If this really were the way our brains are naturally wired, would these problems be considered paradoxes at all? Sure, they involve definite contradictions, but perhaps they are paradoxes because they disagree with the way most people think (which the author has honourably set aside himself in his proof), because most people would want to see the problem in a manner that reflects reality for them?

That thought leads me to wonder if the conceptualization of reality itself has something to do with it. For me, a visualization of reality would be the infinite series, so I have o agree with the author. Perhaps there are people for whom the instantaneous, intuitive response to a problem like this is in its depiction in terms of speed, distance, mid-points, and relative velocities, i.e., in the terms of the physical world. But I doubt it, more so with regard to mathematicians and philosophers (if I'm being naiive or dramatic in using the two in the same sentence, do forgive the indulgence.) I recall reading somewhere that mathematicians in particular do tend to think in a manner of 'abstracted reality' which is rarely elegant, or simple, at first go. I believe that the elegance and the applicability of solutions comes only after at least one level of translation of the initial thought, which might well be an obvious and rather 'brute force'-like way of approaching the problem.


question can be further simplifeid applying theory of RELATIVITY.

--------, ,-------
1 ] bee -->@ [ 2
________] [_______

now bee leaves from train 2 assuming train1 to be stationary train2 approaches train one at 20 mph and bee also flies at 20 mph
therefore they both reach at train1 at same time and and bee is killed that very moment after travelling 20 miles b/w two trains in one hour