The Patient Ant And The Stretchy Rubber Band | Hacker News Reader

The Patient Ant And The Stretchy Rubber Band

solipsys.co.uk

15 pointsColinWright11 comments

Ignore the length of the rubberband. Just think of the fraction of the rubberband the ant covers in any given minute.

The first minute, the ant moves 1/100 of the length of the rubberband. The second minute, 1/200. The third minute, 1/300. Then 1/400, 1/500, 1/600, and so on.

Those who are well-versed in discrete math should recognize this as a variant of the "harmonic series" [0]. It is divergent, meaning it eventually -- but excruciatingly slowly -- will reach any given number. Thus, the ant will eventually reach the end of the rubberband. However, this will take him about 1.5 x 10^43 steps [1]

[0] http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%...

[1] http://oeis.org/A082912 - "In 1968 John W. Wrench Jr calculated the exact minimum number of terms needed for the series to sum past 100; that number is 15 092 688 622 113 788 323 693 563 264 538 101 449 859 497. Certainly, he did not add up the terms."

For the record, I was playing with an experimental perl script (which I was in the process of concluding would not work), when lotharbot walked in and asked what I was doing. I explained the problem, and he had the solution within a few seconds.

So this post inspired me because I've been doing a lot of the Project Euler (http://projecteuler.net/) problems and this seemed in a similar vein.

I let it run a few hours in Python on a fastish laptop (although I could only use one core) and only got to ~23%. I became interested in the number of minutes it took to advance each step, and found an interesting pattern:

To go from 7% to 8% takes 2.719 times as long as 6% to 7%, and 8% to 9% takes 2.719 times as long as that. The period eventually settles at e (2.7182818...). Using this, it should be easy to calculate the total number of minutes as such: I found it took 100210581 minutes to get to 19%, so: 100% = 100210581 * e^(100-19) = 1.509e+43

I checked my math by using another number (36865412 is ~18%) so while I don't understand the underlying mathematics, I'm at least confident that this is correct. It also contradicts my intuition which says that as the ant gets closer to the end, the rubber band stretching goes on mostly behind him and he should be able to make % increases in fewer minutes.

Anyway, here is my python script which never gets past 23% (I'm on minute 14803200000, or year 28,164): https://gist.github.com/1871474

In essence, what's being computed is the sum of 1 + 1/2 + 1/3 + 1/4 + ... (which we call the harmonic series), and you're trying to figure out how fast it reaches a given number. You've experimentally verified that it takes exponential time, which is another way of saying that the sum grows like a logarithm.

To verify this mathematically, use the "integral test" [0] twice. The linked proof shows that the sum of k terms is larger than ln(k+1). It turns out that, by drawing the rectangles under instead of above the curve, you can also show that the sum of k terms is less than 1+ln(k+1). Thus, the long-term behavior of the sum is essentially the same as the long-term behavior of a (base e) logarithm.

[0] http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%...

Think of the ant's progress as a percentage. Every step he makes will increase his progress percentage across the rubber band. Therefore, if he keeps walking he will eventually make it to the other side. Am I missing something?

If the rubberband doubled in length every minute, the ant would still make progress in terms of percentage, but never come close to the end of the rubberband. He would approach the 2% point -- the sum of 1 + 1/2 + 1/4 + 1/8 + ...

In this case, he will eventually make it to the end -- the sum of 1 + 1/2 + 1/3 + 1/4 + 1/5 + ... is divergent.

That's necessary but not sufficient for the ant to make it to the end. Imagine an ant walking on a fixed rope but reducing its speed, such that during the first second it covers one quarter of the rope, the next second covers one eight, and reducing its speed by half like this each second. It will never reach the halfway point of the rope, let alone the end, but the percentage of the rope that it covers always increases.

In this particular case it does make it to the end, just showing how the fact that the percentage always increases is not quite enough to show it.

But his speed would only slow down until he hits the 50% point. After that, his speed will increase until he hits the end.

Huh? I am posing a different hypothetical problem to illustrate how covering a steadily increasing percentage of the total length doesn't necessarily imply that the ant ever reaches the end.

Looks like he gets there somewhere around step 1.5E43. Infinite patience indeed...

That factor of gamma makes a surprisingly large difference. Without it I get about 2.7e43.

Interesting.

Reply on news.ycombinator.com