A probability problem by Muhammad Alif

WLOG, let $a < b < c$ . Suppose $c = n, n \in \mathbb{N}, n \ge 2$ . Then the largest integer that we can form will be $2^{n-2} + 2^{n - 1} + 2^n = 7 \cdot 2^{n - 2} < 2^{n + 1}$ . This means that every integer we can form with $c = n$ will be less than any integer we can form with $c = n + 1$ . By similar reasoning, for a fixed value of $c$ , every integer we can form with $b = k, k \in \mathbb{N}, k \ge 1$ will be less than any integer we can form with $b = k + 1$ .

Therefore, we can order the integers in $S$ first in increasing order of $c$ , then in increasing order of $b$ , and finally in increasing order of $a$ . Specifically,

$(2^0 + 2^1 + 2^2) < (2^0 + 2^1 + 2^3) < (2^0 + 2^2 + 2^3) < (2^1 + 2^2 + 2^3) < (2^0 + 2^1 + 2^4) < \ldots < (2^{n - 2} + 2^{n - 1} + 2^n) < (2^0 + 2^1 + 2^{n + 1}) < + \ldots$

For any $c$ , $a$ and $b$ can take on any two values from $\{0, 1, 2, \ldots, c - 1\}$ , so there are $\dbinom{c}{2}$ possible sets of values for $a$ and $b$ . Then the total number of integers with $c \le n$ will be $\displaystyle \sum_{c = 2}^n \dbinom{c}{2}$ ; we look for the largest $n$ such that $\displaystyle \sum_{c = 2}^n \dbinom{c}{2} \le 100$ . A little trial and error gives us $n = 8$ , for which $\displaystyle \sum_{c = 2}^8 \dbinom{c}{2} = 84$ .

${\color{#FFFFFF} \text{filler}}$

We need sixteen more numbers, all of which will have $c = 9$ . Now for any $b$ , $a$ can take on any value from $\{0, 1, 2, \ldots, b - 1\}$ , so there are $b$ possible values for $a$ . Then the total number of integers with $c = 9$ and $b = k$ will be $\displaystyle \sum_{b = 1}^k b$ ; we look for the largest $k$ such that $\displaystyle \sum_{b = 1}^k b \le 16$ , and we quickly find $k = 5$ , for which $\displaystyle \sum_{b = 1}^5 b = 15$ .

${\color{#FFFFFF} \text{filler}}$

This gives a total of $99$ integers, the last of which is $2^4 + 2^5 + 2^9$ . Therefore the $100$ th integer will be the first one with $c = 9$ and $b = 6$ , i.e. $2^0 + 2^6 + 2^9 = \boxed{577}$

There is a one-to-one correspondence between the elements of $S$ and the set of binary strings consisting of three $1$ 's with $0$ 's in the remaining bits.

Now since $\dbinom{9}{3} = 84$ and $\dbinom{10}{3} = 120$ we know that the 100th smallest element will have a $1$ in the 10th bit from the right, i.e., in the $2^{9}$ bit. Next, since $\dbinom{6}{2} = 15$ we know that the 85th to 99th smallest elements of $S$ will have the second $1$ in the 6th bit from the right, and thus the 100th smallest element will have the second $1$ in the 7th bit from the right and the third $1$ in the rightmost bit, resulting in the 100th smallest element of $S$ being $2^{9} + 2^{6} + 2^{0} = 512 + 64 + 1 = \boxed{577}$ .