Consider the set $$S=\{1,2,3,4,5,\ldots,123456789\},$$ which consists of all positive integers whose digits strictly increase from left to right. This set is finite. What is the median of the set?
Like ... how do I start? I thought it would be 512 (which is clearly wrong).
On
Let's count the cardinality of $S$. For each digit $1$ to $9,$ if it is part of a given number, its position is fixed. That is, if I know that a certain number in $S$ contains the digits $1,2,3,5,7,$ and no others, then the only element of $S$ satisfying this is $12357.$ Then $|S|=2^{9}-1=511,$ since I have $2$ options for every digit (in the number or not), and $9$ digits, but I cannot have a number with no digits.
The median is then the number in the $2^{8}=256$ position in this list. I observe that there is only $1$ $9$-digit number, there are $9$ $8$-digit numbers, there are $\binom{9}{2}=36$ $7$-digit numbers, and similarly there are $\binom{9}{k}$ $(9-k)$-digit numbers, for $k=0$ to $8$ (just choose which digits to leave out).
Observe that the count of all numbers in $S$ with $5$ or more digits is then equal to $\sum_{k=0}^{4}\binom{9}{k}=256,$ and $255=\sum_{k=5}^{8}\binom{9}{k},$ the count of all numbers in $S$ with $4$ or fewer digits. Therefore the median is the smallest $5$-digit number, or $12345$.
Hint:
Assuming that the numbers in the set are ascendantly ordered the counts of $x$-digit numbers can be symbolically presented as
$$ \binom{9}{1},\binom{9}{2},\binom{9}{3},\binom{9}{4},\binom{9}{5},\binom{9}{6},\binom{9}{7},\binom{9}{8},\binom{9}{9}. $$
We see that the median of the set is the first 5-digit number. What is it?
Comment:
If $\binom{9}{0}$ were present (and the cardinality of the set were the even number $2^9=512$), the virtual "median" would be exactly between $\binom{9}{4}$ and $\binom{9}{5}$. But the numbers consisting of 0 digits do not exist. Therefore the median shifts one position to the right from its virtual value.