= Solution
Use <binary search>: maintain the interval of possible integers and ask whether $n$ is at least the first integer in its upper half. Each answer reduces the number of possibilities to at most its previous number divided by two, rounded up. After $q$ questions at most $\lceil10^6/2^q\rceil$ possibilities remain. Since $2^{20}=1\,048\,576>10^6$, \b[twenty questions suffice].
A yes/no <decision tree> of depth twenty has at most $2^{20}$ leaves, whereas the possible finishing orders number $15!=1\,307\,674\,368\,000$. Thus \b[twenty questions cannot identify the finishing order of fifteen horses], assuming no ties. With unrestricted yes/no questions, the exact minimum for $n$ horses is $\lceil\log_2(n!)\rceil$: the leaf count is a lower bound, and repeatedly partitioning the remaining <permutations> into two nearly equal sets attains it. In particular fifteen horses require 41 questions.
By <Stirling's formula>,
$$
\boxed{\log_2(n!)=n\log_2n-(\log_2e)n+\frac12\log_2(2\pi n)+O(n^{-1}),}
$$
so the leading number of questions is $n\log_2n$. These questions may ask about whole sets of possible orders; restricting them to pairwise comparisons is a different model.
Back to article page
