Solution to "I Would Walk Five Hundred Miles (Part 2)"


In the solution to Part 1 we found that Robert would walk 500e^{500}\approx 7.018\times 10^{219} miles.

Now let's see how far Derek would walk.

In the first quatrain Derek would walk

\underbrace{800}_{\text{800 miles}}+\underbrace{800(800)}_{\text{800 more for each of the first 800}}=800+800^2.


Then he would walk 799 miles for half of the additional miles. In other words he would walk 799\left( \frac{800^2}{2}\right)=\frac{799\cdot 800^2}{2} miles more, for a total of

\left[800+800^2+\frac{799\cdot 800^2}{2}\right] \text{ miles}.


Then he would walk 798 miles for a third of the last additional miles (798 times 1/3 of the last term). In other words, 798\cdot \frac{1}{3}\left(\frac{799\cdot 800^2}{2}\right)=\frac{798\cdot 799 \cdot 800^2}{2\cdot 3} miles more, for a total now of

\left[800+800^2+\frac{799\cdot 800^2}{2}+\frac{798\cdot 799 \cdot 800^2}{2\cdot 3}\right] \text{ miles}.


Then adding 797 miles for a fourth of the last additional miles, we get a total of

\left[800+800^2+\frac{799\cdot 800^2}{2}+\frac{798\cdot 799 \cdot 800^2}{2\cdot 3}+\frac{797\cdot 798\cdot 799\cdot 800^2}{2\cdot 3\cdot 4}\right] \text{ miles}.


We can see that eventually, the numerator will decrease to 0 times the previous additional miles ("Until I would walk 0 additional miles"). Factoring out a 800, we get a total distance of

800\left(1+800+\frac{799\cdot 800}{2}+\frac{798\cdot 799 \cdot 800}{2\cdot 3}+\frac{797\cdot 798\cdot 799\cdot 800}{2\cdot 3\cdot 4}+\cdots +\frac{2\cdot 3\cdot \cdots \cdot 798\cdot 799\cdot 800}{2\cdot 3\cdot 4\cdot \cdots \cdot 798\cdot 799}+\frac{1\cdot 2\cdot 3\cdot \cdots \cdot 798\cdot 799\cdot 800}{2\cdot 3\cdot 4\cdot \cdots \cdot 798\cdot 799\cdot 800}\right).


(The next term would be when he reached 0 times the previous additional miles.)
The above can also be written as

800\left( \frac{800!}{(800-0)!0!}+\frac{800!}{(800-1)!1!}+\frac{800!}{(800-2)!2!}+\frac{800!}{(800-3)!3!}+\frac{800!}{(800-4)!4!}+\cdots +\frac{800!}{(800-800)!800!}\right).


Does that look familiar? That's right, it's the Choose function, also known as the binomial coefficient. Then this summation becomes

800\sum\limits_{i=0}^{800}{800 \choose i}.


Notice that the sum of the numbers on any row of Pascal's triangle (values along row k for k\choose i, starting at k=0) is a power of two:

1=2^0

1+1=2^1

1+2+1=2^2

1+3+3+1=2^3

1+4+6+4+1=2^4

\text{and so on...}.

This can be proven by the binomial expansion of (1+1)^k:

2^k=(1+1)^k=\sum\limits_{i=0}^{k}{k\choose i}.


Therefore, how far Derek would walk can be written more succinctly.

800\sum\limits_{i=0}^{800}{800\choose i}=800\cdot 2^{800}.


So Derek would walk 800\cdot 2^{800}\approx 5.334\times 10^{243} miles.

Who gets the girl?

5.334\times 10^{243} > 7.018\times 10^{219}.

Therefore, Derek gets the girl and would walk (800\cdot 2^{800}-500e^{500}) miles more than Robert would walk.