Philippines Mathematical Olympiad

Solution:

Let $M$ be the average that we are computing. First, there are $\binom{2019}{100}$ ways to choose a 100-element subset. Next, if $x$ is the largest element, then $x \geq 100$, and there are $\binom{x-1}{99}$ subsets having $x$ as the largest element. Hence
$$M=\frac{\sum_{x=100}^{2019} x\binom{x-1}{99}}{\binom{2019}{100}}$$
But note that
$$x\binom{x-1}{99}=100\binom{x}{100}$$
Using this fact and the hockey stick identity, we have
$$\begin{aligned} M & =\frac{100 \sum_{x=100}^{2019}\binom{x}{100}}{\binom{2019}{100}} \\ & =\frac{100\binom{2020}{101}}{\binom{2019}{100}} \\ & =\frac{100 \cdot 2020}{101} \\ & =2000 \end{aligned}$$

Solution:

As in Solution 1, the required average $M$ can be written as
$$\begin{aligned} M & =\frac{\sum_{x=100}^{2019} x\binom{x-1}{99}}{\binom{2019}{100}} \\ & =\frac{100\binom{99}{99}+101\binom{100}{99}+\cdots+2019\binom{2018}{99}}{\binom{2019}{100}} \end{aligned}$$

Way 2.1: Note that
$$\begin{aligned} \binom{2019}{100} M= & 100\binom{99}{99}+101\binom{100}{99}+\cdots+2019\binom{2018}{99} \\ = & 2020\left[\binom{99}{99}+\binom{100}{99}+\cdots+\binom{2018}{99}\right]-\left[1920\binom{99}{99}+1919\binom{100}{99}+\cdots+\binom{2018}{99}\right] \\ = & 2020\left[\binom{99}{99}+\binom{100}{99}+\cdots+\binom{2018}{99}\right] \\ & -\left[\binom{99}{99}+\binom{100}{99}+\cdots+\binom{2018}{99}\right] \\ & -\left[\binom{99}{99}+\binom{100}{99}+\cdots+\binom{2017}{99}\right] \\ & -\cdots-\binom{99}{99} \\ = & 2020\binom{2019}{100}-\binom{2019}{100}-\binom{2018}{100}-\cdots-\binom{100}{100} \\ = & 2020\binom{2019}{100}-\binom{2020}{101} . \end{aligned}$$
where the last two lines follow from the hockey stick identity.
Hence, $M=2020-\frac{\binom{2020}{101}}{\binom{2019}{100}}=2020-\frac{2020}{101}=2000$.

Way 2.2: Let
$$X:=\binom{99}{99}+\binom{100}{99}+\cdots+\binom{2018}{99}=\binom{2019}{100}$$
Then
$$\begin{aligned} \binom{2019}{100} M= & 100\binom{99}{99}+101\binom{100}{99}+\cdots+2019\binom{2018}{99} \\ = & 100\left[\binom{99}{99}+\binom{100}{99}+\cdots+\binom{2018}{99}\right] \\ & +\left[\binom{100}{99}+\cdots+\binom{2018}{99}\right] \\ & +\left[\binom{101}{99}+\cdots+\binom{2018}{99}\right] \\ & +\cdots+\binom{2018}{99} \\ = & 100 X+\left[X-\binom{100}{100}\right]+\left[X-\binom{101}{100}\right]+\cdots+\left[X-\binom{2018}{100}\right] \end{aligned}$$
Thus,
$$\begin{aligned} M X & =100 X+1919 X-\left[\binom{100}{100}+\binom{101}{100}+\cdots+\binom{2018}{100}\right] \\ & =2019 X-\binom{2019}{101} \end{aligned}$$
which gives
$$M=2019-\frac{\binom{2019}{101}}{\binom{2019}{100}}=2020-\frac{2020}{101}=2000$$