Of Sets and Sums

We follow Owen's solution up until the bashy sum, and instead of using Wolfram-Alpha, we can use arithmetico-geometric series manipulations. Let $x = 1 \cdot 2^0 + 2\cdot 2^1 + 3 \cdot 2^2 + \ldots + 9 \cdot 2^8 + 10 \cdot 2^9$ Then $2x = 1 \cdot 2^1 + 2 \cdot 2^2 + 3 \cdot 2^3 + \ldots + 9 \cdot 2^9 + 10 \cdot 2^{10}$ So $2x - x = -1 \cdot 2^0 + 1 \cdot 2^1 - 2 \cdot 2^1 + \ldots + 9 \cdot 2^9 - 10 \cdot 2^9 + 10 \cdot 2^{10}$ We see that stuff cancels out to give us a nice geometric series: $x = -1 - 2 - ... -2^9 + 10 \cdot 2^{10}$ $= 1 - 2^{10} + 10 \cdot 2^{10}$ $= 9 \cdot 1024 + 1$ $= 9217$ But we only want the last three digits $\rightarrow \boxed{217}$

We shall consider some cases.

Since $10$ is the greatest number in the whole set, every subset in which $10$ appears will have $M = 10$ . Fixing $10$ , we have $2^9$ subsets which contain it. Here we use the fact that the power set of any set of $n$ elements has $2^n$ subsets.

Now, we have to count the number of subsets in which $9$ appears, but $10$ does not. By the same argument, there are $2^8$ of such subsets.

Continuing like this, we generate the number of subsets which contain $8$ but lack $9$ and $10$ , and so on.

Finally, we have to multiply the number of subsets times their $M$ , and sum these expressions.

Thus, the total sum is

$10 * 2^9 + 9 * 2^8 + 8 * 2^7 + ... + 2*2^1 + 1*2^0 + 0 = 9217$

Since we only require the last three digits, the answer is $217$