In The Library of Babel, there are all the possible 410-page books of a certain format and character set.
There is a legendary book, called a total book, which is supposed to be the catalogue of the library. Now, this is clearly absurd, since any catalogue of the library must contain more information than a mere 410-page book could contain. In fact, since the library has 0 information, to merely write down the address of a certain book takes as much information as the amount of information in that book. Thus, in general, the address of any book is as long as the book itself (410 pages long), and such a total book cannot exist.
But let's suppose it does.
In the story, people have searched for such a book, in vain. So they decided to search for the book indirectly:
How could one locate the venerated and secret hexagon which housed Him? Someone proposed a regressive method: To locate book A, consult first book B which indicates A's position; to locate book B, consult first a book C, and so on to infinity …
I thought "obviously this can't work! It's just self-handicapping an informationless random search, you can't do better that way!"
But then I remembered the 100 prisoners problem, and thought perhaps this method could work.
So here's my problem:
Consider a list (representing the library) of length $N$, and each element (representing a book) is a number between $1$ and $N$ (representing what that book refers to). One of these elements is chosen as special (representing that total book).
Two players are tasked with searching for the book. One player simply searches from the beginning and thus would expect to take $N/2$ steps to find the special element. The other "follows the leads" in each element, and if he finds himself directed to a previously visited element, he would instead search the least unvisited element.
How long would the second player take? I expect it to be $N/2$, since obviously this strategy doesn't work. But then, how is it that this strategy does work in the 100 prisoners problem?
Best Answer
It does not matter what order you search the books in; the expected time it takes to find the special book is always $(N+1)/2$. No matter what, the first book you check is equally likely to be any number between $1$ and $N$, and the second book is equally likely to be any number unequal to the first book, and in general the $k^{th}$ book is equally likely to be anything unequal to the first $(k-1)$ books.