HMMT 二月 2016 · COMB 赛 · 第 5 题

HMMT February 2016 — COMB Round — Problem 5

Let a , b , c , d , e , f be integers selected from the set { 1 , 2 , . . . , 100 } , uniformly and at random with replacement. 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?

解析

Let a , b , c , d , e , f be integers selected from the set { 1 , 2 , . . . , 100 } , uniformly and at random with replacement. 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 63 Answer: 2 Consider M in binary. Assume we start with M = 0, then add a to M , then add 2 b to M , then add 4 c to M , and so on. After the first addition, the first bit (defined as the rightmost bit) of M is 1 toggled with probability . After the second addition, the second bit of M is toggled with probability 2 1 1 . After the third addition, the third bit is toggled with probability , and so on for the remaining 2 2 1 th three additions. As such, the six bits of M are each toggled with probability - specifically, the k 2 1 th bit is toggled with probability at the k addition, and is never toggled afterwards. Therefore, each 2 1 residue from 0 to 63 has probability of occurring, so they are all equally likely. The expected value 64 63 is then just . 2