Hacker News Reader

Comment by DanielStraight | Hacker News Reader

Since Wikipedia doesn't do a good job of simply stating why the ant will eventually reach the end:

The expansion of the rope is over its entire length. When the ant is halfway across the rope, an expansion of 1 km only adds 0.5 km to the length the ant must traverse. So the farther the ant walks, the less the expansion matters, and eventually it won't even add the 1 cm the ant is moving per second.

At least that's as best I understand it.

Here's a Google spreadsheet that shows the process with a significantly faster ant:

https://docs.google.com/spreadsheet/ccc?key=0AsmKPGVX0X-0dFF...

No guarantee of being free of off-by-one type of errors, but it should give the general idea.

View on HN

That is a great intuitive explanation. Much better than the current wikipedia informal solution.

You should add it to Wikipedia, maybe under a new "An intuitive explanation" paragraph.

Or add it to the "simple" wikipedia language.

http://simple.wikipedia.org/wiki/Ant_on_a_rubber_rope

relevant xkcd... http://xkcd.com/547/

This is the right idea. At each iteration the ant has less and less actual band to traverse since it is also expanded behind him, where he's already walked.

We can represent this insight with a series: (1+1/2+...+1/n), as the wiki article states in one of it's approaches. Using Big-O logic, we know a series of this form is a Harmonic Series, and any Harmonic Series is O(log n). This is good news as there is no upper bound and will eventually reach 1 km (...someday).

Alternatively, say the rubber-band doubled every second? The distance the ant must travel is now growing exponentially and he will never get to the other end.

"At each iteration the ant has less and less actual band to traverse since it is also expanded behind him, where he's already walked."

Awesome explanation.

Great explanation. I think many people envision the stretching as either a) the entire 1 km being tacked on to the end, or b) as if the ant were walking alongside the rubber band, rather than on it. This helps clear that up.

This is what I was thinking but reading through the article I was thinking I thought wrong. Thanks for clearing that up.

Reply on news.ycombinator.com