Paper 1, Section I, H

Coding and Cryptography | Part II, 2009

I am putting up my Christmas lights. If I plug in a set of bulbs and one is defective, none will light up. A badly written note left over from the previous year tells me that exactly one of my 10 bulbs is defective and that the probability that the kk th bulb is defective is k/55k / 55.

(i) Find an explicit procedure for identifying the defective bulb in the least expected number of steps.

[You should explain your method but no proof is required.]

(ii) Is there a different procedure from the one you gave in (i) with the same expected number of steps? Either write down another procedure and explain briefly why it gives the same expected number or explain briefly why no such procedure exists.

(iii) Because I make such a fuss about each test, my wife wishes me to tell her the maximum number NN of trials that might be required. Will the procedure in (i) give the minimum NN ? Either write down another procedure and explain briefly why it gives a smaller NN or explain briefly why no such procedure exists.

Typos? Please submit corrections to this page on GitHub.