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?

This amounts to the construction of a binary tree with 100 nodes.

If there were only one node (one page) there'd be only 1 possible book.

If there were two pages, there'd still be only one possible path: the first page leads to the last page.

If there are three pages, the story might have no branches, going 1, 2, 3.  Or page 1 could split into two endings.  That's a total of 2 possibilities.

If there are four pages, the story might have no branches, going 1, 2, 3, 4.  It might have page 1 leading to only one page, which then splits into 2 different endings.  Or, it might split from the very first page, in which case one of the two choices would have to end it and the other go to only one page, as there's only one additional page left.

So for 1, 2, 3 and 4 pages, there are 1, 1, 2, 3 possibilities, respectively.  It looks like the Fibonnacci series.  If so, the answer to the question is F(100) = 354,224,848,179,261,915,075.

Posted by Charlie on 2006-11-20 11:47:22