Paper 1, Section I, G

Coding and Cryptography | Part II, 2011

I think of an integer nn with 1n1061 \leqslant n \leqslant 10^{6}. Explain how to find nn using twenty questions (or less) of the form 'Is it true that nmn \geqslant m ?' to which I answer yes or no.

I have watched a horse race with 15 horses. Is it possible to discover the order in which the horses finished by asking me twenty questions to which I answer yes or no?

Roughly how many questions of the yes/no type are required to discover the order in which nn horses finished if nn is large?

[You may assume that I answer honestly.]

Typos? Please submit corrections to this page on GitHub.