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 re(3): Program needed . . . Comment 9 of 9 |
    (In reply to re(2): Program needed . . . by Federico Kereki)

    then we get

    2       1
    3       2
    4       3
    5       6
    6       11
    7       23
    8       46
    9       98
    10      207
    11      451
    12      983
    13      2179
    14      4850
    15      10905
    16      24631
    17      56011
    18      127912
    19      293547
    20      676157
    21      1563372
    22      3626149
    23      8436379
    24      19680277
    25      46026618
    26      107890609
    27      253450711
    28      596572387
    29      1406818759
    30      3323236238
    31      7862958391
    32      18632325319
    33      44214569100
    34      105061603969
    35      249959727972
    36      595405363473
    37      1419855914607
    38      3389524479050
    39      8099766813570
    40      19374186136140
    41      46384328517112
    42      111146809165122
    43      266552682265118
    44      639754054803187
    45      1536638374367584
    46      3693555574543651
    47      8884204649055027
    48      21383602613828364
    49      51501493576783437
    50      124115016908960463
    51      299284329327592851
    52      722086038540594854
    53      1743130822668362889
    54      4210157426126929793
    55      10173859583519033930
    56      24597126243198759014
    57      59495869434450194896
    58      143974655017644718094
    59      348558271005906100616
    60      844206159208807054529
    61      2045499569096283221895
    62      4958179972866730572551
    63      12022969328821086710364
    64      29165037890838539578082
    65      70773347864023719770582
    66      171802146496610097519585
    67      417190639528111446770779
    68      1013405655241184415852284
    69      2462468880790152941279280
    70      5985395828928747830707833
    71      14552778100739451597075215
    72      35393719712730809489290451
    73      86105380575713265798811097
    74      209534148915752971906161599
    75      510030986091596821585587504
    76      1241802284488914041806071461
    77      3024262793585753830542718048
    78      7367072230435035735914703359
    79      17950473826186485808766524097
    80      43748166298406074100165156764
    81      106645908705895186413843585533
    82      260031824362822308996718870500
    83      634168120133303611054509027359
    84      1546947706732104170486643361489
    85      3774313656277441559498755236651
    86      9210630365092252808401739685165
    87      22481624182119802928656075014331
    88      54884662988678948399811499433020
    89      134016230818483951131182484937715
    90      327299265300988751439224581625959
    91      799488296094557358578760802052204
    92      1953245860469458186958527594063777
    93      4772849784961405441248983134896131
    94      11664686021905422496334056044980747
    95      28512887984332668599209035723441823
    96      69707693362642383731710653732858756
    97      170447287925675703040430908531836451
    98      416838603237108467066464398213155878
    99      1019560119620720464013531852138491082
    100     2494155217372585318678938493802359939

    giving

    2,494,155,217,372,585,318,678,938,493,802,359,939

    Sloane's A001190.

       10   dim F(100)
       20   F(1)=1
       30   for I=2 to 100
       40     T=F(I-1)
       50     J=I-2:K=1
       60     while J>=K
       65      if J=K then T=T+F(J)*(F(K)+1)//2
       70       :else T=T+F(J)*F(K)
       75      J=J-1:K=K+1
       80     wend
       85     F(I)=T
       90     print I,T
      100   next

    Edited on November 20, 2006, 3:58 pm
      Posted by Charlie on 2006-11-20 15:52:58

    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 (3)
    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