 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ib/paper-2/20h/iii/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

Measure vertices by their Hamming distance from the target and let

h_{k}

k

. We already know

h_{1} = 2^{n} - 1

. From distance one, one of the

n

coordinate flips reaches the target and the other

n - 1

flips move to distance two. First-step analysis therefore gives

h_{1} = 1 + \frac{1}{n} h_{0} + \frac{n - 1}{n} h_{2}, h_{0} = 0.

For

n \geq 2

h_{2} = \frac{n}{n - 1} (h_{1} - 1) = \frac{n ( 2 ^{n} - 2 )}{n - 1} .

 New to topics? Read the docs here!