Expected value of the remainder when a random variable is divided by a number

Question

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.

Answer 1

I think there would have been a highschool math solution to this problem if the integers were instead drawn uniformly from $\left\{ 1,2,3...64\right\} $ . Then, regardless of the remainder stemming from $2b+4c+8d+16e+32f$, the $a$ -term would make the final remainder uniformly drawn from $\left\{ 0,1,2...63\right\} $. Why? Say e.g. that the remainder from $2b+4c+8d+16e+32f $ happens to be $15$. If we then draw $a=49$ the final remainder will be $0$ ; if we draw $a=50$ the final remainder will be $1$; if we draw $a=51$ the final remainder will be $2$ and so on with equal chance for all potential outcomes. And this logic goes through regardless of what the remainder from $% 2b+4c+8d+16e+32f$ happen to be. So the expected remainder would then be $% 63/2=31.5$. The same logic would apply if the integers were drawn from $% \left\{ 1,2,3...64N\right\} $. But I can't see any way of extending this line of reasoning to the case when all integers are drawn from $\left\{ 1,2,3...100\right\} $.