, 2024

Solution:
Note that we can just take averages: every time you draw one of two cards, the expected value of the resulting card is the average of the expected values of the two cards. This average must be of the form
$$2^{\bullet} \cdot 1 + 2^{\bullet} \cdot 2 + 2^{\bullet} \cdot 3 + \cdots + 2^{\bullet} \cdot 100$$
where the $2^{\bullet}$s add up to $1$. Clearly, the cards further down in the deck get involved in one less layer of averaging, and therefore $1$ through $72$ are weighted $2^{-7}$ while the rest are weighted $2^{-6}$. To compute the average now, we just add it up to get $\frac{467}{8}$.

Solution:
We see that in a deck with $2^{n}$ cards, after repeating the process $2^{n-1}$ times, each card has a chance of $\frac{1}{2}$ of remaining in the deck. This means that the average of the cards in the deck doesn't change between $2^{n}$ and $2^{n-1}$ cards. Thus, by repeating this process, we determine that the expected value of the last card is the average of all cards whenever we start with $2^{n}$ cards.

Suppose we instead start with $2^{7} = 128$ cards in the following order:
$$73, 73, 74, 74, \ldots, 100, 100, 1, 2, 3, \ldots, 72$$
Thus, after $28$ steps, we will be left with the original configuration. Since a power of $2$ cards are in the deck, we expect that the final card will be the average of these numbers. This is $\frac{467}{8}$.