Help Please

Notations: We use the following notation \(\displaystyle \binom{n}k\) to mean \(\displaystyle \binom{n}k = C^n_k\).

Note that \(\displaystyle \binom{20}{10} = 184756\) so all possible paths are exhausted by the penguins.

There is an important observation in all 4 problems, which I will state below:

Observation:

Let \((x, y)\) be a lattice point, with \(0 \leq x \leq 10\), \(0 \leq y \leq 10\).

Each path that passes through this lattice point must start with a sequence of x + y moves,

consisting of x moves to the right, and y moves upwards, in some order.

By observation, to count the number of path passing through (x, y), we are counting the number of permutations of x (indistinguishable) right moves and y (indistinguishable) up moves. That number is \(\displaystyle \binom{x + y}{x}\). From there, we move from (x, y) to (10, 10) by 10 - x right moves and 10 - y up moves. By the same logic, there are \(\displaystyle \binom{(10 - x) + (10 - y)}{10 - x} = \binom{20 - x - y}{10 - x}\) ways to move from (x, y) to (10, 10). 

Therefore, by basic principles of combinatorics, there are \(\displaystyle \binom{x + y}x \cdot \binom{20 - x - y}{10 - x}\) different paths that passes through \((x, y)\).

With this in hand, the problems are easily solved.

Problem 1

The total sum is \(\displaystyle \binom{7 + 10}{7} \cdot \binom{20 - 7 - 10}{10 - 7} + \binom{8 + 9}8 \cdot \binom{20 - 8 - 9}{10 - 8} + \binom{9 + 8}{9} \cdot \binom{20 -9-8}{10-9} + \binom{10 + 7}{10} \cdot \binom{20 -10- 7}{10-10}\), which is 184756. 

Seeing this answer, you may think there is an easier way to do this. In fact, there is. Note that for each penguin, after 17 moves, one of the 4 points must be reached. From each of the 4 points, the other 3 points cannot be reached. Therefore, each penguin passes through one and only one penguin counter. Therefore the answer is exactly the number of penguins we have.

Problem 2

From the observation in Problem 1, if you fix a number k such that \(0 \leq k \leq 20\) and place counters on each point (x, y) such that \(x + y = k\), every penguin will be counted exactly once. (In Problem 1, the case k = 17 is shown. )

The problem then becomes "how many ways are there to choose 2 integers from 0 to 20 inclusively", which is \(\displaystyle \binom{21}2 = 210\).

Problem 3

The expected sum is 11 times the average number of paths passing through a point, i.e., in summation notation, \(11 \cdot \dfrac{\displaystyle \sum_{x = 0}^{10} \sum_{y = 0}^{10} \binom{x + y}x \binom{20 -x-y}{10-x}}{11^2}\)

While it may seem intimidating, there is a clever way to calculate the double summation \(\displaystyle \sum_{x = 0}^{10} \sum_{y = 0}^{10} \binom{x + y}x \binom{20 -x-y}{10-x}\). From the observation in Problem 2, the sum of counters over the lattices points with \(x + y = k\) is just the total number of penguins, where \(0 \leq k \leq 20\) is a fixed constant. Therefore, the sum is equal to \(\displaystyle\sum_{k = 0}^{20} 184756 = 21(184756) = 3879876\). Now we substitute into the formula and get the expected sum to be \(\dfrac{3879876}{11} = \boxed{352716}\).

Problem 4

The answer is just \(\displaystyle \sum_{x = 4}^{4} \sum_{y = 0}^{10} \binom{x + y}x \binom{20 -x-y}{10-x} = \sum_{y = 0}^{10} \binom{4 + y}4 \binom{16 - y}{6}\). I will let you figure out the rest.