Problem 1

Arpit has 184756 penguins that waddle a unique lattice path from (0,0) to (10,10) on the coordinate plane (penguins only take unit length steps up or to the right). Arpit also has many penguin counters that he can place at any point on the grid (including (0,0) and (10,10)). Each counter counts how many penguins visit its location during their waddles.

Arpit places counters on (7,10), (8,9), (9,8), and (10,7). What will the total sum of the 4 counters be?


Problem 2

How many ways can Arpit place counters such that each penguin is counted exactly twice?

Problem 3

Arpit uniformly randomly chooses 11 distinct integer coordinates (x,y) satisfying 0≤x,y≤10 to place counters. What is the expected sum of the 11 counters?


Problem 4

Arpit places counters on (4,0), (4,1), ..., (4,10). What will the total sum of the 11 counters be?

 Apr 8, 2024
edited by Mather459  Apr 8, 2024

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:


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.

 Apr 9, 2024

Max, your monographic summary analysis on binomial theory is amazing! It’s one of the best I’ve read anywhere. 

It’s wonderful you have returned! I hope you stay around for awhile.I Really Do!


I will let you figure out the rest.


I don’t know if the OP student will choose to figure out the rest, but I sure as hell will.


You may find this formula interesting.

\(\sum \limits_{k=0}^{m}\binom{n}{k} (-1)^k \binom{p – s*k – 1}{p – s*k – n} \leftarrow \text {where p is the point (sum) target, n is the # of die, }\\ \hspace {47mm} \text{s is the number of sides, and } m=\lfloor \dfrac{p-n}{s}\rfloor \\\)

This formula is from J. V. Uspensky’s Introduction to Mathematical Probability (1937).

This calculates the number of combinations for any given sum of pips on (N) number of dice with (S) sides, where each die-side has a unique number of pips from 1 to (S)


I posted it as part of a rhetorical troll post here:  https://web2.0calc.com/questions/counting-question#r17




--. .-

GingerAle  Apr 10, 2024
edited by GingerAle  Apr 10, 2024
edited by GingerAle  Apr 10, 2024
edited by GingerAle  Apr 10, 2024

4 Online Users