Let $a,b,c,d,e,f$ be integers selected from the set $\{1,2,\cdots, 100\}$ uniformly and at random with replacement. Let $M=a+2b+4c+8d+16e+32f$. What is the expected value of the remainder when $M$ is divided by $64$?
Let $f_n(x)$ be the remainder when $x$ is divided by $2^n$. Then we are interested in finding $E(f_6(M))$. Since both the expected value and $f_n$ are linear, we can find the expected value of each term and then sum them together in the end to get the answer.
Now $$E(f_6(a))=\sum_{k=1}^{100}f_6(k)\cdot \frac{1}{100}=26.82$$.
Now since $ac\equiv bc \pmod{nc}$ iff $a\equiv b\pmod{n}$, we can calculate
$$E(f_6(2b))=2\cdot E(f_5(b))=2\cdot \sum_{k=1}^{100}f_5(k)\cdot \frac{1}{100}=29.96$$
And similarly $E(f_6(4c))=29.2, E(f_6(8d))=27.68, E(f_6(16e))=24, E(f_6(32f))=16$ and hence $E(f_6(M))=5456 \pmod{64}=16$.
But this is a question from a math competition training set, so I suspect there is a much quicker and elegant way to solve it, is there such a way? Thanks in advance.