Number of Queries to determine Order of Integers

Question

I have this question as follows:

The eight numbers $11,...,18$ are in a database in some order. You can query any subset of indices, but the reply will be randomly shuffled.

For example, if the order was $17, 12, 13, 16, 11, 15, 14, 18$ and you queried indices $1, 2, 4$, the reply could be $16,17,12$.

What is the minimum number of queries you must make to determine the order of the eight numbers?

I have come up with an empirical answer of $7$ but I have been unable to prove it to myself, hence the question. Many thanks.

Answer 1

You can do it in $3 =\log_2 8$ queries, and this is minimal. For example with the queries:

• 1st: 1,2,3,4
• 2nd: 1,2,5,6
• 3rd: 1,3,5,7

This corresponds to figuring out the binary expansion of the indices of all entries. The 1st entry finds the numbers whose indices have $0$ as first digit, the 2nd finds the numbers whose indices have $0$ as second digit and the 3rd finds the numbers whose indices have $0$ on the third digit.