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?
(1) I would also expect the second player to take $N/2$ steps, but I cannot think of any easy proof. EDIT @MikeEarnest gave a great short proof, as always. :) Anyway, this isn't important...
(2) The key interesting aspect of the $100$ prisoners problem is IMHO this line in the wikipedia article:
In the prisoners problem, let $A_i$ be the event that prisoner $i$ finds his own number within $50$ boxes. It is still true that $\forall i: P(A_i) = 1/2$.
However, the magic of the cycle-following method is that $A_i$ are highly-correlated events! And why is this important? Because by the definition of the problem, overall success is defined as $\bigcap_i A_i$.
If each prisoner looks randomly, then $A_i$'s are independent, and $P(\bigcap_i A_i) = ({\frac12})^{100} \approx 0$. But the cycle-following method makes $P(\bigcap_i A_i) \approx 0.31$. In both cases, $\forall i: P(A_i) = 1/2$ individually.
BTW since the prisoners are now correlated so that they likely succeed together, this also means they likely fail together. E.g., in the random method, the number of prisoners who found his own number, call it $K$, would be $K \sim Binomial(100, 1/2)$, which is unimodal around $50$ (mean $50$, standard deviation $5$, you get the idea). In contrast, in the cycle-following method, $K$ would be very bimodal. In both cases $E[K] = 50$. However, by the problem definition, you don't care about the value of $K$ - except whether it is $= 100$ or $<100$. Informally speaking, failing a little is just as bad as failing catastrophically, and that is due to the definition of success as $\bigcap_i A_i$.