All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Arbitrary Adventures Analysis (Posted on 2006-11-20) Difficulty: 3 of 5
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?

    No Solution Yet Submitted by Old Original Oskar!    
    Rating: 4.0000 (1 votes)

    Comments: ( Back to comment list | You must be logged in to post comments.)
    Solution maybe solution | Comment 3 of 9 |

    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
    Please log in:
    Login:
    Password:
    Remember me:
    Sign up! | Forgot password


    Search:
    Search body:
    Forums (0)
    Newest Problems
    Random Problem
    FAQ | About This Site
    Site Statistics
    New Comments (9)
    Unsolved Problems
    Top Rated Problems
    This month's top
    Most Commented On

    Chatterbox:
    Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information