Problem 15 Solution: "For Science"

Specify a bijective mapping that associates each possible ordering with an integer in the range [1,24]. It does not matter how you do this; one way is in lexicographic order (say the wormholes are marked A, B, C, D, then you would have 1 = ABCD, 2 = ABDC, 3 = ACBD, 4 = ACDB, etc). Then you can use binary search to find the correct number by asking questions of the form "Is the number corresponding to the correct ordering less than or equal to X?"

Since there are 24 possibilities, this takes ceil(log_2(24)) = 5 questions.

The generalization is obvious - if there are N wormholes then you map each possible ordering to an integer int he range [1,N!], and so the algorithm takes ceil(log_2(N!)) = O(n log n) questions.

The proof of optimality is easy: If there are k questions, then the number of possible ways of answering those questions is at most 2^k, so if 2^k < N! (which happens if k < log_2(N!)) there is no possible way of distinguishing between the N! possibilities using just the k questions.

[The trick to this question is that you get to ask *any* yes-or-no question; you are not limited to questions of the form "Does X come before Y" that most sorting algorithms use. As an aside, the proof of optimality above is also the standard argument use to show that no comparison-based sorting algorithm can run in better than O(n log n) time.]