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.

  • 2
    $\begingroup$ I think the claim that $f_n$ is linear is problematic. For instance $0 = (4 \text{ mod } 4) \neq 2\cdot (2 \text{ mod }4) = 4$. $f_n$ is only linear mod $2^n$. $\endgroup$ Nov 25 '21 at 9:24
  • $\begingroup$ @Ishigami Where does $5456$ in $E(f_6(M)) = 5456 \pmod{64}$ come from? $\endgroup$
    – VTand
    Nov 26 '21 at 1:47

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\} $.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.