$11,\ldots,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?
-
- Write out the integers from
$1$to$5$in binary. - Alice is thinking of a number from
$1$to$32$inclusive. You may guess the number and she will tell you whether your guess is greater than the number. How many guesses do you need in the worst case?
- Write out the integers from
-
If the database only had two numbers, how many queries would you need?
-
How can you find the position of two numbers with one query, and why would a single query imply the position of both numbers?
-
How would you use the above strategy to resolve 4 numbers?
-
… how about a divide and conquer approach?
-
… that is, break down this problem into two sub-problems.
-
… you could try to order the two halves, then order the numbers within each half (recall that you can query multiple indices in the same question).
-
… is it possible to do the former using one query, and the latter also using one query?
-
How would you use this approach for larger sets of numbers?
-
The underlying principle is in fact straightforward (divide and conquer): deduce the order of 2 items by querying the position of only one (the other is found by elimination). This is then applied recursively.
When dealing with more than
$2$numbers, split them in two groups of$\frac{n}{2}$numbers and apply the above principle. Then split each group in two sub-groups each of$n/4$numbers and apply the same principle, and so on, until the groups contain only two numbers.Example: For 4 numbers, a first query resolves the ordering of the groups
$\{1,2\}$and$\{3,4\},$and a second query resolves the ordering within each group - recall you can ask for multiple indices. Specifically, first ask for indices$3,4$(resolving the ordering of the groups$\{1,2\}$and$\{3,4\}$- each scrambled at this point) then ask for the indices 2,4 (resolving the ordering of all indices 1,2,3,4 since the queried index 2 resolves the ordering within the group$\{1,2\}$and the queried index 4 resolves the ordering within the group$\{3,4\}).$In our case of 8 numbers we only need 3 queries, as depicted in the following table (where “x” denotes a queried position)
position 1 2 3 4 5 6 7 8 q1 x x x x q2 x x x x q3 x x x x You may recognize the first 8 binary numbers starting with 0. In general we need
$\lceil\log_2(n)\rceil$questions for$n$positions, where$\lceil\cdot\rceil$is the ceiling function.