Brilli's triangular search

Split up the route into outgoing and returning portions.

Outgoing: Each of the distances $1,2, ..., 4753$ is equally likely. so the expected outgoing distance is $\frac{1 + 2 + \dots + 4753}{4753} = \frac{4754}{2} = 2377$ .

Returning: Returning from each of the $k$ points on the $k$ th level gives a distance of $k$ , so the expected returning distance is $\frac{1^2 + 2^2 + \dots + 97^2}{4753} = \frac{195}{3} = 65$ .

Thus, the total expected distance is $2377 + 65 = 2442$ .

In general, this works out to $\frac{(n+1)(n+2) + 2}{4}+ \frac{2n+3}{3} = \frac{3n^2 + 17n + 24}{12}$

Let's consider a triangle with side lenght $n$ . Let's define the number of layers $l=n+1$ . So, the total number of points is $\displaystyle p=\frac{l(l+1)}{2}$ . Let's label each point $i$ , $1 \leq i \leq p$ in this way: the point on the summit is $i=1$ , the next point Brilli will visit is $i=2$ , the adjacent one will be $i=3$ and so on. Hence, the total distance travelled if Brilli finds food on point $i$ is

$d_i=i+l_i$

where $l_i$ is the layer point $i$ is on. Since the probability is uniformly distributed, we have $\displaystyle \mathbb{P}(d_i)=\frac{1}{p}$ . Hence,

$\displaystyle \mathbb{E}[d]=\frac{1}{p} \sum_{i=1}^{p} (i+l_i)=\frac{1}{p}\bigg( \sum_{i=1}^{p} i + \sum_{i=1}^{p} l_i \bigg)= \frac{1}{p} \bigg( \frac{p(p+1)}{2} + \sum_{i=1}^{p} l_i \bigg)$

Notice that there is $1$ point on layer $l=1$ , $2$ on layer $l=2$ , $3$ on layer $l=3$ and so on, so

$\displaystyle \sum_{i=1}^{p} l_i = \sum_{k=1}^{l} k^2 = \frac{l(l+1)(2l+1)}{6}$

and

$\displaystyle \mathbb{E}[d]=\frac{p+1}{2} + \frac{l(l+1)(2l+1)}{6p}$

Eventually, for our case $n=96$ , $l=97$ , $p=4753$ , so that

$\displaystyle \mathbb{E}[d]=\frac{4753+1}{2} + \frac{97(97+1)(2\cdot 97+1)}{6\cdot 4753}=\boxed{2442}$

I'll give my solution as a general case for a triangle with side length $n$ .

Define the triangle as a series of rows. Then there are $(n+1)$ rows in the triangle. The first row has one point, and each subsequent row has one more point. Thus, the number of points in the lattice (not including the starting point) is the $(n+1)^{th}$ triangular number: $\frac{(n+1)(n+2)}{2}$ . Therefore, the probability of having food for each point is $\frac{2}{(n+1)(n+2)}$ .

Note that if Brilli gets to a point on the $k^{th}$ row, then he has exactly $k$ spaces to get back to the starting point.

There are $k$ points in the $k^{th}$ row, so the probability of finding food in the $k^{th}$ row is $\frac{2k}{(n+1)(n+2)}$

Let's first find the distance to get to a point in the $k^{th}$ row. The distance to get to the last point in the $(k-1)^{th}$ row is the $(k-1)^{th}$ triangular number: $\frac{k(k-1)}{2}$ . From there, to get to any point on the $k^{th}$ row, Brilli goes a distance anywhere from $1$ to $k$ . Because each point on that row has the same probability of having food, we can simplify things by using the average distance between $1$ and $k$ : $\frac{k+1}{2}$ .

Thus, the total average distance of Brilli's journey if he finds food on the $k^{th}$ row is $\frac{k(k-1)}{2}+\frac{k+1}{2}+k=\frac{k^{2}+2k+1}{2}$

Using the probability for the $k^{th}$ row from before, the expected value of Brilli's journey is: $\frac{1}{(n+1)(n+2)}\sum\limits_{k=1}^{n+1}{(k^3+2k^2+k)}$

$=\frac{1}{(n+1)(n+2)}\bigg[\sum\limits_{k=1}^{n+1}{k^3}+2\sum\limits_{k=1}^{n+1}{k^2}+\sum\limits_{k=1}^{n+1}{k}\bigg]$

$=\frac{1}{(n+1)(n+2)}\bigg[\frac{(n+1)^{2}(n+2)^2}{4}+\frac{2(n+1)(n+2)(2n+3)}{6}+\frac{(n+1)(n+2)}{2}\bigg]$

$=\frac{(n+1)(n+2)}{4}+\frac{2n+3}{3}+\frac{1}{2}$

$=\frac{3n^2+17n+24}{12}$

With $n=96$ , this expression evaluates to $2442$ .

I'd be interested in seeing if anyone comes up with a simpler solution. Also potentially interesting: is it possible for Brilli to take a path that would result in a lower expected distance?