Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Everybody walks up to the bookshelf, and writes each book's title on the spine of said book. –  anorton Feb 15 '13 at 12:06
    
heh, smart but that would be avoiding the problem –  Sam Feb 15 '13 at 12:11
2  
Life is about avoiding problems. –  Gerry Myerson Feb 15 '13 at 12:19
    
This question is extremely underspecified, to the point where there is not going to be any "correct" answer. I am going to remove the "logic" and "algorithm" tags because this is not about mathematical logic nor about "algorithms" in the formal sense. It's just a puzzle. I added the "modeling" tag because the question is so underspecified that the main difficulty is modeling the situation that is described. –  Carl Mummert Feb 15 '13 at 12:52
add comment

2 Answers 2

up vote 1 down vote accepted

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?

share|improve this answer
    
sounds perfect! can't see anything wrong with it. thanks a ton –  Sam Feb 15 '13 at 12:46
1  
and my attitude, I may come across wrong, sorry if that is the case I do really appreciate all the answers and help you guys are giving! –  Sam Feb 15 '13 at 12:49
add comment

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.

share|improve this answer
    
You are assuming everyone reads at the same speed, no? –  user1729 Feb 15 '13 at 12:16
    
Great answer, however this would mean some people are reading all the old books, if a new book is added(B1001) P1 would take ages to get to it. I forgot to mention this in the question. –  Sam Feb 15 '13 at 12:18
    
@user1729 yes everyone is a speed reader, takes them about 2 seconds :) speed is not an issue here. also books can magically be read by 2 people at the same time –  Sam Feb 15 '13 at 12:19
    
You should edit the body of the question so it asks what you actually want to ask. But first, think about what you want to ask, so we don't wind up with $17$ edits. –  Gerry Myerson Feb 15 '13 at 12:21
1  
@Sam: that is not a limitation according to the question that you actually asked. And, of course, once enough books are out then everyone will be reading at the same time. It's only at the beginning and end that some people have to wait. –  Carl Mummert Feb 15 '13 at 12:53
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.