Expected number of paths

Let $N_s$ be the number of paths in $P$ which contain $s$ . We want $E[N_s]$ .

Count the number of (path,point) pairs $(p,s) \in P \times S$ such that $p$ contains $s$ .

There are $8 \cdot 8 = 64$ points in the grid, each having $N_s$ paths through it.

So, the total number of (path,point) pairs is $\sum_{s \in S} N_s = 64E[N_s]$ .

Every path takes $7$ right steps and $7$ up steps in some order.

There are $\binom{7+7}{7} = 3432$ such paths, each with $7+7+1 = 15$ points on it.

So, the total number of (path,point) pairs is $3432 \cdot 15 = 51480$ .

However, both methods must yield the same number of (path,point) pairs.

Thus, $64E[N_s] = 51480 \leadsto E[N_s] = 804+\dfrac{3}{8} \leadsto a+b+c = \boxed{815}$ .

$E()= \sum_{i=1}^{64}P(i)*$ (paths through i)

P(i)=1/64 for all points

Total no. of paths from bottom left corner to top right corner is $\dbinom{14}{7}$

Each path goes through 15 points.

$E()=1/64\sum_{i=1}^{64}$ (paths through i)

$\sum_{i=1}^{64}$ (paths through i)=total paths*no of points across each path= $\dbinom{14}{7}*15$ (This is because each path will add 1 each to 15 different points )

Thus the ans. is $1/64*\dbinom{14}{7}*15=804+3/8$

At any time, the remaining distance to the top right hand corner will be an integer, say $N$ . Since our grid is $8\times 8$ we have $0 \leq N \leq 14$ . At each possible distance, the total number of paths to the top right hand corner will equal the total number of paths in $S$ which is $\left( \begin{array}{c} 14 \\ 7 \end{array} \right) = 3432$

Since we have $15$ possible distances and the number of paths at each distance is $3432$ counting the total number of paths through any intersection gives $15 \times 3432$ .

Since we had $8 \times 8 = 64$ intersections the expected number of paths is $\frac{3432 \times 15}{64} = 804+\frac{3}{8}$ and thus our answer is $804 + 3 + 8 = \boxed{815}$

The number of paths is the no. of arrangements of 7 N and 7 E s, which is $\binom{14}{7}$ , If we tilt our diagram 45 degress clockwise, we will have 15 rows. Each row will contain the same total no. of paths, since every path from its neighboring row must intersect this row. Hence, expected no. of paths= $\frac{15\times \binom{14}{7}}{64}$ . Ans= $815$

$a + \frac{b}{c}$ = $\frac{\#\_of\_streets \times \#\_of\_points\_per\_street}{\#\_of\_points}$

# of streets = ${14 \choose 7}$

# of points per street = 15

# of points = 64

$\frac{{14 \choose 7} \cdot 15}{64} = \frac{3432 \cdot 15}{64} = \frac{429 \cdot 15}{8} = \frac {6435}{8} = 804 + \frac{3}{8}$

$804+3+8 = \boxed{815}$

{

public static double factorial(int n) {
    double result = 1;
    for (int i = n; i >= 2; i--) {
        result *= i;
    }
    return result;
}
public static void main(String[] args) {
    double sum = 0;
    for (int i=1; i<=8; i++) {
        for (int j=1; j<=8; j++) {
            sum += factorial(i+j-2)*factorial(16-i-j)/(factorial(i-1)*factorial(j-1)*factorial(8-i)*factorial(8-j));
        }
    }
    System.out.println(sum/64);
}

}

sum/64 = 804.375 = 804 + 3/8 = a + b/c => a+b+c = 815