HMMT 二月 2016 · COMB 赛 · 第 5 题

英文解析

5. Let a , b , c , d , e , f be integers selected from the set { 1 , 2 , . . . , 100 } , uniformly and at random withreplacement. Set
   M = a + 2 b + 4 c + 8 d + 16 e + 32 f.
   What is the expected value of the remainder when M is divided by 64?
   Proposed by: Evan Chen
   Answer:63
   Consider M in binary. Assume we start with M = 0, then add a to M , then add 2 b to M , then 2
   add 4 c to M , and so on. After the first addition, the first bit (defined as the rightmost bit) of M istoggled with probability . After the second addition, the second bit of M is toggled with probability 1
   1 12
   . After the third addition, the third bit is toggled with probability , and so on for the remaining
   2 2
   th 1
   three additions. As such, the six bits of M are each toggled with probability - specifically, the kth 12
   bit is toggled with probability at the k addition, and is never toggled afterwards. Therefore, eachresidue from 0 to 63 has probability of occurring, so they are all equally likely. The expected value 12
   6364
   is then just . 2