Bookshelf problem

Question

There is this thought problem I've been trying to solve, it goes as follows

Imagine a bookshelf with a finite number of books in it, to which a finite number of people have access. Each person has a paper and pen where they can keep track of what books they have already read. the books have no covers, so in order to find out if you have read it you must take it out and open it.

What is the most effective method each person can use to find a book they haven't read before?

conditions:

• You cannot change the order of the books in the bookshelf (you can however order the bookshelf into blocks/sections)
• The bookshelf - and its order - is the same for all people

edit:

• The bookshelf can also have new books added, so the system must be able to adapt to that,
• books can get stolen too. so a missing index can appear.

For example we can let each person take a book at random, then check on their list if they have read this book before, this will work. but once you reach the 900th/1000 book, you need to take 10 books in order to be able to read one.

Another example is where everyone writes down what they read, but after a few 100 books this gets rather slow. since you need to keep checking a list of 500 before you can pick one.

Answer 1

I would say that writting on the spine solves the problem, not avoids it. However, given your attitude, let me ask this question: is it possible to make an index? That is, if it is not allowed to write on spines, you could write on paper, everybody can count books and bookshelves (and if you can't write on paper you could do a "spoken index").

If yes, then just go through the index (make many copies) and the problem is solved (indirect references are a common way in computer science).

If no, then the readers are independent of each other but for making some books unavailable to others at some particular time. Then, let $n$ be the number of readers. Split the books into $n$ shelves and make a rule that reader $i$ at time $t$ can read only from shelf $(i+t) \bmod n$ (so there are no collisions). Then for every reader assign a random permutation of books "to read", and at any given time the reader would be to read first available book from the list (and of course, remove it from the list afterwards). After any new book has been added, put it into the remaining list of all the readers and reshuffle them all (lists, not readers).

Is this close to what you want?

Answer 2

All jokes aside (see comment on OP)...

Let the people be numbered $P_1, P_2, P_3,\ldots$ and the books $B_1, B_2, B_3, \ldots$

If we have $P_n$ start on book $B_n$, the next book they have not yet read is book $B_{n+1}$. If this book does not exist, wrap around to the start of the shelf.

Essentially, have each person start with a different book, and move down the shelf one-by-one.

No unnecessary books are opened, so this is optimal.