In the "Your own adventure" books, the reader starts at page 1, and every page either (1) ends the story, or (2) sends him to another page, or (3) offers a choice among two possible pages.

Knowing that:

each page can be reached from only one other page -- except for the 1st page, that cannot be reached from any page;

that all pages can eventually be reached by picking an appropriate path from page 1;

that if a book can be converted into another just by reordering choices and renumbering pages, they are considered to be the same;

and that these books are always 100 pages long...

How many essentially different books can be published?

The fact that all pages can eventually be reached by picking an appropriate path from page 1 means that only one page in the book can end the story.

The fact that each page can be reached from ONLY one other page means that no pages in fact offer a choice of two possible pages. Each page must direct you to exactly one other page. The reason for this is that excluding the first page there are 99 pages remaining to visit. Excluding the last page there are 99 pages which direct you to another page. Each page must therefore direct you to only one page. If a page directed you to two possible pages then both those pages could not be reached by any other page. This would have two consequences: there would be 97 pages left to receive an incoming path but 98 pages left to give an outgoing path. One page wouldn't be able to direct you anywhere and we have already said that only one page can end the story. The second consequence is that both of those pages could not be reached since you would have to choose between them and we are told that every page can be reached.

So given these two bits of information there must be the question comes down to how many ways can the remaining 99 pages be ordered. The answer is 99 factorial:

99*98*97*.....*3*2*1

Which is a very large number!

Posted by Paul on 2006-11-20 10:30:57