Austria competition problems, 2010

If $k$ is the largest element of an outstanding subset $S$, it follows that $S$ must contain $k$ elements. This is possible if it either contains all elements not greater than $k$ or all but one. We see that each outstanding subset of $M_n$ corresponds to an ordered pair $(a, b)$ of integers with $n \ge a \ge b \ge 0$, whereby the case of an $a+1$ element subset with maximum element $a$ is denoted by the pair $(a, a)$ and an $a$ element subset with maximum element $a$ and missing the number $b$ is denoted by $(a, b)$. We also note that each such pair corresponds directly to an outstanding subset. The number of outstanding subsets is therefore equal to the number of ordered pairs of this type. This number is equal to the number of 2-element subsets of $M_n$ plus the number of elements of $M_n$. We see that the number of outstanding subsets is equal to
$$\binom{n+1}{2} + (n+1) = \binom{n+2}{2}$$