, 2019

$$\frac{100}{100}+\frac{100}{99}+\cdots+\frac{100}{1} \approx 100 \ln 100$$
stone throws (it takes $\frac{100}{100-k}$ moves on average to get a stone into a new section if $k$ sections already have a stone). So the answer is at least $100 \ln 100 \approx 450$.

On the other hand, if we divide the river into 200 2-foot sections, then once we have a stone in each section we are guaranteed to be able to cross. By a similar argument, we obtain that the answer is at most $200 \ln 200 \approx 1050$.

Estimates near these bounds earn about 5 to 7 points. An estimate in between can earn close to 20 points.

To compute the answer (almost) exactly, we use the following argument.

Scale the problem so the river is of size 1, and the jumps are of size 0.01. Suppose that after $n$ throws, the stones thrown are located at positions $0 < x_{1} < x_{2} < \cdots < x_{n} < 1$. Let $x_{0} = 0$, $x_{n+1} = 1$, $r = 0.01$. Define $P(n)$ to be the probability that you still cannot cross the river after $n$ throws. In other words, there exists $i$ such that $x_{i+1} - x_{i} > r$. Then our answer is $\sum_{n=0}^{\infty} P(n)$.

By PIE we can write
$$P(n) = \sum_{i=1}^{\infty} (-1)^{i-1} \binom{n+1}{i} \max (1 - i r, 0)^{n}$$
based on which intervals $x_{i+1} - x_{i}$ have length greater than $r$. Now we switch the order of summation:
$$\sum_{n=0}^{\infty} P(n) = \sum_{n=0}^{\infty} \sum_{i=1}^{\infty} (-1)^{i-1} \binom{n+1}{i} \max (1 - i r, 0)^{n} = \sum_{i=1}^{\infty} (-1)^{i-1} \sum_{n=0}^{\infty} \binom{n+1}{i} \max (1 - i r, 0)^{n}$$
Let $x = \max (1 - i r, 0)$. Then
$$\sum_{n=0}^{\infty} \binom{n+1}{i} x^{n} = x^{i-1} \sum_{j=0}^{\infty} \binom{i+j}{i} x^{j} = \frac{x^{i-1}}{(1-x)^{i+1}}$$
Thus, our answer is
$$\sum_{i=1}^{\lfloor 1 / r \rfloor} (-1)^{i-1} \frac{(1 - i r)^{i-1}}{(i r)^{i+1}} \approx 712.811$$
where the last approximation uses the C++ code below.

```
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
int main() {
ld sum = 0, r = 0.01;
for (int i = 1; ; ++i) {
ld x = 1-r*i; if (x <= 0) break;
ld ex = pow(x/(1-x),i-1)/(1-x)/(1-x);
if (i&1) sum += ex;
else sum -= ex;
}
cout << fixed << setprecision(8) << sum;
}
```