The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

Practice Paper 2 Question 16

The eight numbers \(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?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. Write out the integers from \(1\) to \(5\) in binary.
  2. 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?

Hints

  • Hint 1
    If the database only had two numbers, how many queries would you need?
  • Hint 2
    How can you find the position of two numbers with one query, and why would a single query imply the position of both numbers?
  • Hint 3
    How would you use the above strategy to resolve 4 numbers?
  • Hint 4
    ... how about a divide and conquer approach?
  • Hint 5
    ... that is, break down this problem into two sub-problems.
  • Hint 6
    ... 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).
  • Hint 7
    ... is it possible to do the former using one query, and the latter also using one query?
  • Hint 8
    How would you use this approach for larger sets of numbers?

Solution

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.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.